算法實(shí)驗(yàn)報(bào)告一(共4頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析課程實(shí)驗(yàn)報(bào)告專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 學(xué) 號(hào)： 姓 名： 日期：2014 年 10月18 日一、 實(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塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從

2、小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。四、 實(shí)驗(yàn)步驟1、 題目一(1) 問(wèn)題分析在正整數(shù)n的所有不同的劃分中，將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q（n，m）?？梢越（n,m） 的如下遞歸關(guān)系：q（n,m）= 1 n=1，m=1 q（n，n） n<m 1+q(n,n-1) n=m q(n,m-1)+q(n-m,m) n>m>1據(jù)此可設(shè)計(jì)遞歸算

3、法。(2) 算法描述 package com.kong;public class 實(shí)驗(yàn)一一 /* * param args */ TODO Auto-generated method stubSystem.out.println("結(jié)果為："+q(5,6);public static void main(String args) 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) re

4、turn q(n, m-1)+1;return q(n, m-1)+q(n-m, m); (3) 運(yùn)行結(jié)果 2、 題目二(1) 問(wèn)題分析 設(shè)R=r1,r2,r3,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri 集合X中元素的全排列記為perm（X）（ri）perm（X）表示在全排列perm（X）的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：當(dāng)n=1時(shí)，perm（R）=（r），其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm（R）由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)構(gòu)成。(2) 算法描述public class 實(shí)驗(yàn)一一一 /* * pa

5、ram args */public static void main(String args) / TODO Auto-generated method stubchar c='1','2','3'sort (c,0,c.length-1);public static void sort (charc,int k,int m)if(k=m)for(int i=0;i<=m;i+)System.out.print(ci);System.out.println();elsefor(int i=0;i<=m;i+)char temp=ck;

6、ck=ci;ci=temp;sort(c,k+1,m);ci=ck;ck=temp;(3) 運(yùn)行結(jié)果 3、 題目三(1) 問(wèn)題分析當(dāng)n=1時(shí)，將編號(hào)為1的圓盤(pán)直接從a移動(dòng)b即可；當(dāng)n>1時(shí)，加入c，將n-1個(gè)較小的圓盤(pán)依次移動(dòng)規(guī)則從a到c，然后將剩下的最大圓盤(pán)從a移至b，最后在設(shè)法將n-1個(gè)較小的圓盤(pán)依次移動(dòng)規(guī)則從c到b。即將n個(gè)圓盤(pán)的問(wèn)題分為兩個(gè)n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，以此類(lèi)推。(2) 算法描述 package com.kong;public class 試驗(yàn)一 /* * param args */public static void main(String args) / TODO Auto-generated method stubhanoi(3, 'a', 'b', 'c');public static void hanoi(int n, char a, char b, char c) if (n > 0) hanoi(n-1, a, c, b);Move(a, b);hanoi(n-1, c, b, a);private static void Move(char a, char b) System.out.println("從" + a + "移到" + b)