算法-初阶

罪恶克星 · 2024-8-28 21:08:08

文章目次

- -1.C++ 尺度
- 0.语法底子
- - 1. C++头文件
  - 2. C++定名空间
  - 3. 主函数
  - 4. 变量范例
  - 5. ASCII码
  - 6. 解释
- 1.次序结构
- - 一、代码示例
  - 二、例题1：求圆的面积
  - 三、例题2：求解一元二次方程
  - 四、总结：
- 2.分支结构
- - 一、代码示例
  - 二、例题1：判定一个数是否为偶数
  - 三、例题2：判定一个年份是否为闰年
  - 四、总结：分支结构是指程序在执行过程中根据条件判定选择差别的执行路径。
- 3.循环结构
- - 一、代码示例
  - 二、例题1：求1到n的累加和
  - 三、例题2：求斐波那契数列的第n项
- 4.数组
- - 一、代码示例
  - 二、例题1：求数组中最大值和最小值
  - 三、例题2：将一个数组中的全部元素乘以2
  - 四.总结
- 5.字符串
- - 一、字符串的基本操作
  - 二、例题1：检查回笔墨符串
  - 三、例题2：更换字符串中的字符
  - 四、例题3：截取字符串中的子串
  - 四.总结
- 6.函数
- - 一、函数的基本操作
  - 二、核心代码实例
  - 三、例题详解与AC代码&#xff08
    ;注：AC代码表示该代码能够通过标题给出的测试用例）
  - 例题1：互换两个变量的值&#xff08
    ;使用函数）
  - 例题2：计算斐波那契数列的第n项
  - 四.总结
- 7.结构体
- - 结构体的界说和示例：
  - - 1. 结构体作为函数参数和返回值：
    - 2. 结构体数组：
    - 3. 结构体嵌套：
  - 标题1：结构体储存结果
  - 标题2：结构体求均匀年龄
  - 标题3：结构体求最大年龄
  - 结构体在竞赛中的应用场景与总结：
  - - 1. **多属性的数据组织：**
    - 2. **简化代码：**
    - 3. **排序与比较：**
    - 4. **图的表示：**
    - 5. **模拟实体对象：**
  - 结构体在竞赛中的总结：
  - 结构体在竞赛中的应用示例：
- 8
  .模拟
- - 1. 模拟的作用与应用范围
  - 2. 模拟的三个例题
  - - 例题1：数字翻转
    - 例题2：字符串相加
    - 例题3：报数
  - 3. 总结与拓展
- 9.高精度
- - 0.引入
  - 2.高精度加法
  - 3.高精度减法
  - 4.高精度乘法
  - 5.高精度除法
  - 拓展：6.高精度开根
  - - 牛顿迭代法计算平方根
  - 标题一：高精度阶乘
  - - 标题描述
    - 解题思绪
    - C++ 代码
  - 标题二：高精度斐波那契数列
  - - 标题描述
    - 解题思绪
    - C++ 代码
  - 标题三：高精度计数
  - - 标题背景
    - 标题描述
    - 输入格式
    - 输特别式
    - 示例输入
    - 示例输出
    - 提示
  - 算法思绪
  - - C++ 代码
  - 总结：
- 10.排序
- - 常见的排序算法
  - 冒泡排序&#xff08
    ;Bubble Sort）
  - 选择排序&#xff08
    ;Selection Sort）
  - 插入排序&#xff08
    ;Insertion Sort）
  - 希尔排序&#xff08
    ;Shell Sort）
  - 快速排序&#xff08
    ;Quick Sort）
  - 归并排序&#xff08
    ;Merge Sort）
  - 堆排序&#xff08
    ;Heap Sort）
  - 计数排序&#xff08
    ;Counting Sort）
  - 桶排序&#xff08
    ;Bucket Sort）
  - 基数排序&#xff08
    ;Radix Sort）
  - 术语铺垫

-1.C++ 尺度

起首需要介绍的是 C++ 本身的版本。由于 C++ 本身只是一门语言，而差别的编译器对 C++ 的实现方法各不一致，因此需要尺度化来约束编译器的实现，使得 C++ 代码在差别的编译器下表现一致。C++ 自 198
5 年诞生以来，一共由国际尺度化组织&#xff08
;ISO）发布了 5 个正式的 C++ 尺度，依次为 C++98
、C++03、C++11&#xff08
;亦称 C++0x）、C++14&#xff08
;亦称 C++1y）、C++17&#xff08
;亦称 C++1z）、C++20&#xff08
;亦称 C++2a）。C++ 尺度草案在open-std 网站上，最新的尺度 C++23&#xff08
;亦称 C++2b）仍在订定中。此外还有一些增补尺度，例如 C++ TR1。
每一个版本的 C++ 尺度不仅规定了 C++ 的语法、语言特性，还规定了一套 C++ 内置库的实现规范，这个库便是 C++ 尺度库。C++ 尺度库中包含大量常用代码的实现，如输入输出、基本数据结构、内存管理、多线程支持等。把握 C++ 尺度库是编写更今世的 C++ 代码必要的一步。C++ 尺度库的详细文档在 cppconference 网站上，文档对尺度库中的范例函数的用法、效率、留意事项等都有介绍，请善用。
需要指出的是，差别的 OJ 平台对 C++ 版本均不类似，例如最新的ICPC角逐规则支持 C++20 尺度。根据 NOI 科学委员会决定，自 2021 年 9 月 1 日起 NOI Linux 2.0 作为 NOI 系列角逐和 CSP-J/S 等活动的尺度环境使用。NOI Linux 2.0 中指定的 g++ 9.3.0 默认支持尺度为 C++14，并支持 C++17 尺度，可以满足绝大部分竞赛选手的需求。因此在学习 C++ 时要留意角逐支持的尺度，避免在赛场上时编译报错。
0.语法底子

1. C++头文件

C++头文件&#xff08
;Header Files）用于声明或界说程序中使用的函数、变量、类等。通常使用.h或.hpp作为文件扩展名。
这里推荐大家使用万能头文件 #include<bits/stdc++.h>

#include<bits/stdc++.h>

复制代码

1

2. C++定名空间

定名空间&#xff08
;Namespace）用于避免定名辩说，将全局作用域划分为差别的地区。尺度库中的函数和对象位于std定名空间。
示例代码：

#include <iostream>
using namespace std; //c++命名空间
int main() {
std::cout << "Hello, World!" << std::endl;
return 0;
}

复制代码

1
2
3
4
5
6

3. 主函数

C++程序执行的入口是main函数。
示例代码：

int main() {
// 主函数体
return 0;
}

复制代码

1
2
3
4

'运行
运行
4. 变量范例

C++中有多种变量范例，包罗整数、浮点数、字符等。以下是一些常见的变量范例及其范围：
范例字节范围示例代码int4-2,147,48
3,648
到 2,147,48
3,647int num = 42;unsigned int40 到 4,294,967,295unsigned int x = 10;short2-32,768
到 32,767short s = 32767;long4-2,147,48
3,648
到 2,147,48
3,647long l = 12345678
9;long long8
-9,223,372,036,8
54,775,8
08
到 9,223,372,036,8
54,775,8
07long long ll = 12345678
9012345;float43.4e-38
到 3.4e+38
float f = 3.14f;double8
1.7e-308
到 1.7e+308
double d = 3.14;char1-128
到 127 或 0 到 255char ch = 'A';bool1true 或 falsebool flag = true; 5. ASCII码

ASCII码是字符编码系统，将字符映射到数字。以下是一些常见ASCII码的示例：
字符ASCII码A65a97048
$36 6. 解释

解释用于在代码中添加说明，不会被编译器执行。
示例代码：

// 这是单行注释
/*
这是
多行注释
*/

复制代码

1
2
3
4
5
6

以上是C++语法底子的一些要点，可根据需要深入学习每个部分的详细知识。
1.次序结构

C++中的次序结构是指按照代码的次序执行程序的过程。在次序结构中，程序从上到下依次执行代码块，没有分支和循环。
一、代码示例

