Pascal講授遞歸問題多種解法

遞歸問題的多種解法數(shù)的計數(shù)我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n):先輸入一個自然數(shù)n(n≤1000)，然后對此自然數(shù)按照如下方法進行處理：l·不作任何處理:2·在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半;3·加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再產(chǎn)生自然數(shù)為止。【輸入】為一行，一個整數(shù)n?！据敵觥繛橐恍?，滿足條件數(shù)的個數(shù)。【樣例輸入】6【樣例輸出】6數(shù)的計數(shù)【問題分析】對于任意一個數(shù)X，用變量S表示滿足條件的解的個數(shù)，則S初值為1（即什么也不做）；假設(shè)X前可以添加的數(shù)字為Y，則Y取值為[1..XDIV2];假設(shè)Y前可以添加的數(shù)字為Z，則Z取值為[1..YDIV2];……對于每個可以取的值，將S:=S+1;遞歸程序如下（解題思路一）。在計算的過程中出現(xiàn)了很多重復(fù)計算，例如計算X=8，要枚舉[1..4],計算X=4時，要枚舉[1..2]，如果X的值越大，則重復(fù)計算的就越多，可以使用一個一維數(shù)組H[1..X]，記錄已經(jīng)計算出來X的解的個數(shù)，則可以提高運算效率。參考程序（解題思路二）解題思路一解題思路二programacm21102;varn,i,s:longint;procedurejisuan(x:longint);vari:longint;begin

fori:=1toxdiv2do

begin

s:=s+1;

if(idiv2)>0thenjisuan(i)

end;end;begin

readln(n);

s:=1;

jisuan(n);

writeln(s);end.programacm21102;varn,i:longint;h:array[1..1000]oflongint;procedurejisuan(x:longint);vari:longint;beginifh[x]>0thenexit;h[x]:=1;fori:=1toxdiv2dobeginjisuan(i);h[x]:=h[x]+h[i];end;end;beginreadln(n);fillchar(h,sizeof(h),0);jisuan(n);writeln(h[n]);end.解題思路三采用遞推思路。用H(n)表示自然數(shù)n所能擴展的數(shù)據(jù)個數(shù)，則h(1)=1;h(2)=2;h(3)=2;h(4)=4;h(5)=4;h(6)=6;h(7)=6;……歸納遞推公式：h(i)=1+h(1)+h(2)+……+h(idiv2);programacm21102;varn,i,j:longint;h:array[1..1000]oflongint;beginreadln(n);fillchar(h,sizeof(h),0);fori:=1tondobeginh[i]:=1;forj:=1toidiv2doh[i]:=h[i]+h[j];end;writeln(h[n]);end.解題思路四在思路三的基礎(chǔ)上，我們定義一個S，令S(x)=h(1)+h(2)+……+h(x);則S(x-1)=h(1)+h(2)+……+h(x-1);h(x)=S(x)-S(x-1);h(x)=h(i)=1+h(1)+h(2)+……+h(idiv2)=1+S(idiv2);算法的復(fù)雜度可以進一步降低。參考程序programacm21102;varh,s:array[1..1001]oflongint;i:longint;beginreadln(n);h[1]:=1;s[1]:=1;fori:=2tondobeginh[i]:=1+s[idiv2];s[i]:=s[i-1]+h[i];end;writeln(h[n]);end.解題思路五進一步分析，可以得到以下的遞推公式：(1)當(dāng)i為奇數(shù)時，h(i)=h(i-1);(2)當(dāng)i為偶數(shù)時，h(i)=h(i-1)+h(idiv2);programacm21102;varh:array[1..1001]oflongint;n,i:longint;beginreadln(n);h[1]:=1;fori:=2tondoifimod2=0thenh[i]:=h[i-1]+h[idiv2]elseh[i]:=h[i-1];writeln(h[n]);end.遞推算法遞推算法是以初始點的值為基礎(chǔ)，用相同的運算規(guī)律，依次重復(fù)運算，直至運算結(jié)束。這種從“起點”重復(fù)相同的方法直至到達一定“邊界”，猶如單向運動，用循環(huán)可以實現(xiàn)。遞推關(guān)系是一種簡潔高效的常見數(shù)學(xué)模型，在這種類型的問題中，每個數(shù)據(jù)項都和它前面的若干個數(shù)據(jù)項有一定的關(guān)聯(lián)，這種關(guān)聯(lián)一般是通過一個遞推關(guān)系式來表示的。應(yīng)用舉例——斐波那契數(shù)列題目描述斐波那契數(shù)列:0,1,1,2,3,5,8,13,21,34,55,…，從第三項起，每一項都是緊挨著的前兩項的和。用遞歸程序求斐波那契數(shù)列的任意一項。輸入一個整數(shù)：所求的基數(shù)n(1<=n<=35)輸出一個整數(shù)：第n項數(shù)據(jù)的值。樣例輸入10樣例輸出34遞歸與遞推算法比較programacm23145;vara:array[1..40]ofint64;n,i,t:longint;beginreadln(n);a[1]:=0;a[2]:=1;fori:=3tondoa[i]:=a[i-1]+a[i-2];writeln(a[n]);end.programacm23145;varf:array[1..40]oflongint;n:longint;functiondigui(x:longint):longint;beginifx=1thenf[x]:=0elseifx=2thenf[x]:=1elsef[x]:=digui(x-1)+digui(x-2);digui:=f[x];end;beginreadln(n);writeln(digui(n));end.應(yīng)用舉例——貼瓷磚題目描述有一塊大小是2*n的墻面，現(xiàn)在需要用2種規(guī)格的瓷磚鋪滿，瓷磚規(guī)格分別是2*1和2*2，請計算一共有多少種鋪設(shè)的方法。輸入輸入的第一行包含一個正整數(shù)T（T<=20），表示一共有T組數(shù)據(jù)，接著是T行數(shù)據(jù)，每行包含一個正整數(shù)N（N<=30），表示墻面的大小是2行N列。輸出輸出一共有多少種鋪設(shè)的方法，每組數(shù)據(jù)的輸出占一行。樣例輸入32812樣例輸出31712731題目分析programp1059;vart,i,j,k,n:longint;a:array[1..30]oflongint;beginreadln(t);a[1]:=1;a[2]:=3;fori:=3to30doa[i]:=a[i-1]+2*a[i-2];fori:=1totdobeginreadln(n);writeln(a[n]);end;end.25323:連續(xù)奇數(shù)和樣例輸入4樣例輸出13151719題目分析觀察給出的樣例，尋找規(guī)律。（1）n的立方可以表示成n個連續(xù)奇數(shù)相加的形式。（2）尋找連續(xù)奇數(shù)的第一個數(shù)字：若n是奇數(shù)，則n3divn則是奇數(shù)中間的那個數(shù)字，向前遞減2*(ndiv2)則是第一個數(shù)字。若n是偶數(shù)，則n3divn則是奇數(shù)中間的那個偶數(shù)，向前遞減2*(ndiv2)+1則是第一個數(shù)字。核心代碼s:=n*n*n;ifodd(n)thenbegintmp:=sdivn;tmp:=tmp-2*(ndiv2);write(tmp);fori:=2tondobegintmp:=tmp+2;write('',tmp);end;writeln;endn為偶數(shù)：begintmp:=sdivn;tmp:=tmp-2*(ndiv2)+1;write(tmp);fori:=2tondobegintmp:=tmp+2;write('',tmp);end;writeln;end;end.programacm25323;varn,i,j:longint;s,tmp:qword;beginreadln(n);s:=n*n*n