算法设计与分析论文.doc

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

1、08341114陈彬算法设计与分析论文算法理论研究的是算法的设计技术和分析技术，两者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。算法设计与分析中包含非常经典的算法设计技术，例如递归与分治、动态规划、贪心、冋溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。下面我将介绍一下递归与分治策略。具体实验如下：一、实验目的：熟练掌握递归与分治的思想并应用其解决实际问题。二、递归与分治策略思想基木思想将要求解的较大规模的问题分割成k个更小规模的了问题。对这k个了问题分别求解。如果了问题的规模仍然不够小，则

2、再划分为k个了问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。实验题目：找出从白然数1,2,…….，n其屮任取「个数的所有组合。算法思想：当组合的第一个数字选定时，其后的数字是从余下的m-1个数屮取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数屮取k-1个数的组合问题。设数引入工作数组a[]存放求出的组合，约定函数将确定的k个数字组合的第一个数字放在a[k]屮，当一冋组合求出后，才将啊"[]屮的一个组合输出。第一个数可以是m、m-1k,函数将确足组合的第一个数字放入数组麻，有两种可能的选择，因还未确泄组合的H余元索,继续递归去确定；或已确定了组合的元

3、素，输出这个组合。问题描述：找出从自然数1、2n屮任取r个数的所有组合。例如n=5,n=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个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为voidfind(intm,intk)为找出从H然数1、2m屮任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的山・1个数屮的组合问题。设函数引入工作数组滅]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，

4、当一个组合求出后，才将a[]屮的一个组合输出。第一个数可以是m、m-1k,函数将确定组合的第一个数字放入数组示，有两种肯的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见一下稈序屮的函数。【程序】#include#includeusingnamespacestd;#defineMAXN1000intafMAXN];voidf(intmjntk)intij;a[k]=i;if(k>l)f(i-l,k-l);else{fo「(j=l;a[j]>O;j++)printf(“％4cT,a[j]);printf(t

5、4M);}})intmain(){intm,k,i;vvhile(cin»m»k){for(i=0;i