1、 算法設計與分析課程實驗報告專 業： 班 級： 學 號： 姓 名： 日期： 2014年 11月 10日一、 實驗題目熟悉環境和遞歸算法二、 實驗目的（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個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現要求將塔座a上的

2、圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則： 規則1：每次只能移動1個圓盤； 規則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規則3：在滿足移動規則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。四、 實驗步驟 (一) 正整數劃分問題 （1）、問題分析 在正整數n的不同劃分中，將最大加數n1不大于m的劃分個數記作q(n，m)。可以建立q(n，m)的如下遞歸關系。1、q(n，1)=1，n>=1。當最大加數n1不大于1時，任何正整數n只有一種劃分形式，即。2、q(n，m)=q(n，n)，m>=n。最大加數n1實際上不能大于n，因此，q(1，m)=

3、1。3、q(n，n)=1+q(n，n-1)。正整數n的劃分由n1=n的劃分和n1<=n-1的劃分組成。4、q(n，m)= q(n，m-1)+q(n-m，m)，n>m>1。正整數n的最大加數n1不大于m的劃分由n1=m的劃分和n1<=m-1的劃分組成。（2）、算法描述public class 張萌 /* * param args */public static void main(String args) / TODO Auto-generated method stub System.out.println(q(2,2);public static int q(int

4、n,int m)if(n<1)|(m<1) return 0;if(n=1)|(m=1) return 1;if(n<m) return q(n,n);if(n=m) return q(n,m-1)+1;return q(n,m-1)+q(n-m,m); (3) 、運行結果（二）n個元素全排列問題（1）、問題分析 設R=r1，r2,rn是要進行排列的n個元素，Ri=Rri。集合X中元素的全排列記為perm(X).(ri)perm(X)表示在全排列perm(X)每一個排列前加上前綴ri，得到的排列。R的全排列可歸納定義為如下：當n=1時，perm（R）=（r），其中r是集合R中

5、唯一的元素;當n>1時，perm（R）由（r1）perm（R1），（r2）perm（R1），（rn）quan（Rn）構成。（2）、算法描述public class 張萌 /* * param args */public static void main(String args) / TODO Auto-generated method stub String list="a","b","c","d" perm(list,0,list.length-1);public static void perm(Obje

6、ctlist,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;i<=m;i+)MyMath.swap(list,k,i);perm(list,k+1,m);MyMath.swap(list,k,i);public static class MyMathpublic static void swap(Object list, int k, int i) / TODO Auto-generated method stubObject t

7、;t=listk;listk=listi;listi=t; （3）、運行結果 （三）漢諾塔問題（1）、問題分析 當n=1時，只要將編號為1的圓盤從塔座a直接移至b座上即可。當n>1時，需要利用塔座c作為輔助塔座。此時若能設法將n-1個較小的圓盤依照移動規則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至b，最后，再設法將n-1個較小的圓盤依照移動規則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可以分為兩次n-1個圓盤移動的問題,這又可以遞歸地用上述方法來做。 （2）、算法描述public class 張萌 /* * param args */public static void main(String args) / TODO Auto-generated method stubhanoi(4,'a','b','c');public static void hanoi(int n,int a,int b,int c) if (n>0) hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,c,b,a); private static void mo