《算法設計與分析》課程實驗報告-熟悉環(huán)境和遞歸算法

算法設計與分析課程實驗報告專 業(yè)： 網絡工程 班 級： 1220551 學 號： 15 姓 名： 王曉鑫 日期： 2013年 10月 20 日一、 實驗題目熟悉環(huán)境和遞歸算法二、 實驗目的（1） 熟悉Java上機環(huán)境;（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,現(xiàn)要求將塔座a上的圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則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）=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），n>m>1。正整數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=new Scanner(System.in);int n=scanner.nextInt();System.out.println("它的劃分個數為："+q(n,n);public static int q(int 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) 運行結果 2、 題目二(1) 問題分析 設R=r1，r2，rn是要進行排列的n個元素，Ri=R-ri。集合X中元素的全排列記為perm（X）。（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) 算法描述 public class FullArray public static void main(String args) Object list=a,b,c;Perm(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;i<=m;i+)swap(list,k,i);Perm(list,k+1,m);swap(list,k,i);public static void swap(Object list,int k,int i)Object temp;temp=listk;listk=listi;listi=temp;(3) 運行結果 3、 題目三(1) 問題分析當n=1時，問題比較簡單，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當n>1時，需要利用塔座c作為輔助塔座。此時若能設法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為兩次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。(2) 算法描述 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(n>0)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) 運行結果 五、 出現(xiàn)的問題及解決的方法這次實驗主要的問題還是在對算法的掌握上，掌握這些算法要有邏輯好好思考想想理解掌握，而且學了這么多算法，還是沒好好掌握，要自己拿到一個新的題目去設計還是很欠缺，最后思想主要還是看書上的，然后自己加了個殼，所以以后還要多思考，多想，多練習。六、