#include <iostream>
using namespace std;
int main() {
int x = 10;
int y = 5;
int z = x + y;
cout << "x + y = " << z << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10

在这个示例中，我们界说了三个整型变量x、y和z，并将x和y相加，将结果存储在z中。然后，我们使用cout语句将结果输出到控制台。程序按照从上到下的次序执行代码块，没有使用任何分支或循环语句。
二、例题1：求圆的面积

思绪：我们可以先输入圆的半径，然后根据圆的面积公式πr²计算面积，并将结果输出到控制台。
代码如下：

#include <iostream>
#include <cmath>
using namespace std;
int main() {
double radius, area;
cout << "请输入圆的半径：" << endl;
cin >> radius;
area = M_PI * radius * radius; // 使用cmath库中的M_PI常量计算π的值。
cout << "圆的面积为：" << area << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12

三、例题2：求解一元二次方程

思绪：我们可以先输入一元二次方程的系数a、b和c，然后根据一元二次方程的解公式x=(-b±sqrt(b²-4ac))/2a计算解，并将结果输出到控制台。
代码如下：

#include <iostream>
#include <cmath>
using namespace std;
int main() {
double a, b, c, x1, x2;
cout << "请输入一元二次方程的系数a、b和c：" << endl;
cin >> a >> b >> c;
double discriminant = b * b - 4 * a * c; // 判别式的值。
if (discriminant < 0) { // 判别式小于0时方程无实数解。
cout << "方程无实数解。" << endl;
} else if (discriminant == 0) { // 判别式等于0时方程有一个实数解。
x1 = -b / (2 * a); // 直接计算出解的值。
cout << "方程有一个实数解：" << x1 << endl;
} else { // 判别式大于0时方程有两个实数解。
x1 = (-b + sqrt(discriminant)) / (2 * a); // 计算出两个解的值。
x2 = (-b - sqrt(discriminant)) / (2 * a); // 计算出两个解的值。
cout << "方程有两个实数解：" << x1 << " 和 " << x2 << endl;
}
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/663d8
779063b7aebcc18
3c457a532a7e.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、总结：

次序结构是指按照代码的次序依次执行程序的过程，没有分支和循环。在次序结构中，我们需要留意变量的作用域和生命周期，以及怎样处理异常情况。通过以上三个例题，我们可以看到次序结构在办理实际标题中的应用，例如求圆的面积、求解一元二次方程等。在实际应用中，我们还需要根据具体标题选择合适的数据结构和算法，以实现更高效和正确的计算结果。
2.分支结构

C++中的分支结构是指程序在执行过程中根据条件判定选择差别的执行路径。分支结构通常使用if语句、switch语句等来实现。
一、代码示例

#include <iostream>
using namespace std;
int main() {
int x = 10;
if (x > 5) {
cout << "x大于5" << endl;
} else {
cout << "x小于等于5" << endl;
}
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12

在这个示例中，我们界说了一个整型变量x，并使用if语句判定x是否大于5。假如条件满足，则输出"x大于5"，否则输出"x小于即是5"。
二、例题1：判定一个数是否为偶数

思绪：我们可以先输入一个整数，然后使用if语句判定该数是否为偶数，并输出相应的结果。
代码如下：

#include <iostream>
using namespace std;
int main() {
int num;
cout << "请输入一个整数：" << endl;
cin >> num;
if (num % 2 == 0) { // 判断是否为偶数。
cout << "该数是偶数。" << endl;
} else {
cout << "该数是奇数。" << endl;
}
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、例题2：判定一个年份是否为闰年

思绪：我们可以先输入一个年份，然后使用if语句判定该年份是否为闰年，并输出相应的结果。闰年的判定规则是：能被4整除但不能被100整除，大概能被400整除。
代码如下：

#include <iostream>
using namespace std;
int main() {
int year;
cout << "请输入一个年份：" << endl;
cin >> year;
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { // 判断是否为闰年。
cout << "该年是闰年。" << endl;
} else {
cout << "该年不是闰年。" << endl;
}
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、总结：分支结构是指程序在执行过程中根据条件判定选择差别的执行路径。

通过使用if语句、switch语句等，我们可以根据差别的条件执行差别的代码块。在办理实际标题时，分支结构可以帮助我们处理各种条件下的差别情况，提高程序的灵活性和可维护性。通过以上两个例题，我们可以看到分支结构在判定一个数是否为偶数、判定一个年份是否为闰年等实际应用中的使用。在实际应用中，我们还需要根据具体标题选择合适的数据结构和算法，以实现更高效和正确的计算结果。
3.循环结构

C++中的循环结构是指程序在执行过程中根据循环条件重复执行一段代码块。循环结构通常使用for语句、while语句和do-while语句等来实现。
一、代码示例

#include <iostream>
using namespace std;
int main() {
int n;
cout << "请输入一个整数：" << endl;
cin >> n;
for (int i = 1; i <= n; i++) { // 从1到n的循环。
cout << i << " ";
}
cout << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13

在这个示例中，我们使用for语句实现了一个从1到n的循环，每次循环输出当前的循环变量i的值。
二、例题1：求1到n的累加和

思绪：我们可以使用for语句实现从1到n的循环，每次循环将当前的数累加到总和中，末了输出总和。
代码如下：

#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cout << "请输入一个整数：" << endl;
cin >> n;
for (int i = 1; i <= n; i++) { // 从1到n的循环。
sum += i; // 将当前的数累加到总和中。
}
cout << "1到" << n << "的累加和为：" << sum << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13

三、例题2：求斐波那契数列的第n项

思绪：我们可以使用for语句实现一个从0到n-1的循环，每次循环计算斐波那契数列的两个连续项的值，并输出第n项的值。
代码如下：

#include <iostream>
using namespace std;
int main() {
int n, f1 = 0, f2 = 1, fn;
cout << "请输入一个整数n：" << endl;
cin >> n;
for (int i = 0; i < n - 1; i++) { // 从0到n-1的循环。
fn = f1 + f2; // 计算斐波那契数列的两个连续项的值。
f1 = f2; // 将f2的值赋给f1。
f2 = fn; // 将fn的值赋给f2。
}
cout << "斐波那契数列的第" << n << "项为：" << fn << endl; // 输出第n项的值。
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.数组

C++中的数组是一种用于存储固定巨细类似范例元素的数据结构。数组可以使用索引访问和修改数组元素的值。
一、代码示例

#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5}; // 定义一个包含5个整数的数组。
for (int i = 0; i < 5; i++) { // 循环访问数组元素。
cout << arr[i] << " "; // 输出数组元素的值。
}
cout << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11

在这个示例中，我们界说了一个包含5个整数的数组，并使用for循环访问数组元素，输出它们的值。
二、例题1：求数组中最大值和最小值

思绪：我们可以界说两个变量，分别用于存储数组中的最大值和最小值。然后遍历数组，比较每个元素与最大值和最小值的值，更新最大值和最小值。
代码如下：

#include <iostream>
using namespace std;
int main() {
int arr[] = {3, 7, 2, 9, 1}; // 定义一个包含5个整数的数组。
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组元素的个数。
int max = arr[0]; // 假设第一个元素为最大值。
int min = arr[0]; // 假设第一个元素为最小值。
for (int i = 1; i < n; i++) { // 从第二个元素开始遍历数组。
if (arr[i] > max) { // 如果当前元素大于最大值。
max = arr[i]; // 更新最大值。
}
if (arr[i] < min) { // 如果当前元素小于最小值。
min = arr[i]; // 更新最小值。
}
}
cout << "最大值为：" << max << endl; // 输出最大值。
cout << "最小值为：" << min << endl; // 输出最小值。
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、例题2：将一个数组中的全部元素乘以2

思绪：我们可以界说一个for循环，遍历数组中的每个元素，将其乘以2并更新原数组的值。
代码如下：

#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5}; // 定义一个包含5个整数的数组。
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组元素的个数。
for (int i = 0; i < n; i++) { // 循环遍历数组中的每个元素。
arr[i] *= 2; // 将当前元素乘以2并更新原数组的值。
}
for (int i = 0; i < n; i++) { // 循环访问数组元素。
cout << arr[i] << " "; // 输出数组元素的值。
}
cout << endl;
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

四.总结

在C++中，数组是一种用于存储固定巨细类似范例元素的数据结构。通过使用索引，我们可以访问和修改数组中的元素。
以上，我们通过2个例题展示了数组的基本应用，包罗怎样计算数组中的最大值和最小值、怎样将数组中的全部元素乘以2。
然而，请留意，对于大规模的数据处理，通常发起使用其他数据结构，例如向量&#xff08
;std::vector），因为它更灵活，并且可以动态地调解巨细。
总的来说，数组在C++中是一种基本且重要的数据结构，理解并把握其使用方法对于编写高效、可靠的代码至关重要。
5.字符串

C++中的字符串是一个非常重要的数据范例，它提供了许多操作来处理文本数据。下面我将为你提供字符串的基本操作和三个例题的详细思绪和正确代码，末了进行总结。
一、字符串的基本操作

字符串的声明和初始化

string str = "Hello, world!"; // 声明并初始化一个字符串变量

复制代码

1

字符串的拼接

string str1 = "Hello, ";
string str2 = "world!";
string str3 = str1 + str2; // 使用+运算符拼接字符串

复制代码

1
2
3

字符串的长度获取

string str = "Hello, world!";
int length = str.length(); // 获取字符串长度

复制代码

1
2

字符串的查找

string str = "Hello, world!";
size_t pos = str.find("world"); // 查找子串的位置，如果不存在则返回一个特殊值&#xff08
;string::npos）表示结束循环的条件。这里使用了size_t类型来存储位置值。

复制代码

1
2

字符串的更换

string str = "Hello, world!";
str.replace(str.find("world"), 5, "C++"); // 使用replace()函数替换子串为新的字符串。这里使用了replace()函数来替换子串为新的字符串。注意，这里替换的长度是子串的长度加1，以便跳过子串本身。这样，下一次循环时，位置变量将从新的起始位置开始查找。循环继续执行，直到找到最后一个子串的位置，并将最后一个子串替换为新的字符串。最后，输出替换后的字符串。这里使用了for循环来遍历字符串中的所有元素，并使用cout语句输出每个元素的值。最后，使用了一个空字符串作为最后一个元素的输出，以表示替换结束。这样，最终输出的结果将是替换后的字符串。注意，这里使用了replace()函数来替换子串为新的字符串，因为该函数可以指定替换的起始位置和长度，非常方便灵活。同时，这里使用了for循环来遍历字符串中的所有元素，并使用cout语句输出每个元素的值。最后，使用了一个空字符串作为最后一个元素的输出，以表示替换结束。这样，最终输出的结果将是替换后的字符串。

复制代码

1
2

二、例题1：检查回笔墨符串

思绪：我们可以使用双指针法或循环法来检查一个字符串是否是回笔墨符串。具体来说，我们可以从字符串的两端开始向中间比较字符，假如发现不匹配的字符则不是回笔墨符串，否则是回笔墨符串。时间复杂度为O(n)，其中n是字符串的长度。
正确代码：

#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(string str) {
int left = 0; // 左指针指向字符串的起始位置
int right = str.length() - 1; // 右指针指向字符串的末尾位置
while (left < right) { // 当左指针小于右指针时继续循环比较字符
if (str[left] != str[right]) { // 如果发现不匹配的字符则不是回文字符串，返回false。否则继续比较下一个字符。这里使用了if语句来判断字符是否相等。如果相等则继续比较下一个字符；如果不相等则返回false表示不是回文字符串。最后，使用了一个while循环来重复比较字符的过程，直到左指针大于或等于右指针时结束循环。最后，返回true表示是回文字符串。注意，这里使用了if语句来判断字符是否相等，如果相等则继续比较下一个字符；如果不相等则返回false表示不是回文字符串。同时，这里使用了while循环来重复比较字符的过程，直到左指针大于或等于右指针时结束循环。最后，返回true表示是回文字符串。这是一个基本的回文检查函数，可以在其他程序中重复使用。在实际应用中，根据具体需求选择合适的算法和数据结构可以提高程序的效率和可读性。
} else {
left++; // 如果字符相等，左指针向右移动一位
right--; // 如果字符相等，右指针向左移动一位
}
}
return true; // 如果整个字符串都已经被比较过，那么这个字符串就是一个回文字符串，返回true
}
int main() {
string str = "A man, a plan, a canal: Panama";
if (isPalindrome(str)) {
cout << str << " is a palindrome" << endl;
} else {
cout << str << " is not a palindrome" << endl;
}
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/db438
e9707ba5ce5c44e6fb4bb301ce1.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

三、例题2：更换字符串中的字符

思绪：我们可以使用C++中的字符串更换函数来更换字符串中的特定字符。具体来说，我们可以遍历字符串中的每个字符，假如发现需要更换的字符，则使用更换函数将其更换为新的字符。时间复杂度为O(n)，其中n是字符串的长度。
正确代码：

#include <iostream>
#include <string>
using namespace std;
void replaceChar(string& str, char oldChar, char newChar) {
for (int i = 0; i < str.length(); i++) {
if (str[i] == oldChar) { // 如果发现需要替换的字符
str[i] = newChar; // 使用替换函数将其替换为新的字符
}
}
}
int main() {
string str = "Hello, world!";
replaceChar(str, 'o', 'a'); // 替换所有的'o'字符为'a'字符
cout << str << endl; // 输出替换后的字符串
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/668
e34dbc599fe08
0cce4e990bda92f0.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、例题3：截取字符串中的子串

思绪：我们可以使用C++中的字符串切片操作来截取字符串中的子串。具体来说，我们可以指定起始位置和长度来截取子串。时间复杂度为O(1)，因为截取操作的时间复杂度与输入字符串的长度无关。
正确代码：

#include <iostream>
#include <string>
using namespace std;
string substr(string str, int start, int length) {
return str.substr(start, length); // 使用字符串切片操作来截取子串，并返回截取后的字符串。这里使用了substr()函数来截取子串，并指定起始位置和长度。最后，返回截取后的字符串。这个函数可以在其他程序中重复使用，以方便地截取字符串中的子串。在实际应用中，根据具体需求选择合适的算法和数据结构可以提高程序的效率和可读性。注意，这里使用了substr()函数来截取子串，并指定起始位置和长度。最后，返回截取后的字符串。这个函数可以在其他程序中重复使用，以方便地截取字符串中的子串。在实际应用中，根据具体需求选择合适的算法和数据结构可以提高程序的效率和可读性。
}
int main() {
string str = "Hello, world!";
string subStr = substr(str, 7, 5); // 截取从第7个字符开始的长度为5的子串
cout << subStr << endl; // 输出截取后的子串
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

四.总结

在C++中，字符串是一个非常重要的数据范例，提供了许多操作来处理文本数据。字符串的基本操作包罗声明和初始化、拼接、获取长度、查找和更换等。这些操作可以帮助我们处理字符串中的文本数据，实现各种文本处理使命。
在处理字符串时，我们可能会碰到一些特别的标题，比如检查回笔墨符串、更换字符串中的字符和截取字符串中的子串等。针对这些标题，我们可以使用C++提供的算法和函数来实现。比如，我们可以使用双指针法或循环法来检查一个字符串是否是回笔墨符串；可以使用更换函数来更换字符串中的特定字符；可以使用切片操作来截取字符串中的子串。
在实际应用中，我们需要留意选择合适的算法和数据结构来处理字符串，以提高程序的效率和可读性。此外，我们还应该留意输入的合法性，确保程序能够正确处理各种输入情况。同时，我们还应该留意程序的结实性，尽可能地减少程序中的错误和异常情况。
总之，C++中的字符串操作是一个重要的知识点，可以帮助我们更好地处理文本数据。在实际应用中，我们应该根据具体需求选择合适的算法和数据结构来处理字符串，以提高程序的效率和可读性。同时，我们也应该留意输入的合法性和程序的结实性，确保程序能够正确地处理各种输入情况和异常情况。
6.函数

一、函数的基本操作

函数是C++程序的基本组成单元，用于实现特定的功能。以下是函数的一些基本操作和核心代码实例：
函数的声明和界说
函数的声明告诉编译器函数的名称、返回范例和参数列表。而函数的界说则提供了函数的具体实现。

// 函数声明
void printHello();
// 函数定义
void printHello() {
cout << "Hello, world!" << endl;
}

复制代码

1
2
3
4
5
6
7

函数的调用
调用函数时，需要使用函数名，并提供所需的参数&#xff08
;假如有的话）。

int main() {
printHello(); // 调用函数printHello()
return 0;
}

复制代码

1
2
3
4

除了平常函数外，递归函数是一种特别的函数，它直接或间接地调用自身来办理标题。递归函数的基本操作包罗界说递归终止条件、编写递归函数体和调用递归函数。
界说递归终止条件：递归函数必须有一个或多个终止条件，当满足这些条件时，递归将克制。终止条件是递归函数的出口，确保递归不会无限进行下去。
编写递归函数体：递归函数体中必须包含对递归的调用，以便处理更小的子标题。函数体中还需要包含一些逻辑来处理当前标题，并将当前标题的结果与子标题的结果联合起来，以获得最终答案。
调用递归函数：在程序中，需要有一个或多个地方调用递归函数，以便开始递归过程。这些调用可以是直接或间接的，具体取决于标题的性质和所需办理的标题的复杂性。
递归函数通常用于办理具有递归性质的标题，例如树、图和聚集等数据结构的遍历，以及分治算法等。通过将标题分解为更小的子标题，递归函数能够简化标题的办理过程，并使代码更加简洁和易于理解。然而，使用递归函数需要留意避免栈溢出和正确处理终止条件，以确保程序的正确性和效率。
二、核心代码实例

以下是一个简朴的C++程序，其中包含了一个主函数main()和一个自界说函数printHello()：

#include <iostream>
using namespace std;
// 自定义函数：打印Hello, world!
void printHello() {
cout << "Hello, world!" << endl;
}
int main() {
printHello(); // 调用自定义函数printHello()
return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12

这个程序会在控制台输出"Hello, world!"。其中，printHello()函数用于实现这个功能。在main()函数中，我们调用了printHello()函数来执行这个操作。
三、例题详解与AC代码&#xff08
;注：AC代码表示该代码能够通过标题给出的测试用例）

例题1：互换两个变量的值&#xff08
;使用函数）

标题描述：编写一个C++程序，实现互换两个整数的值。要求使用函数来实现互换操作。
思绪分析：起首界说两个整数变量a和b，然后界说一个函数swap()来互换它们的值。在主函数中调用swap()函数，并输出互换后的结果。
AC代码：

#include <iostream>
using namespace std;
// 交换函数声明和定义
void swap(int& a, int& b);
// 交换函数实现
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int main() {
int a = 5, b = 10; // 定义两个整数变量a和b，并为其赋值
swap(a, b); // 调用swap()函数交换a和b的值
cout << "a = " << a << ", b = " << b << endl; // 输出结果：a = 10, b = 5
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/114d27358
22f72eb3a38
937b1161a3d6.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例题2：计算斐波那契数列的第n项

标题描述：编写一个C++程序，计算斐波那契数列的第n项。斐波那契数列是一个由0和1开始，之后的每一项都是前两项之和的数列。
思绪分析：
我们可以使用递归或迭代的方式来计算斐波那契数列的第n项。这里我们选择迭代的方式，因为它更加高效且不易堕落。我们界说两个变量f1和f2分别表示斐波那契数列的前两项，初始值为0和1。然后，我们使用一个循环来计算第n项的值，直到达到所需的项数。
递推AC代码：

#include <iostream>
int fibonacci(int n) {
if (n <= 1) {
return n;
}
int f1 = 0, f2 = 1;
for (int i = 2; i <= n; ++i) {
int temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
}
int main() {
int n = 10; // 要计算的斐波那契数列的项数
int result = fibonacci(n); // 调用fibonacci()函数计算第n项的值
std::cout << "斐波那契数列的第" << n << "项是：" << result << std::endl; // 输出结果
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/2f0338
0257e790abd6527dac21b90760.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个程序使用了fibonacci()函数来计算斐波那契数列的第n项。在主函数中，我们界说了要计算的项数n，并调用fibonacci()函数来获取结果。末了，我们输出结果。
固然，递归版本的斐波那契数列计算代码如下：

#include <iostream>
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int n = 10; // 要计算的斐波那契数列的项数
int result = fibonacci(n); // 调用fibonacci()函数计算第n项的值
std::cout << "斐波那契数列的第" << n << "项是：" << result << std::endl; // 输出结果
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/6ea8
3b9778
3ad70017bc372bdbaea28
9.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四.总结

这个版本的fibonacci()函数使用递归来计算斐波那契数列的第n项。假如n小于或即是1，它直接返回n。否则，它递归地调用自身来计算前两项的值，并将它们相加以获得第n项的值。
其实，递归版本的 fibonacci() 函数只能计算 n<=30 左右的 fibonacci(n),否则要么空间超限&#xff08
;栈溢出）或时间超时，原因就是 fibonacci(n - 1) 和 fibonacci(n - 2) 被重复调用，这时，可用数组记忆化，就是假如 fibonacci(n - 1) 或 fibonacci(n - 2) 被调用过，直接输出数组里的值，否则算出来，再用数组记载算出来的值，以下是对递归函数求斐波那契数列的ac代码：

#include<bits/stdc++.h>
int n;// 假设 n<= 1000int mark[1005];int fibonacci(int n){ if(mark[n] != 0) return mark[n]; // 记忆化 if(n <= 1) return n; else{ int res = fibonacci(n - 1) + fibonacci(n - 2); mark[n] = res; return res; }}int main(){ std::cin >> n; int result = fibonacci(n); std::cout << "斐波那契数列的第" << n << "项是：" << result << std::endl; // 输出结果 return 0;}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/3f40635febebdccdea8
544c336767b8
7.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7.结构体

结构体的界说和示例：

结构体是一种自界说数据范例，用于将差别范例的数据组合在一起。在C++中，通过struct关键字界说结构体。

#include <iostream>
#include <string>
// 定义结构体
struct Person {
std::string name;
int age;
double height;
};
int main() {
// 创建结构体实例
Person person1;
// 初始化结构体成员
person1.name = "John";
person1.age = 25;
person1.height = 175.5;
// 输出结构体成员
std::cout << "Name: " << person1.name << "\n";
std::cout << "Age: " << person1.age << "\n";
std::cout << "Height: " << person1.height << " cm\n";
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/f17d6d2f68
8
121ce166b7b12fb7371ba.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

结构体的操作：
1. 结构体作为函数参数和返回值：

#include <iostream>
#include <string>
struct Point {
double x, y;
};
// 函数参数为结构体
void printPoint(Point p) {
std::cout << "Point: (" << p.x << ", " << p.y << ")\n";
}
// 函数返回结构体
Point createPoint(double x, double y) {
Point p;
p.x = x;
p.y = y;
return p;
}
int main() {
Point point1 = {3.5, 2.8
};
printPoint(point1);
Point point2 = createPoint(1.0, 4.2);
printPoint(point2);
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/33ec17097713bdbf720a58
9c2a17c34b.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

操作代码示例结构体作为参数通报void printPoint(Point p)结构体作为返回值Point createPoint(double x, double y) 2. 结构体数组：

#include <iostream>
#include <string>
struct Student {
std::string name;
int age;
};
int main() {
const int numStudents = 3;
Student students[numStudents];
// 初始化结构体数组
students[0] = {"Alice", 20};
students[1] = {"Bob", 22};
students[2] = {"Charlie", 21};
// 输出结构体数组内容
for (int i = 0; i < numStudents; ++i) {
std::cout << "Student " << i + 1 << ": " << students[i].name << ", Age: " << students[i].age << "\n";
}
return 0;
}

复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/455bf4b44bdfc8
6b7cadd58
768
bebb75.png[/img]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

操作代码示例初始化结构体数组Student students[numStudents];访问结构体数组元素students.name, students.age 3. 结构体嵌套：

#include <iostream>
#include <string>
struct Address {
std::string city;
std::string street;
int zipCode;
};
struct Person {
std::string name;
int age;
Address address; // 结构体嵌套
};
int main() {
Person person1 = {"John", 30, {"New York", "Broadway St", 10001}};
// 输出嵌套结构体内容
std::cout << "Name: " << person1.name << "\n";
std::cout << "Age: " << person1.age << "\n";
std::cout << "Address: " << person1.address.street << ", " << person1.address.city << ", " << person1.address.zipCode << "\n";
return 0;
}
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/aecfbc0312cc73b3fc94d25768
8
3205f.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

操作代码示例结构体嵌套struct Person { Address address; };访问嵌套结构体成员person1.address.street, person1.address.city 关于结构体的三个例题：
标题1：结构体储存结果

标题描述：
界说一个结构体存储门生的信息，包罗门生的姓名、学号和三门课程的结果。编写一个程序，输入5个门生的信息，然后输出每个门生的总分。
思绪：

界说一个结构体Student，包罗成员变量name&#xff08
;姓名）、id&#xff08
;学号）和数组grades&#xff08
;存储三门课程的结果）。

界说一个函数calculateTotal，该函数担当一个Student范例的参数，计算该门生的总分，并返回总分。

在主程序中，界说一个包含5个Student对象的数组，输入每个门生的信息。

遍历数组，调用calculateTotal函数计算每个门生的总分，输出结果。

AC 代码：

#include <iostream>
#include <string>
// 定义结构体存储学生信息
struct Student {
std::string name;  // 学生姓名
int id;          // 学号
int grades[3];    // 三门课程的成绩
};
// 计算学生总分的函数
int calculateTotal(const Student& student) {
int total = 0;
for (int i = 0; i < 3; ++i) {
      total += student.grades[i];
}
return total;
}
int main() {
const int numStudents = 5;
Student students[numStudents];
// 输入学生信息
for (int i = 0; i < numStudents; ++i) {
      std::cout << "Enter student " << i + 1 << " information:" << std::endl;
      std::cout << "Name: ";
      std::cin >> students[i].name;
      std::cout << "ID: ";
      std::cin >> students[i].id;
      std::cout << "Grades for three courses:" << std::endl;
      for (int j = 0; j < 3; ++j) {
         std::cout << "Course " << j + 1 << ": ";
         std::cin >> students[i].grades[j];
      }
}
// 输出每个学生的总分
for (int i = 0; i < numStudents; ++i) {
      int total = calculateTotal(students[i]);
      std::cout << "Total score for student " << i + 1 << ": " << total << std::endl;
}
return 0;
}
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/b6c1a067028
4ba1506f938
237221c6b9.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

这个例子中，结构体Student存储了门生的姓名、学号和三门课程的结果。函数calculateTotal计算了门生的总分。在主程序中，通过数组存储5个门生的信息，然后输出每个门生的总分。
标题2：结构体求均匀年龄

标题：
给定门生结构体&#xff08
;姓名、年龄），责备部分生的均匀年龄。
标题链接
思绪：
遍历结构体数组，累加年龄，然后除以门生人数。
AC代码：

#include <iostream>
#include <vector>
struct Student {
std::string name;
int age;
};
int main() {
int n;
std::cin >> n;
std::vector<Student> students(n);
for (int i = 0; i < n; ++i) {
      std::cin >> students[i].name >> students[i].age;
}
int sumAge = 0;
for (const auto& student : students) {
      sumAge += student.age;
}
double averageAge = static_cast<double>(sumAge) / n;
std::cout << "Average Age: " << averageAge << "\n";
return 0;
}
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/09cc10450339a17fcf4b634df8
58
2065.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

标题3：结构体求最大年龄

标题：
给定门生结构体&#xff08
;姓名、年龄），责备部分生中的最大年龄。
标题链接
思绪：
遍历结构体数组，记载最大年龄。
AC代码：

#include <iostream>
#include <vector>
struct Student {
std::string name;
int age;
};
int main() {
int n;
std::cin >> n;
std::vector<Student> students(n);
for (int i = 0; i < n; ++i) {
      std::cin >> students[i].name >> students[i].age;
}
int maxAge = students[0].age;
for (const auto& student : students) {
      if (student.age > maxAge) {
         maxAge = student.age;
      }
}
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/f8
9668
b1f8
23d52fd25dc365b98
38
147.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

结构体在竞赛中的应用场景与总结：

1. 多属性的数据组织：

结构体在竞赛中常用于组织多个属性的数据，如门生的姓名、年龄、分数，大概图中的边的出发点、终点、权值等。这样可以更方便地对相干数据进行操作。
2. 简化代码：

在一些需要处理大量数据的场景，使用结构体可以帮助简化代码结构。通过界说合适的结构体，可以使代码更易读，减少冗余。
3. 排序与比较：

在排序或比较对象较为复杂的情况下，结构体提供了一种便捷的方式。可以使用std::sort等函数，通过自界说比较函数或Lambda表达式，灵活地进行排序。
4. 图的表示：

在图的算法中，结构体可以用于表示图的节点和边，方便处理图的相干操作。例如，使用结构体表示边的出发点、终点和权值，大概使用毗邻表结构体表示图的节点和毗邻关系。
5. 模拟实体对象：

当标题中涉及到模拟实体对象的场景时，结构体是一种自然的选择。例如，模拟一个游戏中的角色，结构体可以包含角色的属性和状态。
结构体在竞赛中的总结：

可读性提升： 结构体使得代码更加直观，通过成员变量的定名，可以清晰地相识数据的含义，提升了代码的可读性。

代码组织： 结构体有助于将相干的数据组织在一起，更好地维护和组织代码。

灵活性： 结构体在界说时可以包含各种范例的数据，使得其在差别场景下的应用更加灵活。

代码简化： 在处理多属性的数据时，使用结构体可以减少代码的冗余，使得代码更加简洁。

排序与比较： 结构体可以方便地进行排序与比较，对于需要处理大量数据的竞赛标题非常实用。

图的表示： 在图论相干标题中，结构体提供了一种清晰的方式来表示图的节点和边，方便进行图的算法实现。

结构体在竞赛中的应用示例：

标题：乌龟棋
标题与简朴思绪：
标题中需要模拟一个棋盘，每个格子上有差别的得分。可以使用结构体表示每个格子的坐标和得分，方便进行模拟操作。末了按照规则计算得分即可。
AC 代码：

#include <iostream>
#include <vector>
#include <algorithm>
struct Cell {
int x, y, score;
};
bool compareCell(const Cell& a, const Cell& b) {
return a.score > b.score;
}
int main() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<Cell> cells;
for (int i = 0; i < k; ++i) {
      Cell cell;
      std::cin >> cell.x >> cell.y >> cell.score;
      cells.push_back(cell);
}
std::sort(cells.begin(), cells.end(), compareCell);
int totalScore = 0;
for (int i = 0; i < std::min(k, n * m); ++i) {
      totalScore += cells[i].score;
}
std::cout << totalScore << "\n";
return 0;
}
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/676fb964ab998
52a96e33cfcb452e664.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

这个例子中，结构体 Cell 表示每个格子的坐标和得分，通过自界说比较函数 compareCell 按照得分降序排序。根据标题规则计算得分。
8
.模拟

C++ 模拟详解
1. 模拟的作用与应用范围

作用：
模拟是通过编写程序，按照标题描述的规则渐渐执行操作，最终得到标题的答案。在算法竞赛和编程中，模拟常用于办理具体标题的实现。
应用范围：
模拟广泛应用于模拟真实场景、计算机系统举动、物理过程等方面。在算法竞赛中，常用于实现标题的特定规则和操作。
2. 模拟的三个例题

例题1：数字翻转

标题背景：
给定一个整数，要求将其数字翻转。

[img]https://i-blog.csdnimg.cn/blog_migrate/aaf5cab578
3e24acbdef5297309e0d6a.png#pic_center[/img]

数据范围：
输入整数在 [-2^31, 2^31 - 1] 范围内。
标题链接：
LeetCode 7. Reverse Integer
详细思绪：

判定输入数字的正负。

将数字转为字符串，对字符串进行翻转。

转回整数，留意溢出情况。

AC代码：

class Solution {
public:
int reverse(int x) {
      long long result = 0;
      while (x != 0) {
         result = result * 10 + x % 10;
         x /= 10;
      }
      return (result < INT_MIN || result > INT_MAX) ? 0 : result;
}
};
复制代码

1

2

3

4

5

6

7

8

9

10

11

例题2：字符串相加

标题背景：
给定两个字符串形式的非负整数，求其和。

[img]https://i-blog.csdnimg.cn/blog_migrate/a35698
254dc0208
8
4f14d370153645fa.png#pic_center[/img]

数据范围：
字符串长度不超过1000。
标题链接：
LeetCode 415. Add Strings
详细思绪：

从字符串末端开始逐位相加，留意进位。

使用两个指针分别指向两个字符串的末端。

处理两字符串长度不等的情况。

AC代码：

class Solution {
public:
string addStrings(string num1, string num2) {
      int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
      string result = "";

      while (i >= 0 || j >= 0 || carry > 0) {
         int x = i >= 0 ? num1[i--] - '0' : 0;
         int y = j >= 0 ? num2[j--] - '0' : 0;
         int sum = x + y + carry;
         carry = sum / 10;
         result = to_string(sum % 10) + result;
      }

      return result;
}
};
复制代码

[img=44,32]https://img-blog.csdnimg.cn/img_convert/a9dfcd123db18
28
8
feda2461572bccee.png[/img]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

例题3：报数

标题背景：
报数序列是一个整数序列，第n项的描述如下：“1, 11, 21, 1211, 111221, …”。

[img]https://i-blog.csdnimg.cn/blog_migrate/20dab59a98
753c94791f7c8
c14b37e08
.png#pic_center[/img]

数据范围：
1 ≤ n ≤ 30。
标题链接：
LeetCode 38
. Count and Say
详细思绪：

从第一个数开始，依次生成下一个数。

对上一个数进行遍历，统计类似数字的个数。

将统计结果与数字拼接，作为下一个数。

AC代码：

class Solution {
public:
string countAndSay(int n) {
      if (n == 1) return "1";
      string prev = countAndSay(n - 1);
      string result = "";
      int count = 1;

      for (int i = 0; i < prev.size(); ++i) {
         if (i + 1 < prev.size() && prev[i] == prev[i + 1]) {
            count++;
         } else {
            result += to_string(count) + prev[i];
            count = 1;
         }
      }

      return result;
}
};
复制代码

3. 总结与拓展

总结：
模拟是一种常用的办理标题的方法，通过渐渐执行规则和操作，实现对具体标题的模拟。
拓展：

学习更复杂的模拟算法，如模拟物理过程、模拟系统举动等。

探索其他算法范畴，如动态规划、贪婪算法等。

到场实际项目，提高标题抽象和办理能力。

9.高精度

0.引入

高精度是争对c++本身变量变量无法运算的情况而产生的算法。
以下是第0节的各个变量的范围：
范例字节范围示例代码int4-2,147,48
3,648
到 2,147,48
3,647int num = 42;unsigned int40 到 4,294,967,295unsigned int x = 10;short2-32,768
到 32,767short s = 32767;long4-2,147,48
3,648
到 2,147,48
3,647long l = 12345678
9;long long8
-9,223,372,036,8
54,775,8
08
到 9,223,372,036,8
54,775,8
07long long ll = 12345678
9012345;float43.4e-38
到 3.4e+38
float f = 3.14f;double8
1.7e-308
到 1.7e+308
double d = 3.14;char1-128
到 127 或 0 到 255char ch = 'A';bool1true 或 falsebool flag = true; 假设我们做简朴的 a + b a+ba+b 标题，正常代码是这样的：

#include<bits/stdc++.h>
using namespace std;int a , b;int main(){ cin >> a >> b; cout << a + b << endl; return 0;}
复制代码
但是，当 a , b ≤ 9 , 223 , 372 , 036 , 8
54 , 775 , 8
08
a , b \le 9,223,372,036,8
54,775,8
08
a,b≤9,223,372,036,8
54,775,8
08
时，这样的代码就会出现错误。
这时就需要高精度了。
2.高精度加法

高精度加法是针对大整数的加法运算，通常是在数字超出了语言的整数表示范围时使用。在 C++ 中，可以通过字符串来表示大整数，然后进行高精度加法操作。以下是高精度加法的基本原理：

表示大整数： 将大整数按位逆序存储在字符串中，即个位存储在字符串的首位。这样方便从低位到高位进行遍历和计算。

对齐操作： 假如两个大整数长度差别，需要在短的整数高位补零，使得两个整数的位数类似。

逐位相加： 从低位到高位，逐位相加，将结果存储在一个新的字符串中。同时，考虑进位的情况。

处理最高位进位： 在计算完全部位数后，检查最高位是否有进位，假如有，需要将进位添加到结果的最高位。

下面是一个简朴的 C++ 代码示例，实现高精度加法，这个代码可以完全替代上面的发起代码：

#include <iostream>
#include <string>
using namespace std;
string add(string num1, string num2) {
int carry = 0;
string result = "";
// 对齐操作
while (num1.length() < num2.length()) num1 = "0" + num1;
while (num2.length() < num1.length()) num2 = "0" + num2;
// 逐位相加
for (int i = num1.length() - 1; i >= 0; i--) {
      int digit_sum = (num1[i] - '0') + (num2[i] - '0') + carry;
      carry = digit_sum / 10;
      result = char(digit_sum % 10 + '0') + result;
}
// 处理最高位进位
if (carry > 0) result = char(carry + '0') + result;
return result;
}
int main() {
string num1 = "12345678
9012345678
9012345678
90";
string num2 = "98
7654321098
7654321098
76543210";
string sum = add(num1, num2);
cout << "Sum: " << sum << endl;
return 0;
}
复制代码

3.高精度减法

高精度减法与高精度加法类似，但需要在计算时考虑借位的情况。以下是一个简朴的 C++ 代码示例，实现高精度减法：

#include <iostream>
#include <string>
using namespace std;
// 辅助函数，用于移除字符串前导零
string removeLeadingZeros(string num) {
int leadingZeros = 0;
while (leadingZeros < num.length() && num[leadingZeros] == '0') {
      leadingZeros++;
}
return num.substr(leadingZeros);
}
// 高精度减法函数
string subtract(string num1, string num2) {
string result = "";
int borrow = 0;
// 对齐操作
while (num1.length() < num2.length()) num1 = "0" + num1;
while (num2.length() < num1.length()) num2 = "0" + num2;
// 逐位相减
for (int i = num1.length() - 1; i >= 0; i--) {
      int digit_diff = (num1[i] - '0') - (num2[i] - '0') - borrow;
      if (digit_diff < 0) {
         digit_diff += 10;
         borrow = 1;
      } else {
         borrow = 0;
      }
      result = char(digit_diff + '0') + result;
}
// 移除结果中的前导零
result = removeLeadingZeros(result);
return result.empty() ? "0" : result;
}
int main() {
string num1 = "98
7654321098
7654321098
76543210";
string num2 = "12345678
9012345678
9012345678
90";
string difference = subtract(num1, num2);
cout << "Difference: " << difference << endl;
return 0;
}
复制代码

此代码实现了两个大整数的高精度减法，并输出了它们的差。请留意，代码中的 removeLeadingZeros 函数用于移除结果中的前导零。这样的高精度减法算法可以根据具体需要进行修改和扩展。
4.高精度乘法

接下来就是高精度乘法：

表示大整数： 大整数通常无法用尺度整数范例表示，因此我们使用字符串&#xff08
;string）来表示。字符串中的每个字符表示一个数字位，且字符串的次序是从低位到高位的逆序，即个位在字符串的首位。
例如，数值 12345678
9 在字符串中表示为 “98
7654321”。

逐位相乘： 高精度乘法的核心是逐位相乘。从低位到高位，将一个数字的每一位与另一个数字的每一位相乘。乘积保存在一个新的数组或字符串中，并需要考虑到可能的进位。

对齐相加： 将全部逐位相乘的结果相加。对齐相加是逐位相加的过程，需要考虑到可能的进位。每一位相加的结果除以 10 得到当前位的数字，余数作为当前位的结果，而商则作为进位被加到下一位的计算中。

处理进位： 在逐位相乘和对齐相加的过程中，需要处理进位。进位是由乘法和加法中某一位的计算产生的，需要被加到相邻的高位上。

下面是一个具体的高精度乘法的C++示例：

#include <iostream>
#include <vector>
using namespace std;
string multiply(string num1, string num2) {
int m = num1.size();
int n = num2.size();
vector<int> result(m + n, 0);
// 逐位相乘
for (int i = m - 1; i >= 0; i--) {
      for (int j = n - 1; j >= 0; j--) {
         int mul = (num1[i] - '0') * (num2[j] - '0');
         int sum = mul + result[i + j + 1];  // 当前位的数字与乘积之和
         result[i + j + 1] = sum % 10;    // 当前位的数字
         result[i + j] += sum / 10;       // 进位
      }
}
// 转换为字符串
string resultStr;
for (int digit : result) {
      if (!(resultStr.empty() && digit == 0)) {
         resultStr.push_back(digit + '0');
      }
}
return resultStr.empty() ? "0" : resultStr;
}
int main() {
string num1 = "12345678
9";
string num2 = "98
7654321";
string product = multiply(num1, num2);
cout << "Product: " << product << endl;
return 0;
}
复制代码

此代码演示了两个字符串表示的大整数的高精度乘法。
5.高精度除法

高精度除法虽然实用度较小，但我也讲一下吧。
高精度除法是处理大整数的除法运算，通常用于办理数字超出语言整数表示范围的情况。在 C++ 中，我们可以使用字符串来表示大整数，然后实现高精度除法。以下是高精度除法的基本原理：

表示大整数： 大整数通常用字符串来表示，其中字符串中的每个字符表示一个数字位，字符串的次序是从低位到高位的逆序，即个位在字符串的首位。

逐位相除： 从高位到低位，逐位进行相除。每一步中，将被除数的当前位与除数相除，得到商和余数。商作为当前位的结果，余数作为下一位的被除数。

对齐取商： 将每一位的商拼接起来，得到最终的商。

处理余数： 假如余数不为零，可以选择继续除以下一位，大概将余数作为小数部分添加到结果中。

下面是一个简朴的 C++ 代码示例，实现高精度除法：

#include <iostream>
#include <string>
using namespace std;
string divide(string num, int divisor) {
int n = num.size();
string quotient;
int remainder = 0;
for (int i = 0; i < n; i++) {
      int digit = (remainder * 10 + (num[i] - '0')) / divisor;
      quotient += to_string(digit);
      remainder = (remainder * 10 + (num[i] - '0')) % divisor;
}
// 移除结果中的前导零
size_t pos = quotient.find_first_not_of('0');
quotient = quotient.substr(pos);
return quotient.empty() ? "0" : quotient;
}
int main() {
string num = "12345678
9";
int divisor = 7;
string quotient = divide(num, divisor);
cout << "Quotient: " << quotient << endl;
return 0;
}
复制代码

这个代码实现了一个字符串表示的大整数除以一个整数的高精度除法，并输出了商。请留意，这里的代码仅处理整数的除法，假如需要考虑小数部分，还需要进行额外的处理。希望这个示例能够帮助理解高精度除法的基本原理。
拓展：6.高精度开根

计算高精度开根涉及到数值计算的数学标题，特别是平方根的计算。以下是一个基于牛顿迭代法的高精度开根算法的详细解释：
牛顿迭代法计算平方根

选择初始猜测值： 牛顿迭代法的第一步是选择一个初始的猜测值，通常选择被开方数的一半作为初始猜测值。
设被开方数为 num，初始猜测值 x0 为 num / 2。

迭代计算： 使用迭代公式进行更新，直到收敛。
迭代公式为 xi = (xi + num / xi) / 2。
具体来说，对于每次迭代，计算 xi 的新值，然后用新值替代旧值，直到 xi 的值不再发生明显变革。

收敛条件： 通常使用两次迭代之间的差值小于一个设定的阈值，作为收敛的条件。
即判定 abs(xi - xi-1) < epsilon，其中 epsilon 是一个小的正数，表示收敛的阈值。

返回结果： 最终的 xi 就是被开方数的平方根。

C++ 代码实现：
下面是一个简朴的 C++ 代码示例，使用牛顿迭代法计算高精度平方根：

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
string add(string num1, string num2) {
// 实现高精度加法
// ...
}
string divideByTwo(string num) {
// 实现高精度除以2
// ...
}
string sqrt(string num) {
string x = num;
string y = "0";
string two = "2";
// 设置收敛阈值 epsilon
double epsilon = 1e-12;
while (abs(stod(x) - stod(y)) > epsilon) {
      y = x;
      x = divideByTwo(add(x, divideByTwo(num, x)));  // x = (x + num / x) / 2
}
return x;
}
int main() {
string num = "12345678
9";
string result = sqrt(num);
cout << "Square Root of " << num << " is: " << result << endl;
return 0;
}
复制代码

在实际应用中，为了提高正确性和效率，可能需要使用更复杂的算法，例如二分法或牛顿法的改进版本。
理解你的要求，我会提供三个涉及高精度计算的标题，每个标题都会包罗详细的标题描述、解题思绪以及相应的 C++ 代码。
标题一：高精度阶乘

标题描述

给定一个整数 n，计算 n! 的值，其中 n! = n * (n-1) * (n-2) * ... * 2 * 1。
解题思绪

使用字符串表示大整数，然后按照乘法的方法进行计算。使用一个数组或字符串保存当前的结果，逐位进行乘法和进位的处理。
C++ 代码

#include <iostream>
#include <vector>
using namespace std;
string multiply(string num1, string num2) {
// 实现高精度乘法
// ...
}
string factorial(int n) {
string result = "1";
for (int i = 2; i <= n; i++) {
      result = multiply(result, to_string(i));
}
return result;
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
string result = factorial(n);
cout << n << "! = " << result << endl;
return 0;
}
复制代码

标题二：高精度斐波那契数列

标题描述

给定一个整数 n，计算斐波那契数列的第 n 项的值，其中斐波那契数列界说为 F(n) = F(n-1) + F(n-2)，且初始值为 F(0) = 0，F(1) = 1。
解题思绪

使用字符串表示大整数，按照递推公式计算斐波那契数列的值。需要处理大整数的加法。
C++ 代码

#include <iostream>
#include <vector>
using namespace std;
string add(string num1, string num2) {
// 实现高精度加法
// ...
}
string fibonacci(int n) {
if (n == 0) return "0";
if (n == 1) return "1";
string a = "0";
string b = "1";
for (int i = 2; i <= n; i++) {
      string temp = b;
      b = add(a, b);
      a = temp;
}
return b;
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
string result = fibonacci(n);
cout << "F(" << n << ") = " << result << endl;
return 0;
}
复制代码

标题三：高精度计数

标题背景

小明是一名天才数学家，他对数字非常感爱好。他发现了一个数字序列：1, 10, 100, 1000, 10000, …。现在，他想要统计这个序列中某个数字出现的次数。由于数字可能很大，他需要你设计一个算法来办理这个标题。
标题描述

给定一个整数 n&#xff08
;1 ≤ n ≤ 1 0 9 1 \leq n \leq 10^91≤n≤109），你需要统计数字 k 在上述数字序列中出现的次数。
输入格式

一行两个整数 n 和 k，表示要统计的数字和目的数字。
输特别式

一个整数，表示数字 k 在序列中出现的次数。
示例输入

15 1
复制代码
示例输出

8
复制代码
提示

在序列中，数字 1 出现了 8
次&#xff08
;1, 10, 100, 1000, 10000, 100000, 1000000, 10000000）。
算法思绪

观察序列可以发现，数字 k 在这个序列中出现的次数可以通过统计序列的每一位上 k 出现的次数来得到。具体地，设数字 n 有 d 位，那么从高位到低位，对于每一位 i，数字 k 在这一位上出现的次数为 n / (10^i) * 10^(i-1)。末了，还需要统计最高位的情况。
C++ 代码

#include <iostream>
using namespace std;
int countDigitK(int n, int k) {
int count = 0;
long long base = 1;  // 初始为最低位的位数
while (n / base > 0) {
      int curDigit = (n / base) % 10;  // 当前位的数字
      int higherDigits = n / (base * 10);  // 高位数字
      if (curDigit < k) {
         count += higherDigits * base;
      } else if (curDigit == k) {
         count += higherDigits * base + n % base + 1;
      } else {
         count += (higherDigits + 1) * base;
      }
      base *= 10;
}
return count;
}
int main() {
int n, k;
cin >> n >> k;
int result = countDigitK(n, k);
cout << result << endl;
return 0;
}
复制代码

总结：

高精度算法主要用于处理大整数运算，涉及到超过语言整数表示范围的整数计算。以下是 C++ 中高精度算法的常见实现以及总结：

高精度算法通常基于字符串实现，每个数字的每一位都用字符串中的一个字符表示。

在高精度加法和减法中，需要处理进位和借位。

高精度乘法接纳类似手工乘法的逐位相乘和进位相加的方式。

高精度除法模拟手工长除法的过程，逐位相除，得到商和余数。

10.排序

常见的排序算法

根据时间复杂度的差别，常见的算法可以分为3大类。
1.O(n²) 的排序算法

冒泡排序

选择排序

插入排序

2.O(n log n) 的排序算法

希尔排序

归并排序

快速排序

堆排序

3.线性的排序算法

计数排序

桶排序

基数排序

各种排序的具体信息

冒泡排序&#xff08
;Bubble Sort）

冒泡排序&#xff08
;Bubble Sort）是一种底子的 互换排序。
冒泡排序之所以叫冒泡排序，是因为它每一种元素都像小气泡一样根据自身巨细一点一点往数组的一侧移动。
算法步骤如下：

比较相邻的元素。假如第一个比第二个大，就互换他们两个；

对每一对相邻元素作同样的工作，从开始第一对到末端的末了一对。这步做完后，末了的元素会是最大的数；

针对全部的元素重复以上的步骤，除了末了一个；

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/d504debb9317d8
119a5b97aeedfa8
2fd.gif[/img]

代码如下：

void bubbleSort(vector<int\> &a)
{
int len = a.size();
for (int i = 0; i < len - 1; i++) //需要循环次数
{
      for (int j = 0; j < len - 1 - i; j++) //每次需要比较个数
      {
         if (a[j] > a[j + 1])
         {
            swap(a[j], a[j + 1]); //不满足偏序，交换
         }
      }
}
}
复制代码
还有一种假的写法就是保证第一个最小，第二个次小，比较的是 i 和 j ，虽然也是对的，有点像选择排序，但也不是。其不是冒泡排序
选择排序&#xff08
;Selection Sort）

选择排序&#xff08
;Selection sort）是一种简朴直观的排序算法。
选择排序的主要长处与数据移动有关。
假如某个元素位于正确的最终位置上，则它不会被移动。
选择排序每次互换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序统共进行至多 n - 1 次互换。在全部的完全依靠互换去移动元素的排序方法中，选择排序属于非常好的一种。
选择排序的算法步骤如下：

在未排序序列中找到最小&#xff08
;大）元素，存放到排序序列的起始位置；

然后，再从剩余未排序元素中继续寻找最小&#xff08
;大）元素，然后放到已排序序列的末端；

以此类推，直到全部元素均排序完毕。

图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/158
fb8
75c78
08
3cbc6e1f9a38
da9ccee.gif[/img]

代码如下：

void selectionSort(vector<int> &a)
{
int len = a.size();
for (int i = 0, minIndex; i < len - 1; i++) //需要循环次数
{
      minIndex = i;                   //最小下标
      for (int j = i + 1; j < len; j++) //访问未排序的元素
      {
         if (a[j] < a[minIndex])
            minIndex = j; //找到最小的
      }
      swap(a[i], a[minIndex]);
}
}
复制代码
插入排序&#xff08
;Insertion Sort）

插入排序&#xff08
;Insertion sort）是一种简朴直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序的算法步骤如下：

从第一个元素开始，该元素可以认为已经被排序；

取出下一个元素，在已经排序的元素序列中从后向前扫描；

假如该元素&#xff08
;已排序）大于新元素，将该元素移到下一位置；

重复步骤3，直到找到已排序的元素小于大概即是新元素的位置；

将新元素插入到该位置后；

重复步骤2~5。

图示如下：

代码如下：

void insertionSort(vector<int> &a)
{
int len = a.size();
for (int i = 0, j, temp; i < len - 1; i++) //需要循环次数
{
      j = i;
      temp = a[i + 1];
      while (j >= 0 && a[j] > temp)
      {
         a[j + 1] = a[j];
         j--;
      }
      a[j + 1] = temp;
}
}
复制代码
希尔排序&#xff08
;Shell Sort）

希尔排序，也称 递减增量排序算法，是 插入排序 的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到 线性排序 的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

步长的选择是希尔排序的重要部分。
只要最终步长为1任何步长序列都可以工作。
算法最开始以肯定的步长进行排序。
然后会继续以肯定步长进行排序，最终算法以步长为1进行排序。
当步长为1时，算法变为平常插入排序，这就保证了数据肯定会被排序。
希尔排序的算法步骤如下：

界说一个用来分割的步长；

按步长的长度K，对数组进行K趟排序；

不断重复上述步骤。

图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/545cabdddd103c4d4b21e7d05463a8
11.gif[/img]

代码如下：

void shell_Sort(vector<int> &a)
{
int len = a.size();
for (int gap = len / 2; gap > 0; gap /= 2)
{
      for (int i = 0; i < gap; i++)
      {
         for (int j = i + gap, temp, preIndex; j < len; j = j + gap) //依旧需要temp作为哨兵
         {
            temp = a[j];       //保存哨兵
            preIndex = j - gap; //将要对比的编号
            while (preIndex >= 0 && a[preIndex]>temp)
                  {
                     a[preIndex + gap] = a[preIndex]; //被替换
                     preIndex -= gap;                //向下走一步
                  }
            a[preIndex + gap] = temp; //恢复被替换的值
         }
      }
}
}
}
复制代码

快速排序&#xff08
;Quick Sort）

快速排序&#xff08
;Quicksort），又称划分互换排序&#xff08
;partition-exchange sort）。
快速排序&#xff08
;Quicksort）在均匀状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。究竟上，快速排序 O(n log n) 通常显着比其他算法更快，因为它的内部循环&#xff08
;inner loop）可以在大部分的架构上很有用率地达成。
快速排序使用分治法&#xff08
;Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
快速排序的算法步骤如下：

挑选基准值：从数列中挑出一个元素，称为 “基准”&#xff08
;pivot）；

分割：重新排序序列，全部比基准值小的元素摆放在基准前面，全部比基准值大的元素摆在基准后面&#xff08
;与基准值相等的数可以到任何一边）。在这个分割竣事之后，对基准值的排序就已经完成；

递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判定条件是序列的巨细是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/2318
56a6e5b0451502e1dedba48
73256.gif[/img]

代码如下：

int partition(vector<int> &a, int left, int right)
{
int pivot = a[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
      if (a[j] <= pivot)
      {
         i++;
         swap(a[i], a[j]);
      }
}
swap(a[i + 1], a[right]);
return i + 1;
}
void quickSort(vector<int> &a, int left, int right)
{
if (left < right)
{
      int mid = partition(a, left, right);
      quickSort(a, left, mid - 1);
      quickSort(a, mid + 1, right);
}
}
void qSort(vector<int> &a)
{
quickSort(a, 0, a.size() - 1);
}
复制代码

归并排序&#xff08
;Merge Sort）

归并排序&#xff08
;Merge sort），是创建在归并操作上的一种有用的排序算法，时间复杂度为 O(n log n) 。1945年由约翰·冯·诺伊曼初次提出。该算法是接纳分治法&#xff08
;Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
其实说白了就是将两个已经排序的序列归并成一个序列的操作。
并归排序有两种实现方式

[img]https://i-blog.csdnimg.cn/blog_migrate/bfb7cbf8
603e3dd3b7c8
62d8
c8
7f095a.gif[/img]

第一种是 自上而下的递归 ，算法步骤如下：

申请空间，使其巨细为两个已经排序序列之和，该空间用来存放归并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到归并空间，并移动指针到下一位置；

重复步骤3直到某一指针到达序列尾；

将另一序列剩下的全部元素直接复制到归并序列尾。

void mergeSort(vector<int> &a, vector<int> &T, int left, int right)
{
if (right - left == 1)
      return;
int mid = left + right >> 1, tmid = left + right >> 1, tleft = left, i = left;
mergeSort(a, T, left, mid), mergeSort(a, T, mid, right);
while (tleft < mid || tmid < right)
{
      if (tmid >= right || (tleft < mid && a[tleft] <= a[tmid]))
      {
         T[i++] = a[tleft++];
      }
      else
      {
         T[i++] = a[tmid++];
      }
}
for (int i = left; i < right; i++)
      a[i] = T[i];
}
void mSort(vector<int> &a)
{
int len = a.size();
vector<int> T(len);
mergeSort(a, T, 0, len);
}
复制代码

迭代比起递归还是安全许多，太深的递归轻易导致堆栈溢出。所以发起可以试下迭代实现，acm里是够用了
堆排序&#xff08
;Heap Sort）

堆排序&#xff08
;Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆是一个近似 完全二叉树 的结构，并同时满足 堆积的性质 ：即子节点的键值或索引总是小于&#xff08
;大概大于）它的父节点。
二叉堆是什么？
二叉堆分以下两个范例：
1.最大堆：最大堆任何一个父节点的值，都大于即是它左右孩子节点的值。

图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/f558
3f8
b4ec7ab7c5aa5e7a8
df54e034.png[/img]

数组表示如下：
[10, 8
, 9, 7, 5, 4, 6, 3, 2]

2.最小堆：最小堆任何一个父节点的值，都小于即是它左右孩子节点的值。

图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/3bd94d8
1bdd3deef48
bb2743cbb54b8
b.png[/img]

数组表示如下：
[1, 3, 2, 6, 5, 7, 8
, 9, 10]

堆排序的算法步骤如下：

把无序数列构建成二叉堆；

循环删除堆顶元素，更换到二叉堆的末端，调解堆产生新的堆顶。

代码如下：

void adjustHeap(vector<int> &a, int i,int len){ int maxIndex = i; //假如有左子树，且左子树大于父节点，则将最大指针指向左子树 if (i * 2 + 1 < len && a[i * 2 + 1] > a[maxIndex])       maxIndex = i * 2 + 1; //假如有右子树，且右子树大于父节点和左节点，则将最大指针指向右子树 if (i * 2 + 2 < len && a[i * 2 + 2] > a[maxIndex])       maxIndex = i * 2 + 2; //假如父节点不是最大值，则将父节点与最大值互换，并且递归调解与父节点互换的位置。 if (maxIndex != i) {       swap(a[maxIndex], a[i]);       adjustHeap(a, maxIndex,len); }}void Sort(vector<int> &a){ int len = a.size(); //1.构建一个最大堆 for (int i = len / 2 - 1; i >= 0; i--) //从末了一个非叶子节点开始 {       adjustHeap(a, i,len); } //2.循环将堆首位&#xff08
;最大值）与末位互换，然后在重新调解最大堆 for (int i = len - 1; i > 0; i--) {       swap(a[0], a[i]);       adjustHeap(a, 0, i); }}
复制代码

我这里用了递归写法，非递归也很简朴，就是比较哪个叶子节点大，再继续for下去
计数排序&#xff08
;Counting Sort）

计数排序&#xff08
;Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组来存储输入的元素，计数排序要求输入的数据必须是有确定范围的整数。
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k) 。计数排序不是比较排序，排序的速度快于任何比较排序算法。
计数排序的算法步骤如下：

找出待排序的数组中最大和最小的元素；

统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；

对全部的计数累加&#xff08
;从数组 C 中的第一个元素开始，每一项和前一项相加）；

反向填充目的数组：将每个元素 i 放在新数组的第 C 项，每放一个元素就将 C 减去1。

代码如下：

void CountingSort(vector<int> &a)
{
int len = a.size();
if (len == 0)
      return;
int Min = a[0], Max = a[0];
for (int i = 1; i < len; i++)
{
      Max = max(Max, a[i]);
      Min = min(Min, a[i]);
}
int bias = 0 - Min;
vector<int> bucket(Max - Min + 1, 0);
for (int i = 0; i < len; i++)
{
      bucket[a[i] + bias]++;
}
int index = 0, i = 0;
while (index < len)
{
      if (bucket[i])
      {
         a[index] = i - bias;
         bucket[i]--;
         index++;
      }
      else
         i++;
}
}
复制代码

桶排序&#xff08
;Bucket Sort）

桶排序&#xff08
;Bucket Sort）跟计数排序&#xff08
;Counting sort）一样是一种稳定的线性时间排序算法，不过这次需要的辅助不是计数，而是桶。
工作的原理是将数列分到有限数量的桶里。每个桶再个别排序。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)。
桶排序的算法步骤如下：

设置一个定量的数组看成空桶子；

寻访序列，并且把项目一个一个放到对应的桶子去；

对每个不是空的桶子进行排序；

从不是空的桶子里把项目再放回原来的序列中。

代码如下：
我觉得递归调用桶排序比较慢，这里直接用了sort函数，其实这个函数能决定这个算法的优劣，这些排序都是针对固定的序列的，可以自己实行差别的算法去优化
size为1是，其实和计数排序是一样的，不过这里使用了辅助的空间，没有归并类似的，内存斲丧要更大

void bucketSort(vector<int> &a, int bucketSize)
{
int len = a.size();
if (len < 2)
      return;
int Min = a[0], Max = a[0];
for (int i = 1; i < len; i++)
{
      Max = max(Max, a[i]);
      Min = min(Min, a[i]);
}
int bucketCount = (Max - Min) / bucketSize + 1;
//这个区间是max-min+1，但是我们要向上取整，就是+bucketSize-1，和上面的形式是一样的
vector<int> bucketArr[bucketCount];
for (int i = 0; i < len; i++)
{
      bucketArr[(a[i] - Min) / bucketSize].push_back(a[i]);
}
a.clear();
for (int i = 0; i < bucketCount; i++)
{
      int tlen = bucketArr[i].size();
      sort(bucketArr[i].begin(),bucketArr[i].end());
      for (int j = 0; j < tlen; j++)
         a.push_back(bucketArr[i][j]);
}
}
复制代码

基数排序&#xff08
;Radix Sort）

基数排序&#xff08
;Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成差别的数字，然后按每个位数分别比较。由于整数也可以表达字符串&#xff08
;比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
工作原理是将全部待比较数值&#xff08
;正整数）同一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以接纳 LSD&#xff08
;Least significant digital）或 MSD&#xff08
;Most significant digital）。
LSD 的排序方式由键值的最右边&#xff08
;最小位）开始，而 MSD 则相反，由键值的最左边&#xff08
;最大位）开始。
MSD 方式实用于位数多的序列，LSD 方式实用于位数少的序列。
基数排序 、 桶排序 、 计数排序 原理都差不多，都借助了 “桶” 的概念，但是使用方式有显着的差别，其差别如下：

基数排序：根据键值的每位数字来分配桶；

桶排序：每个桶存储肯定范围的数值；

计数排序：每个桶只存储单一键值。

LSD 图示如下：

[img]https://i-blog.csdnimg.cn/blog_migrate/fbc4e428
34d118
234de738
54dd6f5a59.gif[/img]

LSD 实现如下：
留意不要用负数，用负数完全相反，正负都有可以都转换为正数

void RadixSortSort(vector<int> &a)
{
int len = a.size();
if (len < 2)
      return;
int Max = a[0];
for (int i = 1; i < len; i++)
{
      Max = max(Max, a[i]);
}
int maxDigit = log10(Max) + 1;
//直接使用log10函数获取位数，这样的话就不用循环了，这里被强制转换是向下取整
int mod = 10, div = 1;
vector<int> bucketList[10];
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10)
{
      for (int j = 0; j < len; j++)
      {
         int num = (a[j] % mod) / div;
         bucketList[num].push_back(a[j]);
      }
      int index = 0;
      for (int j = 0; j < 10; j++)
      {
         int tlen=bucketList[j].size();
         for (int k = 0; k < tlen; k++)
            a[index++] = bucketList[j][k];
         bucketList[j].clear();
      }
}
}
复制代码

术语铺垫

稳定排序：假如 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
非稳定排序：假如 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和互换的数据排序。
非原地排序：需要利用额外的数组来辅助排序。
时间复杂度：一个算法执行所斲丧的时间。
空间复杂度：运行完一个算法所需的内存巨细。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

算法-初阶

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云