算法设计与分析所有程序

1 / 68目 录第二章 递归与分治 .31、用递归思想求 N! .32、用递归思想求 Fibonacci 数列 .33、用递归思想求排列问题 .44、用递归思想求整数划分问题 .55、用递归思想求汉诺塔问题 .66、用递归思想实现插入排序 .77、用分治思想实现二分查找 .88、用分治法求两个大整数的乘法 .99、用分治思想求一个数组的最大值与最小值 .1010、用分法思想实现合并排序 .1211、用分治思想实现快速排序 .1312、用分治法实现线性时间选择问题 .1513、用分法思想实现残缺棋盘问题 .15第三章 动态规划法 .181、矩阵连乘问题 .182、最长公子序列 .203、最大子段和问题 .234、图像压缩问题 .285、电路布线问题 .316、最 .317、最 .31第四章 贪心算法 .321、哈夫曼编码 .324、Kruskal 算法求最小生成树 .355、集装箱问题 .386、活动安排问题 .40第五章 回溯法 .421、用回溯法求 01 背包问题 .422 / 682、用回溯法求 N 皇后问题 .453、用回溯法求旅行售货员问题 .464、用回溯法求圆排列问题 .485、用回溯法求符号三角形问题 .506、用回溯法求批处理作业调度问题 .527、用回溯法求连续邮资问题 .548、用回溯法求图的 m 着色问题 .579、用回溯法求最大团问题 .59第六章 回溯法 .621、用分支限界法求 01 背包问题 .623 / 68第二章 递归与分治1、用递归思想求 N!王晓东版计算机算法设计与分析（第四版） P11 页，例 21#include void main()long n;int JieChen(int n);printf(“请输入一个数n“);scanf(“%ld“,long result = JieChen(n);printf(“%ld“,result);int JieChen(int n)if(n=1)return 1;elsereturn n*JieChen(n-1);2、用递归思想求 Fibonacci 数列王晓东版计算机算法设计与分析（第四版） P12 页，例 22int Fibonacci(int n)if(n/ 交换两个元素的值void Swap(int x = y;y = t;/ 产生 listk:m的所有排列/ m 是最后一个元素在数组中的下标void Perm(int list,int k,int m)if(k=m)/ 如果只有一个元素for(int i=0;i0) ，只有一种划分即1;(2) 当 m=1 时，不论 n 的值为多少，只有一种划分即 n 个 1，1,1, 1, ., 1 ;(3) 当 n=m 时，根据划分中是否包含 n，可以分为两种情况：(a). 划分中包含 n 的情况，只有一个即 n ；(b). 划分中不包含 n 的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有 ( n - 1 ) 划分。因此 f(n, n) = 1 + f(n, n-1);(4) 当 n m 时，根据划分中是否包含最大值 m，可以分为两种情况：(a). 划分中包含 m 的情况，即m,x1,x2, .,xi,其中x1,x2, .,xi 的和为 n-m，可能再次出现 m，因此是（n-m ）的 m 划分，因此这种划分个数为 f(n-m, m);(b). 划分中不包含 m 的情况，则划分中所有值都比 m 小，即 n 的(m-1) 划分个数为 f(n, m - 1);因此 f(n, m) = f(n-m, m) + f(n, m-1);综合以上情况，我们可以看出，上面的结论具有递归定义特征，其中（1）和（2）属于回归条件， （3）和（4）属于特殊情况，将会转换为情况（5） 。而情况（5）为通用情况，属于递推的方法，其本质主要是通过减小 m 以达到回归条件，从而解决问题。其递推表达6 / 68式如下：f(n, m) = 1; ( n = 1 or m = 1 )f(n, m) = f(n, n); ( n m )因此我们可以给出求出 f(n, m) 的递归函数代码如下。/ 求整数 n 的全部划分数，其中 max 代表最大加数long GetPartitionCount(int n, int max)if (n = 1 | max = 1)return 1;else if (n 0)Hanoi(n-1,A,C,B);7 / 68printf(“%d,%c%cn“,n,A,B); / 模拟移动过程Hanoi(n-1,C,B,A);void main()Hanoi(3,a,b,c); 6、用递归思想实现插入排序#include #include #include void insertSort(int *aa,int n)if(n0)n = n-1;insertSort(aa,n);int a= aan;int k = n-1;while(k=0)if(x=amiddle)return middle;elseif(xamiddle)return BinarySearch(a,x,middle+1,right);elsereturn BinarySearch(a,x,left,middle-1);void main()int a9=-2,2,7,9,19,21,34,65,98;int index = BinarySearch(a,100,8);printf(“%dn“,index);方法二：用循环代替递归/ 在 a 数组里查找是否存在 x 这个元素，如果存在，则返回元素所在下标，如果不存在/ 则返回-1/ n 为最后一个元素的下标int BinarySearch(int a,int x,int n)int left = 0; / 开始需要查找元素的下标9 / 68int right = n-1; / 最后需要查找元素的下标while(leftamiddle)left = middle+1;elseright = middle-1;return -1;8、用分治法求两个大整数的乘法最简单的方法，这里没有体现分治法的思想#include int main()char a100,b100,s202;int i,j,g,t=0,k=0,temp;printf(“请输入两个大整数，空格分隔n“);scanf(“%s%s“,int m = strlen(a);int n = strlen(b);while(k=0;i-)printf(“%d“,si);printf(“n“);return 0;9、用分治思想求一个数组的最