算法分析与设计复习笔记
插入排序
1. void insert_sort(int A[ ],int n)
2. {
3. int a,i,j;
4. for (i=1;i<n;i++) {
5. a = A[ i ];
6. j = i – 1;
7. while (j>=0 && A[j]>a) {
8. A[ j+1 ] = A[ j ];
9. j- -;
10. }
11. A[ j+1 ] = a;
12. }
13. }
合并两个有序的子数组
1. void merge(int A[ ],int p,int q,int r)
2. {
3. int *bp = new int[r-p+1]; // 分配缓冲区,存放被排序的元素
4. int i,j,k;
5. i = p; j = q + 1; k = 0;
6. while (i<=q && j<=r) { // 逐一判断两子数组的元素
7. if (A[ i ] <=A[ j ]) // 按两种情况,把小的元素拷贝到
8. bp[ k++ ] = A[ i++ ]; // 缓冲区*/
9. else
10. bp[ k++ ] = A[ j++ ];
11. }
12. if (i==q+1) // 按两种情况,处理其余元素
13. for (;j<=r;j++)
14. bp[++] = A[j]; // 把A[ j ]~A[ r ]拷贝到缓冲区
15. else
16. for (;i<=q;i++)
17. bp[++] = A[i]; // 把A[i]~A[q]拷贝到缓冲区
18. k = 0;
19. for (i=p;i<=r;i++) // 最后,把数组bp的内容拷贝
20. A[i++] = bp[k++]; // 到 A[p]~A[r]
21. delete bp;
22. }
i:开始合并时第一个序列的起始位置
s:合并前序列的大小
t:合并后序列的大小
合并排序算法
1. template <class Type>
2. void merge_sort(Type A[ ],int n)
3. { int i, s, t = 1;
5. while (t<n) {
6. s = t; t = 2 * s; i = 0;
7. while (i+t<n) {
8. merge(A,i,i+s-1,i+t-1); //i,i+s-1,i+t-1定义被合并的两个序列的边界。
9. i = i + t;
10. }
11. if (i+s<n)
12. merge(A,i,i+s-1,n-1);
13. }
14. }
- 汉诺塔（Hanoi）问题：
void Hanoi (char a, char b, char c, int n)
{
if ( n ==1 ) printf (“%c->%c”, a, b);
else{
Hanoi( a, c, b, n-1);
printf( “%c->%c”, a, b);
Hanoi(c, b, a, n-1);
}
}
阶乘函数可归纳定义为:
算法 计算阶乘函数 n!
1. int factorial(int n)
2. {
3. if (n==0)
4. return 1;
5. else
6. return n * factorial(n-1);
7. }
整数划分问题
用一系列正整数之和的表达式来表示一个正整数，称为整数的划分。
例：7 可划分为：
7
6 + 1
5 + 2，5 + 1 + 1
4 + 3，4 + 2 + 1，4 + 1 + 1 + 1
3 + 3 + 1，3 + 2 + 2, 3 + 2 + 1 + 1，3 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1，2 + 2 + 1 + 1 + 1，2 + 1 + 1 + 1+ 1 + 1
1 + 1 + 1+ 1 + 1 + 1 + 1
上述任何一个表达式都称为整数 7 的一个划分。
2）正整数 n 的不同的划分个数称为正整数 n 的划分数，记为 p(n )；
3）求正整数 n 的划分数称为整数划分问题。
1）定义两个函数：
r(n,m)：正整数 n 的划分中加数含 m 而不含大于 m 的所有划分数；
q(n,m)：正整数 n 的划分中加数小于或等于 m 的所有划分数。
例：在 7 的划分中：
含 6 而不含大于 6 的划分有：
6 + 1，因此，r(7,6)=1；
含 5 而不含大于 5 的划分有：
5 + 2，5 + 1 + 1，因此，r(7,5)=2；
含 4 而不含大于 4 的划分有：
4 + 3，4 + 2 + 1，4 + 1 + 1 + 1，因此，r(7,4)=3；
含 3 而不含大于 3 的划分有：
3 + 3 + 1，3 + 2 + 2, 3 + 2 + 1 + 1，3 + 1 + 1 + 1 + 1
因此，r(7,3)=4
4）递归式：
⑴ 由式 (4.1.1) 和式 (4.1.2) 可得下面递归关系：
⑵ 对所有的正整数 n， 有：
⑶ n 的划分不可能包含大于 n 的加数
⑷ 整数 1 只有一个划分，而不管 m 有多大
⑸
分治策略
将要求解的较大规模问题分割成若干个更小规模的子问题；
对这些子问题分别求解，如果子问题的规模仍不够小，则再划分为更小的子问题，如此递归的进行下去，直到问题规模足够小、很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
- 分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决；
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
快速排序的序列的划分算法
2. int split(Type A[ ], int low, int high)
3. { int k, i = low;
5. Type x = A[low];
6. for (k=low+1; k<=high; k++) {
7. if (A[k]<=x) {
8. i = i + 1;
9. if (i!=k) swap(A[i], A[k]);
11. }
12. }
13. swap(A[low], A[i]);
14. return i;
15. }
快速排序:
1. template <class Type>
2. void quick_sort(Type A[ ], int low, int high)
3. {
4. int k;
5. if (low < high) {
6. k = split(A, low, high);
7. quick_sort(A, low, k-1); //对左半段排序
8. quick_sort(A, k+1, high); //对右半段排序
9. }
10. }
贪婪法:
解向量：问题中n个元素的具体取值所构成的向量；
解空间：问题中n个元素的各种不同取值组合所构成的向量全体；
约束方程：问题中的限制条件所列出的方程；
目标函数：问题求解所要达到的目标；
可行解：满足约束方程的向量；
最优解：使目标函数达极值的向量。
性质: 最优子结构性质(动态规划也有该性质) 自顶向下
斐波那契
分治法: 优化原则或最优子结构性质, 自底向上, 划分子问题
- 分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决；
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
货郎担的动态规划函数
多段图动态规划函数:
资源分配问题
- 回溯法
- 回溯法是一个既带有系统性又带有跳跃性的搜索算法；
- 它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。——系统性
原文地址：https://blog.csdn.net/m0_74042991/article/details/144232899
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！