devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c++史上最全算法详解，0基础可秒懂！（爆肝4万字）

作者：Li_阴宅 | 2024-08-03 00:19:56

赞

踩

c++

本文极长，建议点赞收藏后看！
质量分95+！！

文章目录

-1.C++ 标准

首先需要介绍的是 C++ 本身的版本。由于 C++ 本身只是一门语言，而不同的编译器对 C++ 的实现方法各不一致，因此需要标准化来约束编译器的实现，使得 C++ 代码在不同的编译器下表现一致。C++ 自 1985 年诞生以来，一共由国际标准化组织（ISO）发布了 5 个正式的 C++ 标准，依次为 C++98、C++03、C++11（亦称 C++0x）、C++14（亦称 C++1y）、C++17（亦称 C++1z）、C++20（亦称 C++2a）。C++ 标准草案在open-std 网站上，最新的标准 C++23（亦称 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++头文件（Header Files）用于声明或定义程序中使用的函数、变量、类等。通常使用.h或.hpp作为文件扩展名。

这里推荐大家使用万能头文件 #include<bits/stdc++.h>

#include<bits/stdc++.h>

  • 1

2. C++命名空间

命名空间（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,483,648 到 2,147,483,647int num = 42;
unsigned int40 到 4,294,967,295unsigned int x = 10;
short2-32,768 到 32,767short s = 32767;
long4-2,147,483,648 到 2,147,483,647long l = 123456789;
long long8-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807long long ll = 123456789012345;
float43.4e-38 到 3.4e+38float f = 3.14f;
double81.7e-308 到 1.7e+308double d = 3.14;
char1-128 到 127 或 0 到 255char ch = 'A';
bool1true 或 falsebool flag = true;

5. ASCII码

ASCII码是字符编码系统，将字符映射到数字。以下是一些常见ASCII码的示例：

字符ASCII码
A65
a97
048
$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;  
}

  • 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。

然而，请注意，对于大规模的数据处理，通常建议使用其他数据结构，例如向量（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");  // 查找子串的位置，如果不存在则返回一个特殊值（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;  
}

  • 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;  
}

  • 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

函数的调用
调用函数时，需要使用函数名，并提供所需的参数（如果有的话）。

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代码（注：AC代码表示该代码能够通过题目给出的测试用例）

例题1：交换两个变量的值（使用函数）

题目描述：编写一个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;  
}

  • 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;  
}

  • 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;  
}

  • 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),否则要么空间超限（栈溢出）或时间超时，原因就是 fibonacci(n - 1) 和 fibonacci(n - 2) 被重复调用，这时，可用数组记忆化，就是如果 fibonacci(n - 1) 或 fibonacci(n - 2) 被调用过，直接输出数组里的值，否则算出来，再用数组记录算出来的值，以下是对递归函数求斐波那契数列的ac代码：

#include<bits/stdc++.h>
int n;// 假设 n<= 1000
int 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;
}

  • 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;
}

  • 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;
}

  • 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;
}

  • 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[i].name, students[i].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;
}

  • 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个学生的信息，然后输出每个学生的总分。

思路：

  1. 定义一个结构体Student，包括成员变量name（姓名）、id（学号）和数组grades（存储三门课程的成绩）。
  2. 定义一个函数calculateTotal，该函数接受一个Student类型的参数，计算该学生的总分，并返回总分。
  3. 在主程序中，定义一个包含5个Student对象的数组，输入每个学生的信息。
  4. 遍历数组，调用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;
}

  • 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：结构体求平均年龄

题目：
给定学生结构体（姓名、年龄），求所有学生的平均年龄。

题目链接

思路：
遍历结构体数组，累加年龄，然后除以学生人数。

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;
}

  • 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：结构体求最大年龄

题目：
给定学生结构体（姓名、年龄），求所有学生中的最大年龄。

题目链接

思路：
遍历结构体数组，记录最大年龄。

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;
        }
    }

  • 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;
}

  • 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：数字翻转

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

在这里插入图片描述

