《算法设计》课程解题报告

《《算法设计》课程解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称：算法设计学生姓名：郭泉学生学号：0643111084《算法设计》课程报告课题名称：算法设计课程解题报告课题负责人名（学号）：郭泉（0643111084）同组成员名单（角色）：独立完成指导教师：左劼评阅成绩：评阅意见：提交报告时间：2008年12月7日-21-课程名称：算法设计学生姓名：郭泉学生学号：0643111084目录《算法设计》课程报告1递归与分治策略4问题描述4算法设计4数据输入4结果输出4问题分析5代码5非递归化：6测试数据及运行结果7复杂度分析7动态规划8问题描述8算法设计8数据输入

2、8结果输出8问题分析8代码9测试数据及运行结果10复杂度分析11和其他算法的比较11贪心算法11问题描述11算法设计11数据输入11结果输出11问题分析12代码12测试数据及运行结果13复杂度分析14和其他算法的比较14回溯法14问题描述14算法设计14数据输入14结果输出15问题分析15代码15测试数据及运行结果16复杂度分析16和其他算法的比较17分支限界法17问题描述17算法设计17数据输入17结果输出17-21-课程名称：算法设计学生姓名：郭泉学生学号：0643111084问题分析18代码18测试

3、数据及运行结果21复杂度分析21和其他算法的比较21-21-课程名称：算法设计学生姓名：郭泉学生学号：0643111084《算法设计》课程解题报告软件工程专业学生郭泉指导老师左劼递归与分治策略排列的字典顺序问题问题描述n个元素{1,2,…,n}有n!个不同的排列。将这n!个排列按字典序排列，并编号0,1,…,n!-1。每个排列的编号为其字典序值。算法设计给定n及n个元素{1,2,…,n}的一个排列，计算出这个排列的字典序值。数据输入由文件input.txt提供输入数据。文件的第一行是元素个数n。接下来的1

4、行是n个元素{1,2,…,n}的一个排列。结果输出将计算出的排列的字典序输出到文件output.txt。输入文件示例input.txt826458173输出文件示例output.txt8227-21-课程名称：算法设计学生姓名：郭泉学生学号：0643111084问题分析对于给定{1,2,…,n}的一个排列arr，设字典序为DictRankn(arr)。容易知道：(arr[0]–1)*(n-1)!<=DictRankn(arr)<=arr[0]*(n-1)!–1既字典序值必大于排列第一个元素arr[0]开始

5、的全排列，且可知DictRankn(arr)是由(arr[0]–1)*(n-1)!和排列除第一个元素外的元素在子列内的字典序组成。由此，我们可以构造递归式：DictRankn(arr)=(arr[0]–1)*(n-1)!+DictRankn-1(arr’)其中，arr’是arr去掉arr[0]后，在原集合{1,2,…,n}中去除arr[0]后组成的集合中的字典序。元集合去掉arr[0]需要将所有的大于arr[0]的值的元素减一，故arr’中的大于arr[0]的值的元素也需要减一，组成n-1个元素的排列。既

6、：arr’[i]=arr[i+1]–1，arr[i+1]>arr[0];arr[i+1]，arr[i+1]#includeusingnamespacestd;//calcthefactorialofnintfactorial(intn){ints=1;for(;n>0;n--)s*=n;returns;}//calcthedictRankofanarrangementintdictRank

7、(int*arr,intn){//definetheedgeif(n==1){//ifonlyoneelement,itthefirstreturn0;}//headingvaluearr[0]inth=arr[0];//newarr-arr'-21-课程名称：算法设计学生姓名：郭泉学生学号：0643111084//shifteveryelementleft,ifgreaterthanarr[0],decreaseby1for(inti=0;ih){arr[i]=

8、arr[i+1]-1;}else{arr[i]=arr[i+1];}//returnrecursioninvokereturn(h-1)*factorial(n-1)+dictRank(arr,n-1);}intmain(){//inoutandoutputfilesifstreamfin("input.txt",ios::in);ofstreamfout("output.txt",ios::out);//readinnand