算法设计与分析的一些实例分析

《算法设计与分析的一些实例分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一递归与分治策略一、实验目的：熟练掌握递归与分治策略的思想并应用其解决实际问题。二、递归与分治策略思想基本思想:将要求解的较大规模的问题分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。实验题目(1-2):找出从自然数1,2,…，n中任取r个数的所有组合。算法思想：当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[]存放

2、求出的组合，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或已确定了组合的全部元素，输出这个组合。问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为：（1）5、4、3（2）5、4、2（3）5、4、1（4）5、3、2（5）5、3、1（6）5、2、1（7）4、3、2（8）4、3、1（9）4、2、1（10）3、2、1分析所列的10个组合

3、，可以采用这样的递归思想来考虑求组合函数的算法。设函数为voidfind(intm,intk)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元

4、素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数。【程序】#include#includeusingnamespacestd;#defineMAXN1000inta[MAXN];voidf(intm,intk){inti,j;for(i=m;i>=k;i--){a[k]=i;if(k>1)f(i-1,k-1);else{for(j=1;a[j]>0;j++)printf("%4d",a[j]);printf("");}}}intmain(){intm,k,i;while(cin>>

5、m>>k){for(i=0;i

6、n位的串相邻元素恰好只有1位不同,以n=3为例。可以画出树形的Gray码，见图1-3即它的字符串为：0000；0001；0011；00100110；0111；0101；0100分别设为a[i]（i=0，1，2，3，4，5，6，7）观察该字符串并以分治策略可以看出，从a[0]到a[3]和a[4]到a[7]，作出比较1．最高位都为0。2．在各元素的第二位，前四个为0而后四个为1。3．后两位，前四个刚好是后四个的逆顺序，即a[0]=a[7]，a[1]=a[6]，a[2]=a[5]，a[3]=a[4]。再看n=2的字符串：n=1的字符串：00000001010110

7、10n=2的字符串在最高位加0的话就是n=3的前四个，n=1的字符串在最高位加0的话就是n=2的前二个，而且n=2的字符串也符合前面所述的三条规律。所以按照分治策略设计，利用递归方法就能构造Grey码。长度为n的Grey码字符串，前半部分只要在长度为n-1的Grey码前添0就可；后半部分令第二位为1，后几位为前半部分的逆顺序就可。源程序如下:#includeusingnamespacestd;#defineMAX100intnum,a[MAX]={0};voidGray(intn){if(n>1)Gray(n-1);if(a[n-1]==

8、0)a[n-1]=1;elsea[n-1]=0;fo