数据范围：
输入整数在 [-2^31, 2^31 - 1] 范围内。

题目链接：
LeetCode 7. Reverse Integer

详细思路：

  1. 判断输入数字的正负。
  2. 将数字转为字符串，对字符串进行翻转。
  3. 转回整数，注意溢出情况。

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：字符串相加

题目背景：
给定两个字符串形式的非负整数，求其和。
在这里插入图片描述

数据范围：
字符串长度不超过1000。

题目链接：
LeetCode 415. Add Strings

详细思路：

  1. 从字符串末尾开始逐位相加，注意进位。
  2. 使用两个指针分别指向两个字符串的末尾。
  3. 处理两字符串长度不等的情况。

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
例题3：报数

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

在这里插入图片描述

数据范围：
1 ≤ n ≤ 30。

题目链接：
LeetCode 38. Count and Say

详细思路：

  1. 从第一个数开始，依次生成下一个数。
  2. 对上一个数进行遍历，统计相同数字的个数。
  3. 将统计结果与数字拼接，作为下一个数。

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;
    }
};

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

3. 总结与拓展

总结：
模拟是一种常用的解决问题的方法，通过逐步执行规则和操作，实现对具体问题的模拟。

拓展：

  1. 学习更复杂的模拟算法，如模拟物理过程、模拟系统行为等。
  2. 探索其他算法领域，如动态规划、贪心算法等。
  3. 参与实际项目，提高问题抽象和解决能力。

9.高精度

0.引入

高精度是争对c++本身变量变量无法运算的情况而产生的算法。
以下是第0节的各个变量的范围：

类型字节范围示例代码
int4-2,147,483,648 到 2,147,483,647int num = 42;
unsigned int40 到 4,294,967,295unsigned int x = 10;
short2-32,768 到 32,767short s = 32767;
long4-2,147,483,648 到 2,147,483,647long l = 123456789;
long long8-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807long long ll = 123456789012345;
float43.4e-38 到 3.4e+38float f = 3.14f;
double81.7e-308 到 1.7e+308double d = 3.14;
char1-128 到 127 或 0 到 255char ch = 'A';
bool1true 或 falsebool flag = true;

假设我们做简单的 a + b a+b a+b 问题，正常代码是这样的：

#include<bits/stdc++.h>
using namespace std;
int a , b;
int main(){
	cin >> a >> b;
	cout << a + b << endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

但是，当 a , b ≤ 9 , 223 , 372 , 036 , 854 , 775 , 808 a , b \le 9,223,372,036,854,775,808 a,b≤9,223,372,036,854,775,808 时，这样的代码就会出现错误。
这时就需要高精度了。

2.高精度加法

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

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

  2. 对齐操作： 如果两个大整数长度不同，需要在短的整数高位补零，使得两个整数的位数相同。

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

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

下面是一个简单的 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 = "123456789012345678901234567890";
    string num2 = "987654321098765432109876543210";

    string sum = add(num1, num2);

    cout << "Sum: " << sum << endl;

    return 0;
}

  • 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

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 = "987654321098765432109876543210";
    string num2 = "123456789012345678901234567890";

    string difference = subtract(num1, num2);

    cout << "Difference: " << difference << endl;

    return 0;
}

  • 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
  • 46
  • 47
  • 48
  • 49
  • 50

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

4.高精度乘法

接下来就是高精度乘法：

  1. 表示大整数： 大整数通常无法用标准整数类型表示，因此我们使用字符串（string）来表示。字符串中的每个字符表示一个数字位，且字符串的顺序是从低位到高位的逆序，即个位在字符串的首位。

    例如，数值 123456789 在字符串中表示为 “987654321”。

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

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

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

下面是一个具体的高精度乘法的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 = "123456789";
    string num2 = "987654321";

    string product = multiply(num1, num2);

    cout << "Product: " << product << endl;

    return 0;
}

  • 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

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

5.高精度除法

高精度除法虽然实用度较小，但我也讲一下吧。

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

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

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

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

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

