算法分析與設(shè)計(jì)

算法分析與設(shè)計(jì)算法分析與設(shè)計(jì)算法分析與設(shè)計(jì)資料僅供參考文件編號：2022年4月算法分析與設(shè)計(jì)版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：《算法設(shè)計(jì)與分析》課程實(shí)驗(yàn)報告專業(yè)：班級：學(xué)號：姓名：日期：2014年11月10日實(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， 其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個數(shù)。2、設(shè)計(jì)一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。3、Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則： 規(guī)則1：每次只能移動1個圓盤； 規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。實(shí)驗(yàn)步驟(一)正整數(shù)劃分問題（1）、問題分析在正整數(shù)n的不同劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n，m)。可以建立q(n，m)的如下遞歸關(guān)系。1、q(n，1)=1，n>=1。當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即。2、q(n，m)=q(n，n)，m>=n。最大加數(shù)n1實(shí)際上不能大于n，因此，q(1，m)=1。3、q(n，n)=1+q(n，n-1)。正整數(shù)n的劃分由n1=n的劃分和n1<=n-1的劃分組成。4、q(n，m)=q(n，m-1)+q(n-m，m)，n>m>1。正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1<=m-1的劃分組成。（2）、算法描述publicclass張萌{ /** *@paramargs */ publicstaticvoidmain(String[]args){ ri)perm(X)表示在全排列perm(X)每一個排列前加上前綴ri，得到的排列。R的全排列可歸納定義為如下：當(dāng)n=1時，perm（R）=（r），其中r是集合R中唯一的元素;當(dāng)n>1時，perm（R）由（r1）perm（R1），（r2）perm（R1）………，（rn）quan（Rn）構(gòu)成。（2）、算法描述publicclass張萌{ /** *@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstubString[]list={"a","b","c","d"};perm(list,0,; } publicstaticvoidperm(Object[]list,intk,intm) { if(k==m) { for(inti=0;i<=m;i++) } else for(inti=k;i<=m;i++) { (list,k,i); perm(list,k+1,m); (list,k,i); } } publicstaticclassMyMath { publicstaticvoidswap(Object[]list,intk,inti) { //TODOAuto-generatedmethodstub Objectt; t=list[k]; list[k]=list[i]; list[i]=t; } }}（3）、運(yùn)行結(jié)果（三）漢諾塔問題（1）、問題分析當(dāng)n=1時，只要將編號為1的圓盤從塔座a直接移至b座上即可。當(dāng)n>1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可以分為兩次n-1個圓盤移動的問題,這又可以遞歸地用上述方法來做。（2）、算法描述publicclass張萌{ /** *@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub hanoi(4,'a','b','c'); } publicstaticvoidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}