算法实验报告一.doc

《算法实验报告一.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》课程实验报告专业：计算机科学与技术班级：学号：姓名：日期：2014年10月18日一、实验题目熟悉环境和递归算法二、实验目的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中任一塔座上。3一、实验步骤1、题目一(1)问题分析在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q（n，m）。可以建立q（n,m）的如下递归关系：q（n,m）=1n=1，m=1q（n，n）nm>1据此可设计递归算

3、法。(2)算法描述packagecom.kong;publicclass实验一一{/***@paramargs*///TODOAuto-generatedmethodstubSystem.out.println("结果为："+q(5,6));publicstaticvoidmain(String[]args){}publicstaticintq(intn,intm){if((n<1)

4、

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

6、

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

8、urnq(n,m-1)+q(n-m,m);}}(3)运行结果2、题目二(1)问题分析设R=｛r1,r2,r3,…rn｝是要进行排列的n个元素，Ri=R-｛ri｝集合X中元素的全排列记为perm（X）（ri）perm（X）表示在全排列perm（X）的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：当n=1时，perm（R）=（r），其中r是集合R中唯一的元素；当n>1时，perm（R）由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。(2)算法描述publicclass实验一一一{/***@paramargs*/p

9、ublicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubcharc[]={'1','2','3'};sort(c,0,c.length-1);}publicstaticvoidsort(char[]c,intk,intm){if(k==m){for(inti=0;i<=m;i++){System.out.print(c[i]);}System.out.println();}else{for(inti=0;i<=m;i++){chartemp=c[k];c[k]=c[i];c[i]=temp

10、;sort(c,k+1,m);c[i]=c[k];c[k]=temp;}}3}}(1)运行结果2、题目三(1)问题分析当n=1时，将编号为1的圆盘直接从a移动b即可；当n>1时，加入c，将n-1个较小的圆盘依次移动规则从a到c，然后将剩下的最大圆盘从a移至b，最后在设法将n-1个较小的圆盘依次移动规则从c到b。即将n个圆盘的问题分为两个n-1个圆盘的移动问题，以此类推。(2)算法描述packagecom.kong;publicclass试验一{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAu

11、to-generatedmethodstubhanoi(3,'a','b','c');}publicstaticvoidhanoi(intn,chara,charb,charc){if(n>0){hanoi(n-1,a,c,b);Move(a,b);hanoi(n-1,c,b,a);}}privatestaticvoidMove(chara,charb){System.out.println("从"+a+"移到"+b);}｝(3)运行结果一、出现的问题及解决的方法问题：试验3hanoi调试错误解决方法：算法需要定义move函数，才能实现函数的调用；问题：出现未

12、定义字母解决方法：检查代码是否有错误，