《《算法設(shè)計(jì)與分析》課程實(shí)驗(yàn)報(bào)告-熟悉環(huán)境和遞歸算法》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》課程實(shí)驗(yàn)報(bào)告-熟悉環(huán)境和遞歸算法（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 《算法設(shè)計(jì)與分析》課程實(shí)驗(yàn)報(bào)告 專 業(yè)： 網(wǎng)絡(luò)工程 班 級(jí)： 1220551 學(xué) 號(hào)： 15 姓 名： 王曉鑫 日期： 2013年 10月 20 日 一、 實(shí)驗(yàn)題目 熟悉環(huán)境和遞歸算法 二、 實(shí)驗(yàn)?zāi)康? （1） 熟悉Java上機(jī)環(huán)境; （2） 基本掌握遞歸算法的原理方法. 三、 實(shí)驗(yàn)內(nèi)容 1、 將正整數(shù)n表示成一系列正整數(shù)之和： n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的

2、不同劃分個(gè)數(shù)。 2、 設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。 3、 Hanoi塔問(wèn)題 設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則1：每次只能移動(dòng)1個(gè)圓盤； 規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。 四、 實(shí)驗(yàn)步驟 1、 題目一 (1) 問(wèn)題分析 正整數(shù)n的

3、不同的劃分個(gè)數(shù)稱為正整數(shù)n的劃分?jǐn)?shù)，記作p（n）。 在正整數(shù)n的所有不同的劃分中，將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q（n，m）?？梢越（n，m）的如下遞歸關(guān)系。 ① ：q（n，1）=1，n≥1。 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式。 ② ：q（n，m）=q（n，n），m≥n。 最大加數(shù)n1實(shí)際上不能大于n。因此，q（1，m）=1。 ③ : q（n，n）=1+q（n，n-1）。 正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。 ④ :q（n，m）=q（n，m-1）+q（n-m，m），n>m>1。 正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1

4、=m的劃分和n1≤m-1的劃分組成。 (2) 算法描述 import java.util.Scanner; public class IntPartitioning { public static void main(String[] args) { System.out.println("請(qǐng)輸入一個(gè)正整數(shù)："); Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); System.out.println("它的劃分個(gè)數(shù)為："+q(n,n)); }

5、 public static int q(int n,int m) { if(n<1||m<1) return 0; if(n==1||m==1) return 1; if(n

6、rm（X）。（ri）perm（X）表示在全排列perm（X）的每一個(gè)排列前加上前綴ri得到的排列。R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm（R）=（r），其中r是集合R中唯一的元素。 當(dāng)r>1時(shí)，perm（R）由（r1）perm（R1），（r2）perm（R2），...（rn）perm（Rn）構(gòu)成。 (2) 算法描述 public class FullArray { public static void main(String[] args) { Object[] list={a,b,c}; Perm(list,0,2); } pu

7、blic static void Perm(Object [] list,int k,int m) { if(k==m) { for(int i=0;i<=m;i++) System.out.print(list[i]); System.out.println(); } else { for(int i=k;i<=m;i++) { swap(list,k,i); Perm(list,k+1,m); swap(list,k,i); } } } public stat

8、ic void swap(Object[] list,int k,int i) { Object temp; temp=list[k]; list[k]=list[i]; list[i]=temp; } } (3) 運(yùn)行結(jié)果 3、 題目三 (1) 問(wèn)題分析 當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n>1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依

9、照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見，n個(gè)圓盤的移動(dòng)問(wèn)題可分為兩次n-1個(gè)圓盤的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。 (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();

10、 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) 運(yùn)行結(jié)果 五、 出現(xiàn)的問(wèn)題及解決的方法 這次實(shí)驗(yàn)主要的問(wèn)題還是在對(duì)算法的掌握上，掌握這些算法要有邏輯好好思考想想理解掌握，而且學(xué)了這么多算法，還是沒(méi)好好掌握，要自己拿到一個(gè)新的題目去設(shè)計(jì)還是很欠缺，最后思想主要還是看書上的，然后自己加了個(gè)殼，所以以后還要多思考，多想，多練習(xí)。 六、