《算法設計與分析》課程實驗報告-熟悉環(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)的問題及解決的方法這次實驗主要的問題還是在對算法的掌握上,掌握這些算法要有邏輯好好思考想想理解掌握,而且學了這么多算法,還是沒好好掌握,要自己拿到一個新的題目去設計還是很欠缺,最后思想主要還是看書上的,然后自己加了個殼,所以以后還要多思考,多想,多練習。六、