4、算法
4.1 算法概念与描述
4.1.1 算法的概述
算法指的是解决特定问题的步骤和方法。在计算机科学中，算法通常指的是用于解决问题的可执行指令的集合。算法可以被视为计算中的一个过程，其输入是一个值或一组值，输出是解决问题的解决方案。
算法在计算机科学中是非常重要的，因为它们是在计算机上实现各种应用程序的基础。算法可以被设计为在不同的场景下进行优化，例如在处理大量数据时，或在计算时间或内存使用方面进行优化。
算法的设计可以分为几个阶段，包括问题定义、算法设计、算法实现和算法分析。在问题定义阶段，确定要解决的问题和约束条件。在算法设计阶段，需要考虑可行的解决方案，并选择最合适的算法。在算法实现阶段，将算法转换为代码。在算法分析阶段，需要评估算法的性能和正确性。
算法具有以下特点：
有穷性：一个算法必须在执行有限步之后结束。
确定性：算法中每个步骤都必须明确而无歧义。
可行性：算法中每个步骤都必须能够实现，且时间、空间复杂度必须可行。
输入：算法有也可以没有输入。
输出：算法必须有输出。
独立性：算法必须独立于任何编程语言、计算机硬件或操作系统等环境，即其应用不受具体实现的限制。
优美性：算法应该是简单、易懂、优美和高效的。
4.1.2 算法的描述
算法描述是将一个算法的实现方法用人类能够理解的语言进行描述，以便程序员能够根据描述实现出具体的算法。常见的算法描述方式有自然语言描述、流程图描述和伪代码描述。
自然语言描述：使用日常生活中的语言进行描述，可以使读者通过简单的阅读和理解，掌握算法的基本思想和实现方法。
流程图描述：使用图形符号表示算法的各个步骤和流程，通常是通过连接各种符号来描述算法的具体过程。流程图便于对算法进行可视化的描述，更容易理解算法的执行过程。
伪代码描述：使用近似于编程语言的形式描述算法，伪代码描述可以简洁、准确地表示算法的过程，具有通用性和易读性，不会受限于任何特定的编程语言。同时，伪代码描述可以被方便地转化为实际的程序代码实现，因此也是算法描述中比较常用的一种方式。
4.2 入门算法
4.2.1 枚举法
枚举法（Enumeration）是一种暴力求解问题的方法，也叫暴力搜索（Brute Force）。它的基本思想是：穷举所有可能的情况，找出符合条件的解。
枚举法的优点是思路简单、易于理解和实现，适用于解决小规模的问题。但它的缺点也很明显，由于它需要穷举所有可能的情况，所以在数据量较大时，运行时间很容易超时。
以下是一个枚举法的例子，用于求解一个数列中的最大值：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14 #include <iostream>
using namespace std ;
int main () {
int a [ 5 ] = { 1 , 5 , 3 , 2 , 4 };
int max_value = a [ 0 ]; // 假设第一个数为最大值
for ( int i = 1 ; i < 5 ; i ++ ) {
if ( a [ i ] > max_value ) { // 如果当前数比最大值还大，更新最大值
max_value = a [ i ];
}
}
cout << "The maximum value is " << max_value << endl ;
return 0 ;
}
在这个例子中，我们首先假设第一个数为最大值，然后从第二个数开始遍历数列，如果遍历到的数比当前的最大值还大，就将最大值更新为该数。最后输出最大值即可。
这是一个典型的枚举法例子，它的时间复杂度为O(n)，因为需要遍历整个数列。当然，对于更复杂的问题，枚举法的时间复杂度也可能会更高。
4.2.2 模拟法
模拟法是一种常见的算法思想，它是指通过模拟某些实际过程的方法来解决问题。在计算机编程中，我们通常使用循环结构来实现模拟算法。具体来说，我们可以通过设置计数器、变量、数组等来模拟实际过程中的某些状态，然后通过循环结构来控制状态的改变，最终达到解决问题的目的。
模拟法通常适用于一些问题的求解，这些问题的解法通常需要对某些状态进行模拟，以便得到最终结果。例如，某些游戏的操作就可以通过模拟玩家操作的过程来实现。另外，一些物理学、化学等科学领域的问题也可以使用模拟法求解，例如分子动力学模拟等。
在C++编程中，我们可以通过循环语句（如for、while等）和条件语句（如if、switch等）来实现模拟算法。下面是一个简单的例子，它通过模拟掷骰子的过程来统计掷出某个点数的概率：
C++ 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 #include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std ;
int main ()
{
const int n = 6 ; // 骰子的面数
const int N = 10000 ; // 总共掷骰子的次数
int count [ n + 1 ] = { 0 }; // 统计掷出每个点数的次数
// 初始化随机数种子
srand ( time ( NULL ));
// 模拟掷骰子过程
for ( int i = 0 ; i < N ; i ++ )
{
int num = rand () % n + 1 ; // 随机生成一个点数
count [ num ] ++ ; // 统计次数
}
// 输出每个点数的出现概率
for ( int i = 1 ; i <= n ; i ++ )
{
cout << "点数" << i << "出现的概率：" << double ( count [ i ]) / N << endl ;
}
return 0 ;
}
在上面的代码中，我们通过循环结构来模拟了掷骰子的过程，然后使用数组来统计每个点数掷出的次数，最后输出了每个点数的出现概率。这是一个简单的模拟算法的例子。
4.3 基础算法
C++ 的基础算法包括许多经典的算法和数据结构，比如排序、查找、递归、回溯、动态规划等。下面对一些常见的基础算法进行简单介绍。
1.排序算法
排序是计算机科学中最基本的操作之一。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。这些算法的时间复杂度和稳定性各不相同，可以根据具体的应用场景选择不同的算法。
2.查找算法
查找算法用于在一个数据集合中查找特定的元素。常见的查找算法有顺序查找、二分查找、哈希查找等。其中，二分查找算法只能在已排序的数据集合中使用。
3.递归算法
递归算法是指一个函数调用自身的过程。递归算法通常涉及到一个基本条件和一个递归条件。在实现递归算法时，需要注意控制递归深度和避免重复计算。
4.回溯算法
回溯算法是一种穷举算法，常用于解决组合优化问题。回溯算法会逐步构建一个可能的解，并在每一步中验证这个解是否合法。如果发现当前解无法继续，回溯算法会返回上一步，尝试其他可能的解。
5.动态规划算法
动态规划算法是一种用于解决多阶段决策问题的算法。动态规划算法通过将原问题分解成子问题，并记录每个子问题的最优解，从而避免重复计算。动态规划算法通常涉及到一个递推公式和一个边界条件。
6.贪心算法
贪心算法是一种每步都选择当前状态下最优解的算法。贪心算法通常涉及到一个贪心策略和一个最优子结构。贪心算法具有简单、高效的特点，但不能保证每次选择的最优解一定能导致全局最优解。
4.3.1 贪心法
贪心算法是指，在对问题进行求解时，在每一步选择中都采取当前状态下最优的选择，从而希望最终得到全局最优的解。贪心算法具有简单、高效、易于实现的特点，可以用来求解一些最优化问题。
贪心算法的基本思想是贪心策略，即按照某种规则或策略去选择当前看起来最优的决策，然后直接得到局部最优解。在贪心算法中，我们不考虑可能出现的后效性问题，即当做某个决策后，后面的所有决策都不会受到当前决策的影响。
贪心算法的实现过程通常包括以下几个步骤：
确定问题的最优解的性质，即问题需要满足贪心选择性质和无后效性质；
将问题分解成若干个子问题，每个子问题都有一个局部最优解；
定义一个全局最优解的解空间，然后逐步扩大解空间，直到问题的全局最优解产生；
根据贪心策略，选择当前最优的决策，并更新解空间和局部最优解。
下面是一些常见的贪心算法应用：
活动安排问题（贪心选择活动结束时间最早的）；
最小生成树问题（Kruskal算法和Prim算法）；
最短路径问题（Dijkstra算法和贝尔-福德-摩尔曼算法）；
背包问题（分数背包问题和0/1背包问题）；
区间调度问题（贪心选择结束时间最早的活动）；
数组拆分问题（贪心选择相邻元素之和最小的区间拆分方案）；
数组划分问题（贪心选择中位数）；
最大子序和问题（贪心选择当前最大和）。
在使用贪心算法求解问题时，需要注意以下问题：
判断问题是否具有贪心选择性质和无后效性质，只有满足这两个性质的问题才能使用贪心算法求解；
对于涉及到排序的贪心算法问题，需要选择合适的排序算法，并对排序算法进行适当的改造；
对于贪心策略的选择，需要结合具体问题的特点，选择适当的贪心策略，避免贪心策略的局部最优解与全局最优解不一致。
以下是贪心算法在几个常见问题中的应用示例及相应的C++代码：
1.找零钱问题
问题描述：给定若干面额不同的硬币，以及一个需要找零的金额，如何使找回的硬币数量最少？
贪心策略：每次找最大面值的硬币。
C++代码：
C++ int coins [ 4 ] = { 25 , 10 , 5 , 1 }; // 硬币面额，从大到小排列
int findMinCoins ( int amount ) {
int num = 0 ; // 硬币数量
for ( int i = 0 ; i < 4 && amount > 0 ; i ++ ) {
num += amount / coins [ i ]; // 取尽可能多的 coins[i]
amount %= coins [ i ]; // 更新剩余金额
}
return num ;
}
2.区间选点问题
问题描述：给定多个区间，从每个区间中选一个点，使得所有选出的点组成的集合不相交，如何选出最多的点？
贪心策略：每次选择右端点最小的区间，并且不与已选的点重合。
C++代码：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 struct Interval {
int start , end ;
};
bool cmp ( const Interval & a , const Interval & b ) {
return a . end < b . end ; // 按右端点升序排序
}
int selectPoints ( vector < Interval > & intervals ) {
sort ( intervals . begin (), intervals . end (), cmp );
int num = 0 , cur = -1 ;
for ( int i = 0 ; i < intervals . size (); i ++ ) {
if ( intervals [ i ]. start > cur ) { // 如果与已选点不重合
num ++ ; // 选择该区间的右端点
cur = intervals [ i ]. end ;
}
}
return num ;
}
3.分糖果问题
问题描述：给定若干个孩子和若干个糖果，每个孩子有一个贪心值，每个糖果有一个大小，需要将糖果分给孩子，使得满足以下条件：每个孩子最多只能拥有一个糖果；且对于任意两个孩子i和j，如果i的贪心值大于j，则i获得的糖果的大小也必须大于j获得的糖果的大小。
贪心策略：将孩子按照贪心值升序排序，将糖果按照大小升序排序，然后将糖果分给贪心值最小的孩子，直到找不到满足条件的糖果为止。
C++ 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 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
int main ()
{
// 输入糖果数量和小朋友数量
int n , m ;
cin >> n >> m ;
// 输入每个小朋友的贪心指数和可分配糖果数
vector < int > greed ( m ), candy ( n );
for ( int i = 0 ; i < m ; i ++ )
cin >> greed [ i ];
for ( int i = 0 ; i < n ; i ++ )
cin >> candy [ i ];
// 对小朋友和糖果按照贪心指数和大小排序
sort ( greed . begin (), greed . end ());
sort ( candy . begin (), candy . end ());
// 分配糖果
int i = 0 , j = 0 , count = 0 ;
while ( i < m && j < n )
{
if ( greed [ i ] <= candy [ j ]) // 糖果足够分配
{
i ++ ;
j ++ ;
count ++ ;
}
else // 糖果不足，找下一个小朋友
i ++ ;
}
// 输出最多能满足多少个小朋友
cout << count << endl ;
return 0 ;
}
4.活动安排问题
活动安排问题，即给定一些活动，每个活动有一个开始时间和结束时间，如何安排这些活动，使得尽可能多的活动能够被安排在同一时间段内。
具体算法描述如下：
将所有活动按照结束时间从早到晚排序；
选择第一个活动，并记录它的结束时间作为当前时间；
遍历剩下的活动，如果当前活动的开始时间晚于或等于当前时间，则选择该活动，并将当前时间更新为该活动的结束时间；
重复步骤3，直到遍历结束。
下面是相应的C++代码实现：
C++ 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 #include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
// 定义活动结构体
struct Activity {
int start ;
int end ;
Activity ( int s , int e ) : start ( s ), end ( e ) {}
};
// 按照结束时间从早到晚排序
bool cmp ( const Activity & a , const Activity & b ) {
return a . end < b . end ;
}
// 活动安排函数
int activityArrange ( vector < Activity >& activities ) {
// 按照结束时间排序
sort ( activities . begin (), activities . end (), cmp );
// 记录当前时间和计数器
int curTime = 0 , count = 0 ;
// 遍历所有活动
for ( int i = 0 ; i < activities . size (); i ++ ) {
// 如果当前活动的开始时间晚于或等于当前时间，则选择该活动
if ( activities [ i ]. start >= curTime ) {
count ++ ;
curTime = activities [ i ]. end ;
}
}
return count ;
}
int main () {
// 测试样例
vector < Activity > activities = { Activity ( 1 , 4 ), Activity ( 3 , 5 ), Activity ( 0 , 6 ),
Activity ( 5 , 7 ), Activity ( 3 , 8 ), Activity ( 5 , 9 ),
Activity ( 6 , 10 ), Activity ( 8 , 11 ), Activity ( 8 , 12 ),
Activity ( 2 , 13 ), Activity ( 12 , 14 ) };
cout << activityArrange ( activities ) << endl ; // 输出最多能够安排的活动数
return 0 ;
}
输出结果为 4，表示最多能够安排的活动数为 4。
4.3.2 递推法
递推法，又称为迭代法，是一种通过已知初始条件和递推关系式来求解问题的方法。递推法可以用于各种计算问题，包括数学、物理、计算机科学等领域。在计算机科学中，递推法常用于计算斐波那契数列、动态规划等问题。
递推法的基本思想是，根据已知的初始条件，通过一个递推关系式来求解后续的结果。通常情况下，递推关系式都是一个通式或者一个递推公式，它能够将当前的结果与前面的结果联系起来，从而得到新的结果。
下面是一个求斐波那契数列的递推法实现的示例代码：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 #include <iostream>
using namespace std ;
int main () {
int n ;
cout << "Enter n: " ;
cin >> n ;
int f0 = 0 , f1 = 1 , fn ;
if ( n == 0 ) {
fn = f0 ;
} else if ( n == 1 ) {
fn = f1 ;
} else {
for ( int i = 2 ; i <= n ; i ++ ) {
fn = f0 + f1 ;
f0 = f1 ;
f1 = fn ;
}
}
cout << "Fibonacci(" << n << ") = " << fn << endl ;
return 0 ;
}
这段代码通过一个 for 循环来计算斐波那契数列的第 n 项。其中，f0 和 f1 分别表示斐波那契数列的前两项，fn 表示当前项。在循环中，每次计算出 fn 后，将 f1 赋值给 f0，将 fn 赋值给 f1，继续计算下一项。当 n = 0 或 n = 1 时，直接返回 f0 或 f1 即可。
4.3.3 递归法
递归是指一个函数在调用自身的过程中，能够将大问题分解为小问题的解决方法。递归包含两个基本要素：
递归边界条件：递归结束的条件，也称为递归终止条件。当问题变得足够小，可以直接解决时，递归就不再进行，达到终止条件。
递归式：递归函数在处理问题时，将问题转化为更小规模的同类问题。递归式中包含递归调用，即调用自身解决同类问题。
递归算法的实现需要注意以下几点：
确定递归边界条件。
缩小问题规模，调用自身来解决更小规模的问题。
递归过程中的每一次调用都会产生一些变量，这些变量在递归结束后需要及时清理。
递归算法可能存在栈溢出的问题，因此需要注意递归深度过大的情况。
下面是一个简单的递归算法示例，用于求阶乘：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 #include <iostream>
using namespace std ;
int factorial ( int n ) {
if ( n == 1 ) { // 递归终止条件
return 1 ;
}
else {
return n * factorial ( n - 1 ); // 递归调用
}
}
int main () {
int n = 5 ;
cout << "The factorial of " << n << " is " << factorial ( n ) << endl ;
return 0 ;
}
输出结果：
Text Only The factorial of 5 is 120
该程序通过递归调用实现了求阶乘的功能，当n等于1时，递归结束，返回1。否则，函数调用自身，参数n减1，继续求解n的阶乘，直到n等于1。
4.3.4 二分法
二分法是一种常见的搜索算法，常用于在有序数组中查找特定元素。其思想是将查找范围逐步缩小，将中间位置的元素与目标元素进行比较，进一步缩小查找范围，直到找到目标元素或者确定不存在目标元素为止。
以下是二分法的基本步骤：
初始化左右边界 left 和 right，分别为数组的起始和结束位置；
计算中间位置 mid，并将中间位置的元素与目标元素进行比较；
如果中间位置元素等于目标元素，则返回该位置；
如果中间位置元素大于目标元素，则目标元素只可能存在于左半部分，将右边界设为中间位置减一，继续二分查找；
如果中间位置元素小于目标元素，则目标元素只可能存在于右半部分，将左边界设为中间位置加一，继续二分查找；
如果最终仍然未找到目标元素，则返回不存在。
以下是二分法的C++代码示例：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14 int binarySearch ( int arr [], int n , int target ) {
int left = 0 , right = n - 1 ;
while ( left <= right ) {
int mid = left + ( right - left ) / 2 ;
if ( arr [ mid ] == target ) {
return mid ;
} else if ( arr [ mid ] < target ) {
left = mid + 1 ;
} else {
right = mid - 1 ;
}
}
return -1 ;
}
上述代码中，arr 表示有序数组，n 表示数组的长度，target 表示要查找的目标元素。在每一轮循环中，计算中间位置 mid，并将中间位置的元素与目标元素进行比较，根据比较结果缩小查找范围。如果最终未找到目标元素，则返回 -1。
4.3.5 倍增法
倍增法（Binary Lifting）是一种常用于解决树上最近公共祖先（LCA）等问题的算法。它通过预处理和二进制分解的方式，将原问题转化为多个较小的子问题，从而大幅降低时间复杂度。
具体来说，倍增法是基于以下两个思路：
1.预处理出每个节点向上跳 \(2^k\) 步所能到达的节点。这样，任意两个节点之间的距离就可以表示为若干个 \(2^k\) 的和。
2.在查询时，将两个节点先向上跳到同一深度，再不断向上跳 \(2^k\) 步，直到它们的父节点相同为止。
通过这两个步骤，我们就可以在 \(O(n\log n)\) 的时间内预处理出所有节点向上跳 \(2^k\) 步所能到达的节点，以及在 \(O(\log n)\) 的时间内求出任意两个节点之间的距离或 LCA 等问题。
下面是一个求 LCA 的例子，假设有一棵以 1 为根的二叉树：
Text Only 1
/ \
2 3
/ \ / \
4 5 6 7
那么我们可以预处理出每个节点向上跳 \(2^k\) 步所能到达的节点：
Text Only k=0: 1 2 3 4 5 6 7
k=1: 1 1 2 2 3 3 3
k=2: 1 1 1 1 2 2 2
k=3: 1 1 1 1 1 1 1
这样，在查询节点 4 和节点 6 的 LCA 时，我们先将节点 4 向上跳到深度 3，节点 6 向上跳到深度 3，然后将它们不断向上跳 \(2^k\) 步，直到它们的父节点相同为止，即：
Text Only 4 -> 2 -> 1 -> 1
6 -> 3 -> 1 -> 1
因此，节点 4 和节点 6 的 LCA 是节点 1。
下面是一个基于倍增法求 LCA 的 C++ 代码：
C++ 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
51
52
53
54
55
56
57
58
59
60
61
62 #include <bits/stdc++.h>
using namespace std ;
const int N = 100010 , M = 2 * N ;
int h [ N ], e [ M ], ne [ M ], idx ;
int depth [ N ], fa [ N ][ 17 ];
int n , m ;
void add ( int a , int b )
{
e [ idx ] = b , ne [ idx ] = h [ a ], h [ a ] = idx ++ ;
}
void dfs ( int u , int father )
{
depth [ u ] = depth [ father ] + 1 ;
fa [ u ][ 0 ] = father ;
for ( int i = 1 ; i <= 16 ; i ++ )
fa [ u ][ i ] = fa [ fa [ u ][ i - 1 ]][ i - 1 ];
for ( int i = h [ u ]; ~ i ; i = ne [ i ])
{
int j = e [ i ];
if ( j != father ) dfs ( j , u );
}
}
int lca ( int a , int b )
{
if ( depth [ a ] < depth [ b ]) swap ( a , b );
for ( int i = 16 ; i >= 0 ; i -- )
if ( depth [ fa [ a ][ i ]] >= depth [ b ])
a = fa [ a ][ i ];
if ( a == b ) return a ;
for ( int i = 16 ; i >= 0 ; i -- )
if ( fa [ a ][ i ] != fa [ b ][ i ])
{
a = fa [ a ][ i ];
b = fa [ b ][ i ];
}
return fa [ a ][ 0 ];
}
int main ()
{
memset ( h , -1 , sizeof h );
scanf ( "%d%d" , & n , & m );
for ( int i = 1 ; i < n ; i ++ )
{
int a , b ;
scanf ( "%d%d" , & a , & b );
add ( a , b ), add ( b , a );
}
dfs ( 1 , 0 );
while ( m -- )
{
int a , b ;
scanf ( "%d%d" , & a , & b );
printf ( "%d \n " , lca ( a , b ));
}
return 0 ;
}
该代码中，我们使用深度优先搜索（DFS）预处理出每个节点的深度和其在倍增数组中的祖先节点。其中，深度优先搜索用于在遍历每个节点时计算其深度和预处理其祖先节点。在求解LCA时，我们使用倍增法的思想，在预处理后的倍增数组中查询每个节点的祖先节点，从而求出它们的最近公共祖先。
4.4 数值处理算法
4.4.1 高精度的加法
高精度加法算法是指能够计算两个超过普通计算机数据类型表示范围的大数之和的一种算法。其实现的基本思路是：将大数拆分为多个数位，然后从低位到高位逐位进行计算，同时维护进位信息。具体算法流程如下：
将两个大数从低位到高位逐位相加，同时记录进位信息。
如果两个大数的数位不同，则在计算数位较短的那个数时，需要用 0 补齐相应的位数。
当计算完所有数位后，如果最高位有进位，需要将进位加到结果中。
将计算结果反转，得到最终的结果。
值得注意的是，在实现中需要考虑进位的情况。一般来说，进位可以通过对 10 取模得到，进位数则是除以 10 的商。
另外，在实际应用中，高精度加法算法还需要考虑一些特殊情况，如负数、浮点数等。
以下是C++实现高精度加法的示例代码：
C++ 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 string myAdd ( string a , string b ) //高精度加法
{
int n = max ( a . size (), b . size ()) + 1 ;
vector < int > ans ( n , 0 ); //开辟一个足够存储结果的数组，结果的位数最多为 位数最多的那个数的位数加一(考虑进位)
int i = a . size () -1 , j = b . size () -1 , k = n -1 ; //从个位开始通过模拟竖式进行大数加法
while ( i >= 0 && j >= 0 ) //当两数均未加完时
{
ans [ k -- ] = ( a [ i -- ] - '0' ) + ( b [ j -- ] - '0' ); //我们让我们的数组存储每一位相加的结果注意将字符串转为整型数字
}
//检测是否有某个数的高位未加完将其直接存入数组中
while ( j >= 0 )
{
ans [ k -- ] = ( b [ j -- ] - '0' );
}
while ( i >= 0 )
{
ans [ k -- ] = ( a [ i -- ] - '0' );
}
string c = "" ; //创建一个字符串去存储答案
for ( int i = n -1 ; i > 0 ; i -- ) //因为之前的竖式加每一位都没考虑进位所以我们从最后开始检查进位
{ //因为是加法如果有进位最多也就进一
if ( ans [ i ] >= 10 ) //如果大于10说明应该进位那么我们让此位减10它的高一位加1
{
ans [ i ] -= 10 ;
ans [ i -1 ] ++ ;
}
c . insert ( 0 , 1 , ans [ i ] + '0' ); //处理后的结果转化为字符插入结果字符的首位
}
if ( ans [ 0 ] > 0 ) //检查最最高位是否大于0如果两数相加没有进位那么这一位就是0我们就不必存储它否则则放入字符串
{
c . insert ( 0 , 1 , ans [ 0 ] + '0' );
}
return c ; //返回答案
}
4.4.2 高精度的减法
高精度的减法是指对于大数进行减法计算，常见于一些需要精确计算的场合，例如大数相减、高精度浮点数计算等。其基本思路与高精度加法类似，主要是按位进行减法运算，并且需要考虑借位和进位的情况。
具体算法步骤如下：
比较两个数的大小，如果被减数小于减数，则需要将两个数交换，确保被减数大于等于减数。
对于两个数的每一位进行逐位相减，从个位开始依次向高位计算。
如果被减数的该位数值小于减数的该位数值，则需要借位，将高一位减1。
如果被减数的该位数值大于等于减数的该位数值，则直接计算该位的差值。
如果被减数的最高位出现了借位，则需要将结果变为负数，并在最高位加上一个负号。
最后去掉高位多余的0，得到减法的结果。
下面是高精度减法的C++代码实现，以字符串的形式输入和输出：
C++ 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 string mySubtract ( string a , string b ) //高精度减法(整体思想同加法)
{
string c = "" ; //创建一个字符串去存储答案
if ( myCompare ( a , b ) == 0 ) //先比较一下两数大小如果相等我们直接返回0即可
return "0" ;
if ( myCompare ( a , b ) == -1 ) //如果a<b那么我们交换两数的值同时在答案字符串中先放入一个负号
{
swap ( a , b );
c . push_back ( '-' );
}
int n = a . size ();
//开辟一个足够存储结果的数组 减法结果的位数最多为位数最多的那个数的位数我们保证了a为的大数所以就是a的位数
vector < int > ans ( n , 0 );
int i = a . size () -1 , j = b . size () -1 , k = n -1 ; //从个位开始模拟竖式减法
int t = 0 ; //表示低位的借位情况 0:无借位 1:有借位
while ( i >= 0 ) //同加法一样模拟运算我们知道a是大数所以a遍历完竖式才完成
{
char nowb ; //被减数当前位有数就正常减 没有数说明就是0
if ( j >= 0 ) nowb = b [ j ];
else nowb = '0' ;
ans [ k ] = a [ i ] - nowb - t ; //对应位相减同时减去低位的借位
if ( ans [ k ] < 0 ) //如果结果小于0 则向高位借一位
{
t = 1 ;
ans [ k ] += 10 ;
}
else t = 0 ; //否则向高位无借位
k -- , i -- , j -- ; //继续判断高一位
}
bool flag = true ; //这里与加法不同高位可能出现多个零开头的情况我们需要找到第一不是零的地方再存数
for ( int i = 0 ; i < n ; i ++ )
{
if ( flag && ans [ i ] == 0 ) //如果当前数为0且未存数则不执行存数操作
continue ;
flag = false ; //一旦存入数更改标志位
c . push_back ( ans [ i ] + '0' );
}
return c ; //返回结果
}
4.4.3 高精度的乘法
高精度乘法是指在计算两个数相乘时，对每一位上的数值都进行计算，得出最终结果。由于计算机的内存有限，一般不能用基本数据类型来存储大数，需要使用高精度的方法。
高精度乘法的实现基本思路与手算乘法相似，可以分为以下几个步骤：
将两个数分别逆序存储到两个数组中（如将1234存储为{4, 3, 2, 1}）。
对于乘数的每一位，分别与被乘数的每一位相乘，并将结果存储到对应的位置上。
处理进位问题：对于每一位的结果，将其余10取模得到该位的值，同时将余数进位。
处理前导0：将结果数组的前导0去掉，得到最终的结果。
具体的实现方式可以根据具体的需求进行调整，例如可以在第三步中对余数进行累加，减少对数组的遍历次数，从而提高运行效率。
高精度乘法的时间复杂度为O(n2 )，其中n为数的位数。
C++ 代码示例：
C++ 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 string myMultiply ( string a , string b ) //高精度乘法
{
if ( a == "0" || b == "0" ) //其中有一个为0时直接返回0
return "0" ;
vector < int > ans ; //开辟一个足够存储结果的数组
int n = a . size (), m = b . size ();
ans . resize ( n + m , 0 ); //乘法结果的位数最多为两数的位数之和
for ( int i = 0 ; i < n ; i ++ ) //这里从高位开始和从低位开始无所谓我们将两数相乘的结果不考虑放到对应位上最后去检测进位即可
{ //例如个位乘百位的结果 以及十位乘十位的结果 都放到百位上
for ( int j = 0 ; j < m ; j ++ )
{
ans [ i + j + 1 ] += ( a [ i ] - '0' ) * ( b [ j ] - '0' );
}
}
for ( int i = n + m -1 ; i > 0 ; i -- ) //我们从低位开始检查进位
{
if ( ans [ i ] >= 10 ) //如果大于10说明有进位但乘法的进位不一定只进1
{
ans [ i -1 ] += ( ans [ i ] / 10 ); //高位加地位的高于个位部分
ans [ i ] %= 10 ; //低位对十求余
}
}
string c = "" ; //创建字符串存储答案
bool flag = true ; //同减法一样找到第一个不是0的位置开始存数
for ( int t = 0 ; t < n + m ; t ++ )
{
if ( flag && ans [ t ] == 0 )
continue ;
flag = false ;
c . push_back ( ans [ t ] + '0' );
}
return c ; //返回答案
}
在这个实现中，我们使用 string 类型来存储高精度数。具体实现方法与前面的数组实现类似，只是使用了 string 的字符操作来实现加法和乘法。在乘法中，我们使用两重循环来逐位相乘，并将结果加入结果字符串的相应位置。由于乘法结果可能超过一个字符，我们需要使用进位来进行处理。最后，我们还需要去掉结果字符串前面多余的 0。
4.4.4 高精度的除法
高精度除法是指两个高精度整数相除的运算，相较于普通整数除法，高精度除法需要考虑更多的细节，如进位、除数为零等情况。以下是高精度除法的算法介绍：
首先判断除数是否为零，若为零则返回错误。
确定商的位数和被除数的最高位数，初始化商为0，余数为被除数。
从被除数的最高位开始，将余数不断左移一位，直到它的位数大于等于除数的位数。
用余数减去除数的最高位所表示的数，若差小于零，则商对应的位为0，否则为1，并将余数更新为差。
将余数和除数一起右移一位，直到余数的位数小于被除数的位数，返回第3步。
完成上述步骤后，商就是答案。如果除数是负数，则商也是负数，否则为正数。
以下是高精度除法的C++代码实现，假设高精度整数已经用string类型表示：
C++ 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 //高精度除以低精度
#include <iostream>
#include <string>
#include <algorithm>
using namespace std ;
string div ( string a , int b ) {
string ans ;
int remainder = 0 ; // 存储余数
for ( int i = 0 ; i < a . size (); i ++ ) {
int temp = ( a [ i ] - '0' ) + remainder * 10 ; // 余数乘以10加上当前位
ans += ( temp / b ) + '0' ; // 相除得到当前位的商，转化为字符后加入答案
remainder = temp % b ; // 更新余数
}
// 如果最后余数为0，则直接返回结果，否则将余数作为最终结果的小数部分
if ( ans . size () == 1 && ans [ 0 ] == '0' ) {
ans = "0" ;
} else if ( remainder != 0 ) {
ans += "." ;
for ( int i = 1 ; i <= 2 ; i ++ ) { // 取小数点后两位
remainder *= 10 ;
ans += ( remainder / b ) + '0' ;
remainder %= b ;
}
}
return ans ;
}
int main () {
string a ;
int b ;
cin >> a >> b ;
string ans = div ( a , b );
cout << ans << endl ;
return 0 ;
}
该算法的时间复杂度为\(O(n)\) ，其中\(n\) 为被除数的位数。
以下是高精度除以高精度的代码实现：
C++ 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 vector < string > myDivide ( string a , string b ) //高精度除法
{
vector < string > ans ( 2 , "0" ); //先创建两个字符串空间去存储答案一个存商一个存余数
if ( myCompare ( a , b ) == -1 ) //如果被除数比除数小商为0余数为a返回答案即可
{
ans [ 1 ] = a ;
return ans ;
}
else if ( myCompare ( a , b ) == 0 ) //如果被除数与除数相等商为1余数为0返回答案即可
{
ans [ 0 ] = "1" ;
return ans ;
}
else //否则我们需要模拟除法的竖式来进行计算
{
string res = "" ; //创建存储商的字符串
int m1 = a . size (), m2 = b . size ();
string a1 = a . substr ( 0 , m2 -1 );
for ( int i = m2 -1 ; i < m1 ; i ++ ) //模拟竖式从高位开始依次取数减去除数能减几个该位商的当前位就是几
{
if ( a1 == "0" ) //如果a1为0为了防止a1出现0开头的情况我们将它清空
a1 = "" ;
a1 . push_back ( a [ i ]); //我们从被除数中取一个数放入a1继续减
int e = 0 ;
while ( myCompare ( a1 , b ) >= 0 ) //当a1大于等于除数时便一直减同时e累加
{
e ++ ;
a1 = mySubtract ( a1 , b );
}
if ( res . size () || e ) //如果res不为空或者e不为0我们存储他
res . push_back ( e + '0' );
}
ans [ 0 ] = res ; //最后res就是商
ans [ 1 ] = a1 ; //a1就是余数
return ans ; //返回答案
}
}
4.4.5 数值处理的示例
以下是完整的演示代码：
C++ 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207 #include <iostream>
#include <vector>
using namespace std ;
//......................................................................................
int myCompare ( string a , string b ) //大数比较设定a>b返回1 a<b返回-1 a=b返回0
{
if ( a . size () != b . size ()) //如果字符串长度不同那么长度大的那个就是更大的大数
{
if ( a . size () > b . size ())
return 1 ;
else
return -1 ;
}
else //如果字符串长度相同我们通过直接比较字符串的字典序来判断大小
{
if ( a > b )
return 1 ;
else if ( a == b )
return 0 ;
else
return -1 ;
}
}
//......................................................................................
string myAdd ( string a , string b ) //高精度加法
{
int n = max ( a . size (), b . size ()) + 1 ;
vector < int > ans ( n , 0 ); //开辟一个足够存储结果的数组，结果的位数最多为 位数最多的那个数的位数加一(考虑进位)
int i = a . size () -1 , j = b . size () -1 , k = n -1 ; //从个位开始通过模拟竖式进行大数加法
while ( i >= 0 && j >= 0 ) //当两数均未加完时
{
ans [ k -- ] = ( a [ i -- ] - '0' ) + ( b [ j -- ] - '0' ); //我们让我们的数组存储每一位相加的结果注意将字符串转为整型数字
}
//检测是否有某个数的高位未加完将其直接存入数组中
while ( j >= 0 )
{
ans [ k -- ] = ( b [ j -- ] - '0' );
}
while ( i >= 0 )
{
ans [ k -- ] = ( a [ i -- ] - '0' );
}
string c = "" ; //创建一个字符串去存储答案
for ( int i = n -1 ; i > 0 ; i -- ) //因为之前的竖式加每一位都没考虑进位所以我们从最后开始检查进位
{ //因为是加法如果有进位最多也就进一
if ( ans [ i ] >= 10 ) //如果大于10说明应该进位那么我们让此位减10它的高一位加1
{
ans [ i ] -= 10 ;
ans [ i -1 ] ++ ;
}
c . insert ( 0 , 1 , ans [ i ] + '0' ); //处理后的结果转化为字符插入结果字符的首位
}
if ( ans [ 0 ] > 0 ) //检查最最高位是否大于0如果两数相加没有进位那么这一位就是0我们就不必存储它否则则放入字符串
{
c . insert ( 0 , 1 , ans [ 0 ] + '0' );
}
return c ; //返回答案
}
//......................................................................................
string mySubtract ( string a , string b ) //高精度减法(整体思想同加法)
{
string c = "" ; //创建一个字符串去存储答案
if ( myCompare ( a , b ) == 0 ) //先比较一下两数大小如果相等我们直接返回0即可
return "0" ;
if ( myCompare ( a , b ) == -1 ) //如果a<b那么我们交换两数的值同时在答案字符串中先放入一个负号
{
swap ( a , b );
c . push_back ( '-' );
}
int n = a . size ();
//开辟一个足够存储结果的数组 减法结果的位数最多为位数最多的那个数的位数我们保证了a为的大数所以就是a的位数
vector < int > ans ( n , 0 );
int i = a . size () -1 , j = b . size () -1 , k = n -1 ; //从个位开始模拟竖式减法
int t = 0 ; //表示低位的借位情况 0:无借位 1:有借位
while ( i >= 0 ) //同加法一样模拟运算我们知道a是大数所以a遍历完竖式才完成
{
char nowb ; //被减数当前位有数就正常减 没有数说明就是0
if ( j >= 0 ) nowb = b [ j ];
else nowb = '0' ;
ans [ k ] = a [ i ] - nowb - t ; //对应位相减同时减去低位的借位
if ( ans [ k ] < 0 ) //如果结果小于0 则向高位借一位
{
t = 1 ;
ans [ k ] += 10 ;
}
else t = 0 ; //否则向高位无借位
k -- , i -- , j -- ; //继续判断高一位
}
bool flag = true ; //这里与加法不同高位可能出现多个零开头的情况我们需要找到第一不是零的地方再存数
for ( int i = 0 ; i < n ; i ++ )
{
if ( flag && ans [ i ] == 0 ) //如果当前数为0且未存数则不执行存数操作
continue ;
flag = false ; //一旦存入数更改标志位
c . push_back ( ans [ i ] + '0' );
}
return c ; //返回结果
}
//......................................................................................
string myMultiply ( string a , string b ) //高精度乘法
{
if ( a == "0" || b == "0" ) //其中有一个为0时直接返回0
return "0" ;
vector < int > ans ; //开辟一个足够存储结果的数组
int n = a . size (), m = b . size ();
ans . resize ( n + m , 0 ); //乘法结果的位数最多为两数的位数之和
for ( int i = 0 ; i < n ; i ++ ) //这里从高位开始和从低位开始无所谓我们将两数相乘的结果不考虑放到对应位上最后去检测进位即可
{ //例如个位乘百位的结果 以及十位乘十位的结果 都放到百位上
for ( int j = 0 ; j < m ; j ++ )
{
ans [ i + j + 1 ] += ( a [ i ] - '0' ) * ( b [ j ] - '0' );
}
}
for ( int i = n + m -1 ; i > 0 ; i -- ) //我们从低位开始检查进位
{
if ( ans [ i ] >= 10 ) //如果大于10说明有进位但乘法的进位不一定只进1
{
ans [ i -1 ] += ( ans [ i ] / 10 ); //高位加地位的高于个位部分
ans [ i ] %= 10 ; //低位对十求余
}
}
string c = "" ; //创建字符串存储答案
bool flag = true ; //同减法一样找到第一个不是0的位置开始存数
for ( int t = 0 ; t < n + m ; t ++ )
{
if ( flag && ans [ t ] == 0 )
continue ;
flag = false ;
c . push_back ( ans [ t ] + '0' );
}
return c ; //返回答案
}
//......................................................................................
vector < string > myDivide ( string a , string b ) //高精度除法
{
vector < string > ans ( 2 , "0" ); //先创建两个字符串空间去存储答案一个存商一个存余数
if ( myCompare ( a , b ) == -1 ) //如果被除数比除数小商为0余数为a返回答案即可
{
ans [ 1 ] = a ;
return ans ;
}
else if ( myCompare ( a , b ) == 0 ) //如果被除数与除数相等商为1余数为0返回答案即可
{
ans [ 0 ] = "1" ;
return ans ;
}
else //否则我们需要模拟除法的竖式来进行计算
{
string res = "" ; //创建存储商的字符串
int m1 = a . size (), m2 = b . size ();
string a1 = a . substr ( 0 , m2 -1 );
for ( int i = m2 -1 ; i < m1 ; i ++ ) //模拟竖式从高位开始依次取数减去除数能减几个该位商的当前位就是几
{
if ( a1 == "0" ) //如果a1为0为了防止a1出现0开头的情况我们将它清空
a1 = "" ;
a1 . push_back ( a [ i ]); //我们从被除数中取一个数放入a1继续减
int e = 0 ;
while ( myCompare ( a1 , b ) >= 0 ) //当a1大于等于除数时便一直减同时e累加
{
e ++ ;
a1 = mySubtract ( a1 , b );
}
if ( res . size () || e ) //如果res不为空或者e不为0我们存储他
res . push_back ( e + '0' );
}
ans [ 0 ] = res ; //最后res就是商
ans [ 1 ] = a1 ; //a1就是余数
return ans ; //返回答案
}
}
//......................................................................................
string myFactorial ( string a ) //高精度阶乘
{ /*我们还可以利用高精度减法和乘法实现大数的阶乘(最大可运行出10000左右的阶乘)*/
if ( a == "1" )
return a ;
else
return myMultiply ( a , myFactorial ( mySubtract ( a , "1" )));
}
//......................................................................................
int main ()
{
string a , b ;
string add_ans , subtract_ans , multiply_ans , factorial_ans ;
vector < string > divide_ans ;
int compare_ans ;
cin >> a >> b ;
compare_ans = myCompare ( a , b );
cout << compare_ans << endl ;
add_ans = myAdd ( a , b );
cout << add_ans << endl ;
subtract_ans = mySubtract ( a , b );
cout << subtract_ans << endl ;
multiply_ans = myMultiply ( a , b );
cout << multiply_ans << endl ;
divide_ans = myDivide ( a , b );
cout << divide_ans [ 0 ] << endl << divide_ans [ 1 ] << endl ;
factorial_ans = myFactorial ( a );
cout << factorial_ans << endl ;
return 0 ;
}
4.5 排序算法
4.5.1 排序算法的基本概念
排序算法是一种将一组数据按照特定顺序排列的算法。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。
排序算法的基本概念包括：
稳定性：如果排序算法对于具有相同关键字的记录在排序前后它们的相对次序不变，则称该排序算法是稳定的，否则称为不稳定的。（选择、希尔、快速、堆排序 为不稳定排序）
时间复杂度：指算法执行所需的时间，通常用“大O表示法”表示，表示最坏情况下的执行次数。
空间复杂度：指算法执行所需的内存空间，通常用“大O表示法”表示，表示最坏情况下的空间占用。
内部排序和外部排序：内部排序指所有排序操作都在内存中进行，而外部排序则是指排序数据很大，无法一次性装入内存，需要在内外存之间进行数据交换的排序算法。
比较排序和非比较排序：比较排序是指通过比较来决定元素间的相对次序，而非比较排序则是通过其他方式来决定元素间的相对次序，如计数排序、基数排序等。
自适应性：指排序算法在处理的数据集本身的特点下进行调整的能力。
4.5.2 冒泡排序
冒泡排序是一种简单的排序算法，通过不断交换相邻元素将最大的元素“冒泡”到最后。具体来说，算法从第一个元素开始，依次比较相邻的两个元素，如果它们的顺序不对，就交换它们的位置，这样一趟下来，最大的元素就“冒泡”到了最后一个位置。接着，算法再从第一个元素开始，重复上述操作，直到所有元素都排好序。
时间复杂度：O(n2 )
下面是一个冒泡排序的 C++ 实现代码：
C++ 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 #include <iostream>
using namespace std ;
void bubbleSort ( int arr [], int n ) {
for ( int i = 0 ; i < n - 1 ; i ++ ) {
for ( int j = 0 ; j < n - i - 1 ; j ++ ) {
if ( arr [ j ] > arr [ j + 1 ]) {
int temp = arr [ j ];
arr [ j ] = arr [ j + 1 ];
arr [ j + 1 ] = temp ;
}
}
}
}
int main () {
int arr [] = { 64 , 34 , 25 , 12 , 22 , 11 , 90 };
int n = sizeof ( arr ) / sizeof ( arr [ 0 ]);
cout << "Original array: \n " ;
for ( int i = 0 ; i < n ; i ++ ) {
cout << arr [ i ] << " " ;
}
bubbleSort ( arr , n );
cout << " \n Sorted array: \n " ;
for ( int i = 0 ; i < n ; i ++ ) {
cout << arr [ i ] << " " ;
}
return 0 ;
}
这段代码实现了冒泡排序的基本功能：在给定的数组上进行排序，最终得到一个从小到大的有序数组。
4.5.3 简单选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是在未排序的元素中选择最小（或最大）的元素，将其放置在已排序的元素末尾。通过不断选择未排序部分的最小元素，直至整个序列有序。
选择排序的时间复杂度为O(n2 )，空间复杂度为O(1)，虽然其时间复杂度相对较高，但实现简单易懂，在一些小规模的数据排序中仍然具有一定的优势。
以下是选择排序的C++代码实现：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13 void selectionSort ( int arr [], int n ) {
for ( int i = 0 ; i < n -1 ; i ++ ) {
int minIndex = i ;
for ( int j = i + 1 ; j < n ; j ++ ) {
if ( arr [ j ] < arr [ minIndex ]) {
minIndex = j ;
}
}
if ( minIndex != i ) {
swap ( arr [ i ], arr [ minIndex ]);
}
}
}
其中，arr为待排序数组，n为数组长度。内层循环每次找到未排序部分的最小值，并将其与未排序部分的第一个元素进行交换。
4.5.4 简单插入排序
插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。
具体步骤如下：
1.将第一个元素看作已排好序的子序列，将第二个元素到最后一个元素看作未排序的子序列。
2.将未排序的子序列中的第一个元素与已排序的子序列进行比较，找到合适的位置将其插入到已排序的子序列中。
3.重复第二步，直到未排序的子序列为空。
C++代码实现如下：
C++ 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 #include <iostream>
using namespace std ;
void insertionSort ( int arr [], int n ) {
int i , key , j ;
for ( i = 1 ; i < n ; i ++ ) {
key = arr [ i ];
j = i - 1 ;
while ( j >= 0 && arr [ j ] > key ) {
arr [ j + 1 ] = arr [ j ];
j = j - 1 ;
}
arr [ j + 1 ] = key ;
}
}
int main () {
int arr [] = { 12 , 11 , 13 , 5 , 6 };
int n = sizeof ( arr ) / sizeof ( arr [ 0 ]);
cout << "Original array: \n " ;
for ( int i = 0 ; i < n ; i ++ ) {
cout << arr [ i ] << " " ;
}
insertionSort ( arr , n );
cout << " \n Sorted array: \n " ;
for ( int i = 0 ; i < n ; i ++ ) {
cout << arr [ i ] << " " ;
}
return 0 ;
}
4.6 搜索算法
搜索算法是一种用于在一个给定问题空间中寻找解决方案的计算机算法。以下是几种常见的搜索算法：
深度优先搜索（DFS）：从起点开始，不断向下搜索直到无法延伸为止，然后回溯到上一个节点继续搜索。
广度优先搜索（BFS）：从起点开始，以层次的方式逐步扩展搜索范围，直到找到目标节点为止。
A*搜索：使用启发式函数来评估搜索节点的优先级，选择当前最有可能导致解决方案的节点进行搜索。
贪心算法：每次都选择局部最优解，但不保证全局最优解。
二分搜索：对于有序数组，反复将数组折半，直到找到目标元素位置。
基于图的搜索算法：如Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等。
遗传算法：模拟自然选择过程，通过交叉、变异等操作逐代优化解决方案。
这些算法各有优缺点，应根据具体问题场景选择合适的算法。
4.6.1 深度优先搜索
深度优先搜索（DFS）是一种常用的图遍历算法，它从图中的一个节点开始，沿着一条分支直到底部，然后回溯到上一个节点，再沿着另一条分支继续深入。它的实现可以使用递归或栈。
以下是深度优先搜索的详细步骤：
访问起始节点，并将其标记为已访问。
从起始节点开始，遍历与之相邻的所有未访问的邻居节点。
对于每个未访问的邻居节点，重复步骤1和步骤2，直到所有的可达节点都被访问为止。
如果当前节点没有未访问过的邻居，回溯到上一个节点，继续遍历其他分支。
深度优先搜索的时间复杂度为O(V+E)，其中V是节点数目，E是边数目。如果使用递归实现，空间复杂度会比较高，因为需要在递归调用时保存函数调用栈。如果使用栈来实现，空间复杂度可以控制在O(H)，其中H是搜索树的高度。
深度优先搜索可以用于解决很多问题，如拓扑排序、连通性问题、迷宫问题等。但是，由于其搜索方式是沿着一条分支不断深入，可能会陷入局部最优解，无法找到全局最优解。因此，在某些情况下，需要使用其他搜索算法来保证找到全局最优解。
以下是一个简单的深度优先搜索的例子，使用C++语言实现：
假设有一个无向图，其中顶点编号从0到6，边的关系如下：
代码如下：
C++ 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 #include <iostream>
#include <vector>
using namespace std ;
const int MAXN = 7 ; // 图中节点数目
vector < int > adj [ MAXN ]; // 存储邻接表
bool visited [ MAXN ]; // 标记每个节点是否已被访问
// 深度优先搜索函数
void dfs ( int u ) {
visited [ u ] = true ;
cout << u << " " ; // 访问当前节点
for ( int v : adj [ u ]) {
if ( ! visited [ v ]) {
dfs ( v ); // 继续遍历未访问过的邻居
}
}
}
int main () {
// 初始化邻接表
adj [ 0 ]. push_back ( 1 );
adj [ 0 ]. push_back ( 3 );
adj [ 1 ]. push_back ( 0 );
adj [ 1 ]. push_back ( 2 );
adj [ 1 ]. push_back ( 4 );
adj [ 2 ]. push_back ( 1 );
adj [ 2 ]. push_back ( 5 );
adj [ 3 ]. push_back ( 0 );
adj [ 3 ]. push_back ( 4 );
adj [ 4 ]. push_back ( 1 );
adj [ 4 ]. push_back ( 3 );
adj [ 4 ]. push_back ( 5 );
adj [ 5 ]. push_back ( 2 );
adj [ 5 ]. push_back ( 4 );
adj [ 5 ]. push_back ( 6 );
adj [ 6 ]. push_back ( 5 );
// 从节点0开始深度优先搜索
dfs ( 0 );
return 0 ;
}
输出结果为：0 1 2 5 4 3 6
在这个例子中，我们使用邻接表来存储图的结构，并使用visited数组来标记每个节点是否已被访问。dfs函数实现了深度优先搜索的核心逻辑，在访问当前节点后，遍历其所有未访问过的邻居节点，并对其进行递归调用。
4.6.2 广度优先搜索
广度优先搜索（BFS）是一种常用的图遍历算法，它从起始节点开始，一层一层地扩展搜索范围，直到找到目标节点为止。BFS通常使用队列来实现。
以下是广度优先搜索的详细步骤：
创建一个队列，将起始节点加入队列中，并将其标记为已访问。
从队列中取出第一个节点，遍历与之相邻的所有未访问过的邻居节点。
对于每个未访问的邻居节点，将其加入队列末尾，并将其标记为已访问。
重复步骤2和步骤3，直到队列为空或者找到目标节点为止。
BFS的时间复杂度为O(V+E)，其中V是节点数目，E是边数目。空间复杂度也为O(V+E)，因为需要保存每个节点的状态及其相关信息。
BFS可以解决很多问题，如最短路径、连通性问题等。它能够保证找到最短路径，并且不会陷入局部最优解。但是，在处理大规模图时，可能会占用较多的内存空间。此外，BFS算法还需要考虑环的情况，否则可能会导致死循环。
以下是一个简单的广度优先搜索的例子，使用C++语言实现：
假设有一个无向图，其中顶点编号从0到6，边的关系如下：
代码如下：
C++ 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
51
52
53
54 #include <iostream>
#include <queue>
#include <vector>
using namespace std ;
const int MAXN = 7 ; // 图中节点数目
vector < int > adj [ MAXN ]; // 存储邻接表
bool visited [ MAXN ]; // 标记每个节点是否已被访问
// 广度优先搜索函数
void bfs ( int u ) {
queue < int > q ;
visited [ u ] = true ;
q . push ( u );
while ( ! q . empty ()) {
int v = q . front ();
q . pop ();
cout << v << " " ; // 访问当前节点
for ( int w : adj [ v ]) {
if ( ! visited [ w ]) {
visited [ w ] = true ;
q . push ( w ); // 将未访问过的邻居加入队列
}
}
}
}
int main () {
// 初始化邻接表
adj [ 0 ]. push_back ( 1 );
adj [ 0 ]. push_back ( 3 );
adj [ 1 ]. push_back ( 0 );
adj [ 1 ]. push_back ( 2 );
adj [ 1 ]. push_back ( 4 );
adj [ 2 ]. push_back ( 1 );
adj [ 2 ]. push_back ( 5 );
adj [ 3 ]. push_back ( 0 );
adj [ 3 ]. push_back ( 4 );
adj [ 4 ]. push_back ( 1 );
adj [ 4 ]. push_back ( 3 );
adj [ 4 ]. push_back ( 5 );
adj [ 5 ]. push_back ( 2 );
adj [ 5 ]. push_back ( 4 );
adj [ 5 ]. push_back ( 6 );
adj [ 6 ]. push_back ( 5 );
// 从节点0开始广度优先搜索
bfs ( 0 );
return 0 ;
}
输出结果为：0 1 3 2 4 5 6
在这个例子中，我们使用邻接表来存储图的结构，并使用visited数组来标记每个节点是否已被访问。bfs函数实现了广度优先搜索的核心逻辑，使用队列来保存待遍历的节点，对于每个未访问过的邻居节点，将其加入队列末尾，并将其标记为已访问。
4.7 图论算法
图论算法是计算机科学中重要的一部分，主要用于研究图形之间的关系和性质。图可以用节点和边的集合来表示，其中节点表示对象或实体，边表示这些实体之间的联系或关系。图论算法可以用于各种应用场景，例如社交网络分析、路线规划、生物信息学等。
图论算法主要包括以下几种：
最短路径算法：用于计算两个节点之间的最短路径，例如 Dijkstra 算法、Floyd 算法等。
最小生成树算法：用于在一个带权的无向图中找到一棵生成树，使得这棵生成树的所有边权之和最小，例如 Prim 算法、Kruskal 算法等。
拓扑排序算法：用于在一个有向无环图中，给出一种节点的线性排序，使得每个节点在排序中都出现在它的所有后继节点之前，例如 Kahn 算法、DFS 算法等。
强连通分量算法：用于将一个有向图中的所有节点分成若干个强连通分量，其中强连通分量指的是一个有向图中任意两个节点之间都存在一条路径，例如 Kosaraju 算法、Tarjan 算法等。
最大流算法：用于计算一个网络中从源节点到汇节点的最大流量，例如 Ford-Fulkerson 算法、Dinic 算法等。
4.7.1 图的表示法
图可以用多种方式进行表示，包括邻接矩阵、邻接表、关联矩阵 等。下面简要介绍一下这些表示法的特点：
邻接矩阵
邻接矩阵是用一个二维数组表示图的连接情况，其中矩阵的行列分别对应于图中的顶点，矩阵中的每个元素则表示对应的两个顶点之间是否存在边。如果两个顶点之间存在边，则该元素的值为边的权值，否则为0或一个表示不存在边的常数。
邻接矩阵的优点是查询两个顶点之间是否存在边非常快，只需要一次数组的访问操作即可。但是，对于稀疏图（即边数很少）而言，邻接矩阵的空间复杂度较高，浪费了大量的空间。
以下是代码示例，包含了图的创建、遍历、最短路径等操作：
C++ 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99 #include <iostream>
#include <queue>
#include <cstring>
using namespace std ;
const int N = 510 ;
const int INF = 0x3f3f3f3f ;
int n , m ;
int g [ N ][ N ];
int dist [ N ]; // 最短路数组
bool st [ N ]; // 是否已经确定最短路
// 图的创建
void createGraph ()
{
cin >> n >> m ;
memset ( g , 0x3f , sizeof g ); // 初始化为INF
while ( m -- )
{
int a , b , c ;
cin >> a >> b >> c ;
g [ a ][ b ] = min ( g [ a ][ b ], c );
}
}
// BFS 遍历
void bfs ( int u )
{
queue < int > q ;
q . push ( u );
st [ u ] = true ;
while ( q . size ())
{
int t = q . front ();
q . pop ();
cout << t << " " ;
for ( int i = 1 ; i <= n ; i ++ )
if ( g [ t ][ i ] != INF && ! st [ i ])
{
q . push ( i );
st [ i ] = true ;
}
}
cout << endl ;
}
// DFS 遍历
void dfs ( int u )
{
cout << u << " " ;
st [ u ] = true ;
for ( int i = 1 ; i <= n ; i ++ )
if ( g [ u ][ i ] != INF && ! st [ i ])
dfs ( i );
}
// Dijkstra 最短路径算法
void dijkstra ( int u )
{
memset ( dist , 0x3f , sizeof dist );
memset ( st , false , sizeof st );
dist [ u ] = 0 ;
for ( int i = 0 ; i < n - 1 ; i ++ )
{
int t = -1 ;
for ( int j = 1 ; j <= n ; j ++ )
if ( ! st [ j ] && ( t == -1 || dist [ t ] > dist [ j ]))
t = j ;
st [ t ] = true ;
for ( int j = 1 ; j <= n ; j ++ )
if ( g [ t ][ j ] != INF )
dist [ j ] = min ( dist [ j ], dist [ t ] + g [ t ][ j ]);
}
for ( int i = 1 ; i <= n ; i ++ )
cout << dist [ i ] << " " ;
cout << endl ;
}
int main ()
{
createGraph ();
bfs ( 1 );
memset ( st , false , sizeof st );
dfs ( 1 );
cout << endl ;
dijkstra ( 1 );
return 0 ;
}
邻接表
邻接表是一种链式存储结构，用一个数组存储所有顶点，每个顶点都有一个链表存储与之相邻的顶点。链表中的每个节点都包含一个指向相邻顶点的指针，以及一些附加信息，如边权值等。
邻接表的优点是适用于表示稀疏图，因为只有存在边的顶点才会被存储，从而减小了空间开销。同时，邻接表的插入和删除操作也比较高效。但是，查询两个顶点之间是否存在边的时间复杂度比邻接矩阵要高一些。
下面是使用邻接表表示无向图的C++代码：
C++ 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
51
52
53
54
55
56
57
58
59
60
61
62 #include <iostream>
#include <vector>
using namespace std ;
// 边的结构体
struct Edge {
int to ; // 边的终点
int weight ; // 边的权值
Edge ( int to , int weight ) : to ( to ), weight ( weight ) {}
};
// 邻接表中的一个节点，表示起点为from的一条边
struct Node {
int from ; // 起点
vector < Edge > edges ; // 所有以该点为起点的边
Node ( int from ) : from ( from ) {}
};
// 无向图的邻接表表示
class Graph {
public :
int n ; // 图中节点数
vector < Node > nodes ; // 邻接表中的所有节点
Graph ( int n ) : n ( n ) {
// 初始化邻接表
for ( int i = 0 ; i < n ; i ++ ) {
nodes . push_back ( Node ( i ));
}
}
// 添加无向边
void addUndirectedEdge ( int from , int to , int weight ) {
nodes [ from ]. edges . push_back ( Edge ( to , weight ));
nodes [ to ]. edges . push_back ( Edge ( from , weight ));
}
};
int main () {
int n = 5 ; // 节点数
Graph g ( n );
g . addUndirectedEdge ( 0 , 1 , 1 );
g . addUndirectedEdge ( 0 , 2 , 3 );
g . addUndirectedEdge ( 1 , 2 , 1 );
g . addUndirectedEdge ( 1 , 3 , 5 );
g . addUndirectedEdge ( 2 , 3 , 2 );
g . addUndirectedEdge ( 2 , 4 , 1 );
g . addUndirectedEdge ( 3 , 4 , 4 );
// 输出邻接表
for ( int i = 0 ; i < n ; i ++ ) {
cout << "Node " << i << ": " ;
for ( auto e : g . nodes [ i ]. edges ) {
cout << "(" << e . to << ", " << e . weight << ") " ;
}
cout << endl ;
}
return 0 ;
}
关联矩阵
关联矩阵是一种二维数组，用于表示顶点和边之间的关系。矩阵的行对应于顶点，列对应于边，矩阵中的每个元素表示对应的顶点和边之间是否存在关联。如果一个顶点与一条边相连，则该元素的值为1或边的权值，否则为0或一个表示不存在关联的常数。
关联矩阵可以用于表示有向图或带权图，但其空间开销较大，且查询两个顶点之间是否存在边的时间复杂度也比较高。因此，一般情况下不建议使用关联矩阵进行图的存储和处理。
下面是一个简单的关联矩阵的实现代码：
C++ 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 #include <iostream>
#include <vector>
using namespace std ;
const int MAXN = 100 ;
int M , N ; // M 表示顶点数，N 表示边数
vector < int > edges [ MAXN ]; // 存储每个顶点所连的边的编号
void printAdjMatrix () { // 输出关联矩阵
int adjMatrix [ MAXN ][ N ];
memset ( adjMatrix , 0 , sizeof ( adjMatrix )); // 初始化为0
for ( int i = 0 ; i < M ; i ++ ) {
for ( int j = 0 ; j < edges [ i ]. size (); j ++ ) {
int e = edges [ i ][ j ];
adjMatrix [ i ][ e ] = 1 ;
}
}
for ( int i = 0 ; i < M ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
cout << adjMatrix [ i ][ j ] << " " ;
}
cout << endl ;
}
}
int main () {
cin >> M >> N ;
for ( int i = 0 ; i < M ; i ++ ) {
int k ;
cin >> k ;
for ( int j = 0 ; j < k ; j ++ ) {
int e ;
cin >> e ;
edges [ i ]. push_back ( e );
}
}
printAdjMatrix ();
return 0 ;
}
这里使用了一个 vector 数组 edges 来存储每个顶点所连的边的编号，这是因为邻接表和关联矩阵之间的转换需要用到每个顶点所连的边的信息。在 printAdjMatrix 函数中，我们首先将关联矩阵的所有元素初始化为0，然后再遍历每个顶点所连的边，将对应位置上的元素设为1。最后输出整个矩阵即可。
4.7.2 图的深度优先遍历算法
图的深度优先遍历算法是一种经典的图遍历算法，它通过从图中某一起点开始，不断访问它的邻居节点，并将已经访问过的节点标记为已访问，直到所有节点都被访问过为止。在访问过程中，对于每个节点，都要递归地访问它的邻居节点，直到无法再访问为止。
下面是图的深度优先遍历算法的C++代码实现：
C++ 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 #include <iostream>
#include <vector>
using namespace std ;
const int MAXN = 1005 ; // 图的最大节点数
vector < int > graph [ MAXN ]; // 邻接表存储图
bool visited [ MAXN ]; // 记录节点是否已被访问
// 深度优先遍历算法
void dfs ( int u ) {
visited [ u ] = true ; // 标记节点u已被访问
cout << u << " " ; // 输出节点u的编号
for ( int i = 0 ; i < graph [ u ]. size (); i ++ ) { // 遍历节点u的所有邻居节点
int v = graph [ u ][ i ];
if ( ! visited [ v ]) { // 如果节点v未被访问
dfs ( v ); // 递归地访问节点v
}
}
}
int main () {
int n , m ;
cin >> n >> m ; // 输入节点数n和边数m
for ( int i = 0 ; i < m ; i ++ ) {
int u , v ;
cin >> u >> v ; // 输入一条边的两个端点u和v
graph [ u ]. push_back ( v ); // 添加一条从u到v的边
graph [ v ]. push_back ( u ); // 添加一条从v到u的边（如果图是无向图）
}
int start ;
cin >> start ; // 输入起点
dfs ( start ); // 从起点开始深度优先遍历整个图
return 0 ;
}
在这个代码中，我们首先定义了一个graph数组，用邻接表的方式存储了整个图。然后定义了一个visited数组，用来记录每个节点是否已被访问。在dfs函数中，我们首先标记了当前节点已被访问，然后输出了它的编号，并递归地访问了它的所有邻居节点。最后在main函数中，我们输入了整个图，然后调用dfs函数从起点开始遍历整个图。
4.7.3 图的宽度优先遍历算法
图的宽度优先遍历（BFS）算法是一种遍历图的算法，可以用于搜索最短路径等问题。
BFS算法的基本思想是从一个起点开始，逐层遍历与该节点相邻的所有节点，直到遍历完所有连通的节点。在遍历的过程中，可以使用队列数据结构来存储已经访问过的节点，保证遍历的正确性和效率。
下面是一个简单的C++实现，其中graph表示邻接表存储的图，start表示起点：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 void BFS ( vector < vector < int >>& graph , int start ) {
queue < int > q ;
vector < bool > visited ( graph . size (), false );
q . push ( start );
visited [ start ] = true ;
while ( ! q . empty ()) {
int curr = q . front ();
q . pop ();
// 处理当前节点
cout << curr << " " ;
// 遍历与当前节点相邻的节点
for ( int i = 0 ; i < graph [ curr ]. size (); ++ i ) {
int neighbor = graph [ curr ][ i ];
if ( ! visited [ neighbor ]) {
q . push ( neighbor );
visited [ neighbor ] = true ;
}
}
}
}
4.7.4 洪水填充算法（floodfill）
洪水填充算法（floodfill）是一种常见的图形填充算法，用于将一个区域中的所有像素值都替换成一个指定的新像素值。该算法通常用于图像处理、计算机游戏中的地图着色、区域填充等应用场景。
算法思路：
首先选择一个起始点，并将其像素值替换为指定的新值；
将起始点入队列；
从队列中取出一个点，对它的四个邻居进行扫描，若邻居像素值与原像素值相同，则将其像素值替换为指定的新值，并将其入队列；
重复步骤3，直到队列为空。
C++代码实现（以二维数组表示图）：
C++ 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
51 #include <iostream>
#include <queue>
using namespace std ;
const int MAXN = 100 ;
int g [ MAXN ][ MAXN ]; // 二维数组表示图
int dx [] = { 0 , 0 , 1 , -1 }; // 方向数组
int dy [] = { 1 , -1 , 0 , 0 };
int n , m ;
void floodfill ( int x , int y , int newcolor ) {
int oldcolor = g [ x ][ y ]; // 原像素值
queue < pair < int , int >> q ; // 保存队列
q . push ({ x , y }); // 入队列
g [ x ][ y ] = newcolor ; // 替换像素值
while ( ! q . empty ()) {
int u = q . front (). first , v = q . front (). second ;
q . pop ();
for ( int i = 0 ; i < 4 ; ++ i ) { // 扫描四个方向的像素
int nx = u + dx [ i ], ny = v + dy [ i ];
if ( nx >= 0 && nx < n && ny >= 0 && ny < m && g [ nx ][ ny ] == oldcolor ) {
g [ nx ][ ny ] = newcolor ; // 替换像素值
q . push ({ nx , ny }); // 入队列
}
}
}
}
int main () {
cin >> n >> m ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < m ; ++ j ) {
cin >> g [ i ][ j ];
}
}
int x , y , newcolor ;
cin >> x >> y >> newcolor ;
floodfill ( x , y , newcolor );
// 输出结果
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < m ; ++ j ) {
cout << g [ i ][ j ] << " " ;
}
cout << endl ;
}
return 0 ;
}
其中，pair<int, int> 表示二维坐标 (x, y)，queue<pair<int, int>> 表示一个坐标点的队列。
4.8 动态规划
4.8.1 动态规划的基本思想
动态规划是一种算法思想，主要用于解决具有重叠子问题和最优子结构性质的问题。其基本思路是将原问题划分为若干个子问题，逐个求解子问题，并保存子问题的解，最终得到原问题的解。动态规划常用于求解最优解问题，比如背包问题、最长递增子序列问题、最短路径问题等。
动态规划算法的基本流程如下：
确定状态：将原问题分解为若干子问题，定义状态，将子问题的解存储起来，通常用一个数组或者矩阵来表示状态。
确定状态转移方程：通过分析子问题之间的联系，确定状态转移方程，以递推方式求解子问题，从而求得原问题的解。
确定边界条件：递推的过程中，需要考虑边界情况，即初始值的问题，从而避免数组越界等问题。
求解原问题：根据递推方程和边界条件，求解原问题。
动态规划算法的时间复杂度一般较高，但是由于其具有子问题重叠性质和最优子结构性质，可以将计算结果进行存储，从而避免重复计算，降低时间复杂度，提高算法效率。
4.8.2 简单一维动态规划
一维动态规划是指问题只涉及一个变量的情况，通常采用一维数组来存储中间状态。下面介绍一个简单的一维动态规划问题及其解法。
问题描述：给定一个长度为n的数组a，求其最大连续子序列和。
最大连续子序列和问题是一个经典的动态规划问题。给定一个整数序列，求它的最大连续子序列的和。
具体算法步骤如下：
定义一个数组 dp，其中 dp[i] 表示以第 i 个数结尾的最大连续子序列和。
初始化 dp[0] 为序列的第一个数。
从第二个数开始，逐个计算 dp[i]，计算方法为：
如果 dp[i-1] 大于 0，则 dp[i] = dp[i-1] + nums[i]，即前面的子序列对于当前子序列的和有增益作用。
如果 dp[i-1] 小于等于 0，则 dp[i] = nums[i]，即前面的子序列对于当前子序列的和没有增益作用，因此最大子序列应该从当前数开始重新计算。
找出数组 dp 中的最大值即为最大连续子序列和。
下面是 C++ 代码实现：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #include <iostream>
#include <vector>
using namespace std ;
int maxSubArray ( vector < int >& nums ) {
int n = nums . size ();
if ( n == 0 ) return 0 ;
int dp = nums [ 0 ], res = dp ;
for ( int i = 1 ; i < n ; i ++ ) {
if ( dp > 0 ) dp += nums [ i ];
else dp = nums [ i ];
res = max ( res , dp );
}
return res ;
}
int main () {
vector < int > nums = { -2 , 1 , -3 , 4 , -1 , 2 , 1 , -5 , 4 };
cout << maxSubArray ( nums ) << endl ; // output: 6
return 0 ;
}
时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(1)\) 。
4.8.3 简单背包类型动态规划
简单背包问题是动态规划中常见的问题之一，也是入门级动态规划问题。
问题描述：给定一个背包，最大容量为 \(W\) ，给定 \(n\) 个物品，每个物品的重量为 \(w_i\) ，价值为 \(v_i\) ，求最多能装下的物品价值总和。
这个问题可以使用动态规划的思想来解决，具体步骤如下：
定义状态
设 \(f(i,j)\) 表示前 \(i\) 个物品中选出一些物品放进容量为 \(j\) 的背包中所能获得的最大价值。
初始化
初始状态为 \(f(0,j) = 0\) ，表示不选取任何物品时背包的价值为 \(0\) ，\(f(i,0) = 0\) ，表示背包容量为 \(0\) 时无论选哪些物品都无法装进去。
状态转移方程
对于每个物品，有两种选择，装入背包或者不装入背包。因此可以得到状态转移方程：
\[f(i,j) = \max{f(i-1,j), f(i-1,j-w_i)+v_i}\]
其中，第一项 \(f(i-1,j)\) 表示不选当前物品 \(i\) ，第二项 \(f(i-1,j-w_i)+v_i\) 表示选取当前物品 \(i\) ，背包容量减少 \(w_i\) ，获得的价值增加 \(v_i\) 。
输出结果
最终的结果为 \(f(n,W)\) ，即选取前 \(n\) 个物品放入容量为 \(W\) 的背包中所获得的最大价值。
以下是 0/1 背包问题的动态规划代码实现：
C++ 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 #include <iostream>
#include <cstring>
using namespace std ;
const int MAX_N = 1005 ;
int N , W ;
int w [ MAX_N ], v [ MAX_N ];
int dp [ MAX_N ][ MAX_N ];
int main () {
cin >> N >> W ;
for ( int i = 1 ; i <= N ; ++ i ) cin >> w [ i ] >> v [ i ];
for ( int i = 1 ; i <= N ; ++ i ) {
for ( int j = 1 ; j <= W ; ++ j ) {
if ( j >= w [ i ]) dp [ i ][ j ] = max ( dp [ i -1 ][ j ], dp [ i -1 ][ j - w [ i ]] + v [ i ]);
else dp [ i ][ j ] = dp [ i -1 ][ j ];
}
}
cout << dp [ N ][ W ] << endl ;
return 0 ;
}
其中，dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。最终输出 dp[N][W] 即为解。
时间复杂度为 \(O(NW)\) ，空间复杂度为 \(O(NW)\) 。
4.8.4 简单区间类型动态规划
简单区间类型动态规划指的是给定一个序列，求解序列的某个子区间上的最优解。比如最长上升子序列、区间最大子段和等问题就属于简单区间类型动态规划。
其中，最长上升子序列问题指的是给定一个序列，求其中的一个最长上升子序列（可以不连续），而区间最大子段和问题指的是给定一个序列，求其任意一个子区间上的最大子段和。
这类问题的动态规划解法一般是通过定义状态表示区间的某种性质，然后根据这种性质设计状态转移方程，求解最终答案。
以下是最长上升子序列和区间最大子段和问题的动态规划代码实现。
最长上升子序列的动态规划代码实现（时间复杂度为 O(n2 )）：
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 int dp [ N ]; // dp[i] 表示以第 i 个数结尾的最长上升子序列的长度
int lengthOfLIS ( vector < int >& nums ) {
int n = nums . size ();
int res = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
dp [ i ] = 1 ; // 初始值为 1
for ( int j = 0 ; j < i ; ++ j ) {
if ( nums [ i ] > nums [ j ]) { // 如果 nums[i] > nums[j]，则可以将 nums[i] 接在 nums[j] 后面
dp [ i ] = max ( dp [ i ], dp [ j ] + 1 ); // 取 dp[j] + 1 和 dp[i] 本身的最大值
}
}
res = max ( res , dp [ i ]); // 更新最长上升子序列的长度
}
return res ;
}
区间最大子段和的动态规划代码实现（时间复杂度为 O(n)）：
C++ 1
2
3
4
5
6
7
8
9
10
11
12 int dp [ N ]; // dp[i] 表示以第 i 个数结尾的区间最大子段和
int maxSubArray ( vector < int >& nums ) {
int n = nums . size ();
int res = INT_MIN ; // 初始化为负无穷
dp [ 0 ] = nums [ 0 ]; // 初始值为 nums[0]
for ( int i = 1 ; i < n ; ++ i ) {
dp [ i ] = max ( dp [ i - 1 ] + nums [ i ], nums [ i ]); // 状态转移方程
res = max ( res , dp [ i ]); // 更新区间最大子段和
}
return res ;
}
小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用