算法设计与分析所有程序文件.doc

《算法设计与分析所有程序文件.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、...目录第二章递归与分治31、用递归思想求N!32、用递归思想求Fibonacci数列33、用递归思想求排列问题44、用递归思想求整数划分问题55、用递归思想求汉诺塔问题66、用递归思想实现插入排序77、用分治思想实现二分查找88、用分治法求两个大整数的乘法99、用分治思想求一个数组的最大值与最小值1010、用分法思想实现合并排序1211、用分治思想实现快速排序1312、用分治法实现线性时间选择问题1513、用分法思想实现残缺棋盘问题15第三章动态规划法181、矩阵连乘问题182、最长公子序列203、最大子段和问题234、图

2、像压缩问题285、电路布线问题316、最317、最31第四章贪心算法321、哈夫曼编码324、Kruskal算法求最小生成树355、集装箱问题386、活动安排问题40第五章回溯法421、用回溯法求0－1背包问题42.......2、用回溯法求N皇后问题453、用回溯法求旅行售货员问题464、用回溯法求圆排列问题485、用回溯法求符号三角形问题506、用回溯法求批处理作业调度问题527、用回溯法求连续邮资问题548、用回溯法求图的m着色问题579、用回溯法求最大团问题59第六章回溯法621、用分支限界法求0－1背包问题62...

3、....第二章递归与分治1、用递归思想求N!王晓东版——《计算机算法设计与分析（第四版）》P11页，例2－1#includevoidmain(){longn;intJieChen(intn);printf("请输入一个数");scanf("%ld",&n);longresult=JieChen(n);printf("%ld",result);}intJieChen(intn){if(n==1)return1;elsereturnn*JieChen(n-1);}2、用递归思想求Fibonacci数列王晓东版

4、——《计算机算法设计与分析（第四版）》P12页，例2－2intFibonacci(intn){if(n<=1)return1;elsereturnFibonacci(n-1)+Fibonacci(n-2);}voidmain(){.......longn;printf("请输入一个数");scanf("%ld",&n);longresult=Fibonacci(n);printf("%ld",result);}3、用递归思想求排列问题王晓东版——《计算机算法设计与分析（第四版）》P13页，例2－4N个元素的全排列的个数

5、为：N!本算法非常重要，因为它是很多算法的基础，比如回溯法那章里的算法很多都是以本算法为基础的。#include//交换两个元素的值voidSwap(int&x,int&y){intt=x;x=y;y=t;}//产生list[k:m]的所有排列//m是最后一个元素在数组中的下标voidPerm(intlist[],intk,intm){if(k==m)//如果只有一个元素{for(inti=0;i<=m;i++)printf("%d",list[i]);printf("");}else{for(inti=

6、k;i<=m;i++){Swap(list[i],list[k]);Perm(list,k+1,m);Swap(list[i],list[k]);//将元素还原}.......}}voidmain(){inta[5]={1,2,3,4,5};//求数组前面三个元素的全排列Perm(a,0,3);}4、用递归思想求整数划分问题王晓东版——《计算机算法设计与分析（第四版）》P14页，例2－5整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：n=m1+

7、m2+……+mi;（其中mi为正整数，并且1<=mi<=n），则{m1,m2,...,mi}为n的一个划分。如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);例如，但n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};注意4=1+3和4=3+1被认为是同一个划分。该问题是求出n的所有划分个数，即f(n,n)。下面我们考虑求f(n,m)的方法;根据n和m的关系，考虑以下几种情况

8、：(1)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};(2)当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};(3)当n=m时，根据划分中是否包含n，可以分为两种情况：(a).划分中包含n的情况，只有一个即{n}；(b).划分中不