《算法設(shè)計(jì)與分析》課程實(shí)驗(yàn)報(bào)告-熟悉環(huán)境和遞歸算法

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

1、算法設(shè)計(jì)與分析課程實(shí)驗(yàn)報(bào)告專 業(yè)： 網(wǎng)絡(luò)工程 班 級： 1220551 學(xué) 號(hào)： 15 姓 名： 王曉鑫 日期： 2013年 10月 20 日一、 實(shí)驗(yàn)題目熟悉環(huán)境和遞歸算法二、 實(shí)驗(yàn)?zāi)康模?） 熟悉Java上機(jī)環(huán)境;（2） 基本掌握遞歸算法的原理方法.三、 實(shí)驗(yàn)內(nèi)容1、 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 2、 設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。3、 Hanoi塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起

2、。各圓盤從小到大編號(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) 問題分析正整數(shù)n的不同的劃分個(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，n1。當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式。 ：q（n，m）

3、=q（n，n），mn。最大加數(shù)n1實(shí)際上不能大于n。因此，q（1，m）=1。 : q（n，n）=1+q（n，n-1）。正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。 :q（n，m）=q（n，m-1）+q（n-m，m），nm1。正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1m-1的劃分組成。(2) 算法描述 import java.util.Scanner;public class IntPartitioning public static void main(String args) System.out.println(請輸入一個(gè)正整數(shù)：);Scanner scanner

4、=new Scanner(System.in);int n=scanner.nextInt();System.out.println(它的劃分個(gè)數(shù)為：+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時(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;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時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見，n個(gè)圓盤的移動(dòng)問題可分為兩次n-1個(gè)圓盤的移動(dòng)問題，這又可以遞歸地用上述方法來做。(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) 運(yùn)行結(jié)果 五、 出現(xiàn)的問題及解決的方法這次實(shí)驗(yàn)主要的問題還是在對算法的掌握上，掌握這些算法要有邏輯好好思考想想理解掌握，而且學(xué)了這么多算法，還是沒好好掌握，要自己拿到一個(gè)新的題目去設(shè)計(jì)還是很欠缺，最后思想主要還是看書上的，然后自己加了個(gè)殼，所以以后還要多思考，多想，多練習(xí)。六、