下面是一个简单的 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 = "123456789";
    int divisor = 7;

    string quotient = divide(num, divisor);

    cout << "Quotient: " << quotient << endl;

    return 0;
}

  • 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

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

拓展：6.高精度开根

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

牛顿迭代法计算平方根

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

    设被开方数为 num，初始猜测值 x0 为 num / 2。

  2. 迭代计算： 使用迭代公式进行更新，直到收敛。

    迭代公式为 xi = (xi + num / xi) / 2。

    具体来说，对于每次迭代，计算 xi 的新值，然后用新值替代旧值，直到 xi 的值不再发生显著变化。

  3. 收敛条件： 通常使用两次迭代之间的差值小于一个设定的阈值，作为收敛的条件。

    即判断 abs(xi - xi-1) < epsilon，其中 epsilon 是一个小的正数，表示收敛的阈值。

  4. 返回结果： 最终的 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 = "123456789";

    string result = sqrt(num);

    cout << "Square Root of " << num << " is: " << result << endl;

    return 0;
}

  • 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

在实际应用中，为了提高准确性和效率，可能需要使用更复杂的算法，例如二分法或牛顿法的改进版本。
理解你的要求，我会提供三个涉及高精度计算的题目，每个题目都会包括详细的题目描述、解题思路以及相应的 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;
}

  • 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

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

题目描述

给定一个整数 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
  • 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

题目三：高精度计数

题目背景

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

题目描述

给定一个整数 n（ 1 ≤ n ≤ 1 0 9 1 \leq n \leq 10^9 1≤n≤109），你需要统计数字 k 在上述数字序列中出现的次数。

输入格式

一行两个整数 n 和 k，表示要统计的数字和目标数字。

输出格式

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

示例输入
15 1

  • 1
示例输出
8

  • 1
提示

在序列中，数字 1 出现了 8 次（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;
}

  • 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

总结：

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

  • 高精度算法通常基于字符串实现，每个数字的每一位都用字符串中的一个字符表示。
  • 在高精度加法和减法中，需要处理进位和借位。
  • 高精度乘法采用类似手工乘法的逐位相乘和进位相加的方式。
  • 高精度除法模拟手工长除法的过程，逐位相除，得到商和余数。

10.排序

常见的排序算法

根据时间复杂度的不同，常见的算法可以分为3大类。

1.O(n²) 的排序算法

  • 冒泡排序

  • 选择排序

  • 插入排序

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

  • 希尔排序

  • 归并排序

  • 快速排序

  • 堆排序

3.线性的排序算法

  • 计数排序

  • 桶排序

  • 基数排序

各种排序的具体信息

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort） 是一种基础的 交换排序。

冒泡排序之所以叫冒泡排序，是因为它每一种元素都像小气泡一样根据自身大小一点一点往数组的一侧移动。

算法步骤如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个；

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

  3. 针对所有的元素重复以上的步骤，除了最后一个；

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

图示如下：

代码如下：

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]); //不满足偏序，交换
            }
        }
    }
}


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

还有一种假的写法就是保证第一个最小，第二个次小，比较的是 i 和 j ，虽然也是对的，有点像选择排序，但也不是。其不是冒泡排序

选择排序（Selection Sort）

选择排序（Selection sort） 是一种简单直观的排序算法。

选择排序的主要优点与数据移动有关。

如果某个元素位于正确的最终位置上，则它不会被移动。

选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n - 1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序的算法步骤如下：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

  2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

  3. 以此类推，直到所有元素均排序完毕。

图示如下：

代码如下：

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]);
    }
}


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

插入排序（Insertion Sort）

插入排序（Insertion sort） 是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的算法步骤如下：

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

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

  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

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

  6. 重复步骤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;
    }
}

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

希尔排序（Shell Sort）

希尔排序，也称 递减增量排序算法，是 插入排序 的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

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

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

步长的选择是希尔排序的重要部分。

只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。

然后会继续以一定步长进行排序，最终算法以步长为1进行排序。

当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

希尔排序的算法步骤如下：

  1. 定义一个用来分割的步长；

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

  3. 不断重复上述步骤。

