《算法设计与分析》课程实验报告-熟悉环境和递归算法.doc

《《算法设计与分析》课程实验报告-熟悉环境和递归算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》课程实验报告专业：网络工程班级：1220551学号：15姓名：王晓鑫日期：2013年10月20日一、实验题目熟悉环境和递归算法二、实验目的（1）熟悉Java上机环境;（2）基本掌握递归算法的原理方法.三、实验内容1、将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。2、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。3、Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大

2、编号为1,2,…,n,现要求将塔座a上的圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。四、实验步骤1、题目一(1)问题分析正整数n的不同的划分个数称为正整数n的划分数，记作p（n）。在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q（n，m）。可以建立q（n，m）的如下递归关系。①：q（n，1）=1，n≥1。当最大加数n1不大于1时，任何正整数n只有一种划分形式。②：q（n，m）=q（n，

3、n），m≥n。最大加数n1实际上不能大于n。因此，q（1，m）=1。③:q（n，n）=1+q（n，n-1）。正整数n的划分由n1=n的划分和n1≤n-1的划分组成。④:q（n，m）=q（n，m-1）+q（n-m，m），n>m>1。正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。(1)算法描述importjava.util.Scanner;publicclassIntPartitioning{publicstaticvoidmain(String[]args){System.out.println("请输入一个正整数：");Scannerscanner=new

4、Scanner(System.in);intn=scanner.nextInt();System.out.println("它的划分个数为："+q(n,n));}publicstaticintq(intn,intm){if(n<1

5、

6、m<1)return0;if(n==1

7、

8、m==1)return1;if(n

9、（ri）perm（X）表示在全排列perm（X）的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：当n=1时，perm（R）=（r），其中r是集合R中唯一的元素。当r>1时，perm（R）由（r1）perm（R1），（r2）perm（R2），...（rn）perm（Rn）构成。(2)算法描述publicclassFullArray{publicstaticvoidmain(String[]args){Object[]list={'a','b','c'};Perm(list,0,2);}publicstaticvoidPerm(Object[]list,intk,intm){

10、if(k==m){for(inti=0;i<=m;i++)System.out.print(list[i]);System.out.println();}else{for(inti=k;i<=m;i++){swap(list,k,i);Perm(list,k+1,m);swap(list,k,i);}}}publicstaticvoidswap(Object[]list,intk,inti){Objecttemp;temp=list[k];list[k]=list[i];list[i]=temp;}}(1)运行结果2、题目三(1)问题分析当n=1时，问题比较简单，只要将编号为1的圆盘从塔

11、座a直接移至塔座b上即可。当n>1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为两次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。(2)算法描述importjava.util.Scanner;/**从A到B*/publicclassHan