《《算法设计与分析》课程实验报告-熟悉环境和递归算法.doc》由会员分享，可在线阅读，更多相关《《算法设计与分析》课程实验报告-熟悉环境和递归算法.doc（4页珍藏版）》请在三一文库上搜索。
1、算法设计与分析课程实验报告专 业： 网络工程 班 级： 1220551 学 号： 15 姓 名： 王晓鑫 日期： 2013年 10月 20 日一、 实验题目熟悉环境和递归算法二、 实验目的（1） 熟悉Java上机环境;（2） 基本掌握递归算法的原理方法.三、 实验内容1、 将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数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，n1。当最大加数n1不大于1时，任何正整数n只有一种划分形式。 ：q（n，m）
3、=q（n，n），mn。最大加数n1实际上不能大于n。因此，q（1，m）=1。 : q（n，n）=1+q（n，n-1）。正整数n的划分由n1=n的划分和n1n-1的划分组成。 :q（n，m）=q（n，m-1）+q（n-m，m），nm1。正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成。(2) 算法描述 import java.util.Scanner;public class IntPartitioning public static void main(String args) System.out.println(请输入一个正整数：);Scanner scanner
4、=new Scanner(System.in);int n=scanner.nextInt();System.out.println(它的划分个数为：+q(n,n);public static int q(int n,int m)if(n1|m1)return 0;if(n=1|m=1)return 1;if(n1时，perm（R）由（r1）perm（R1），（r2）perm（R2），.（rn）perm（Rn）构成。(2) 算法描述 public class FullArray public static void main(String args) Object list=a,b,c;Per
5、m(list,0,2);public static void Perm(Object list,int k,int m)if(k=m)for(int i=0;i=m;i+)System.out.print(listi);System.out.println();elsefor(int i=k;i1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为两次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。(2)
6、算法描述 import java.util.Scanner;/* * 从A到B */public class Hanoi public static void main(String args) Hanoi hanoi = new Hanoi();Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();hanoi.hanoi(n,A,B,C);public void hanoi(int n,int a,int b,int c) if(n0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);private void move(int a,int b) System.out.println(从 + (char)a+ - + (char)b);(3) 运行结果 五、 出现的问题及解决的方法这次实验主要的问题还是在对算法的掌握上，掌握这些算法要有逻辑好好思考想想理解掌握，而且学了这么多算法，还是没好好掌握，要自己拿到一个新的题目去设计还是很欠缺，最后思想主要还是看书上的，然后自己加了个壳，所以以后还要多思考，多想，多练习。六、