《《算法設(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í)。六、