图示如下：

代码如下：

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; //恢复被替换的值
            }
        }
    }
}
}

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

快速排序（Quick Sort）

快速排序（Quicksort），又称 划分交换排序（partition-exchange sort） 。

快速排序（Quicksort） 在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序 O(n log n) 通常明显比其他算法更快，因为它的 内部循环（inner loop） 可以在大部分的架构上很有效率地达成。

快速排序使用 分治法（Divide and conquer） 策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

快速排序的算法步骤如下：

  1. 挑选基准值：从数列中挑出一个元素，称为 “基准”（pivot） ；

  2. 分割：重新排序序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；

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

递归到最底部的判断条件是序列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

图示如下：

代码如下：

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);
}

  • 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

归并排序（Merge Sort）

归并排序（Merge sort） ，是创建在归并操作上的一种有效的排序算法，时间复杂度为 O(n log n) 。1945年由约翰·冯·诺伊曼首次提出。该算法是采用 分治法（Divide and Conquer） 的一个非常典型的应用，且各层分治递归可以同时进行。

其实说白了就是将两个已经排序的序列合并成一个序列的操作。

并归排序有两种实现方式

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

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

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

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

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

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。


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);
}

  • 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

迭代比起递归还是安全很多，太深的递归容易导致堆栈溢出。所以建议可以试下迭代实现，acm里是够用了

堆排序（Heap Sort）

堆排序（Heapsort） 是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆是一个近似 完全二叉树 的结构，并同时满足 堆积的性质 ：即子节点的键值或索引总是小于（或者大于）它的父节点。

二叉堆是什么？

二叉堆分以下两个类型：

1.最大堆：最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

  • 图示如下：

  • 数组表示如下：

    [10, 8, 9, 7, 5, 4, 6, 3, 2]

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

  • 图示如下：

  • 数组表示如下：

    [1, 3, 2, 6, 5, 7, 8, 9, 10]

堆排序的算法步骤如下：

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

  2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

代码如下：

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.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆

    for (int i = len - 1; i > 0; i--)
    {
        swap(a[0], a[i]);
        adjustHeap(a, 0, i);
    }
}


  • 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

我这里用了递归写法，非递归也很简单，就是比较哪个叶子节点大，再继续for下去

计数排序（Counting Sort）

计数排序（Counting sort） 是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组来存储输入的元素，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k) 。计数排序不是比较排序，排序的速度快于任何比较排序算法。

计数排序的算法步骤如下：

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

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

  3. 对所有的计数累加（从数组 C 中的第一个元素开始，每一项和前一项相加）；

  4. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去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++;
    }
}


  • 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

桶排序（Bucket Sort）

桶排序（Bucket Sort） 跟 计数排序（Counting sort） 一样是一种稳定的线性时间排序算法，不过这次需要的辅助不是计数，而是桶。

工作的原理是将数列分到有限数量的桶里。每个桶再个别排序。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)。

桶排序的算法步骤如下：

  1. 设置一个定量的数组当作空桶子；

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

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

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

代码如下：

我觉得递归调用桶排序比较慢，这里直接用了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]);
    }
}


  • 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

基数排序（Radix Sort）

基数排序（Radix sort） 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

工作原理是将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用 LSD（Least significant digital） 或 MSD（Most significant digital） 。

LSD 的排序方式由键值的 最右边（最小位） 开始，而 MSD 则相反，由键值的 最左边（最大位） 开始。

MSD 方式适用于位数多的序列，LSD 方式适用于位数少的序列。

基数排序 、 桶排序 、 计数排序 原理都差不多，都借助了 “桶” 的概念，但是使用方式有明显的差异，其差异如下：

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

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

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

LSD 图示如下：

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();
        }
    }
}


  • 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

术语铺垫

稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

非原地排序：需要利用额外的数组来辅助排序。

时间复杂度：一个算法执行所消耗的时间。

空间复杂度：运行完一个算法所需的内存大小。

未完待续，下一章：排序

请点赞收藏，这是我创作的动力。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/920651
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号