




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
遞歸問(wèn)題的多種解法數(shù)的計(jì)數(shù)我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n):先輸入一個(gè)自然數(shù)n(n≤1000),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:l·不作任何處理:2·在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過(guò)原數(shù)的一半;3·加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再產(chǎn)生自然數(shù)為止?!据斎搿繛橐恍?,一個(gè)整數(shù)n?!据敵觥繛橐恍?,滿足條件數(shù)的個(gè)數(shù)?!緲永斎搿?【樣例輸出】6數(shù)的計(jì)數(shù)【問(wèn)題分析】對(duì)于任意一個(gè)數(shù)X,用變量S表示滿足條件的解的個(gè)數(shù),則S初值為1(即什么也不做);假設(shè)X前可以添加的數(shù)字為Y,則Y取值為[1..XDIV2];假設(shè)Y前可以添加的數(shù)字為Z,則Z取值為[1..YDIV2];……對(duì)于每個(gè)可以取的值,將S:=S+1;遞歸程序如下(解題思路一)。在計(jì)算的過(guò)程中出現(xiàn)了很多重復(fù)計(jì)算,例如計(jì)算X=8,要枚舉[1..4],計(jì)算X=4時(shí),要枚舉[1..2],如果X的值越大,則重復(fù)計(jì)算的就越多,可以使用一個(gè)一維數(shù)組H[1..X],記錄已經(jīng)計(jì)算出來(lái)X的解的個(gè)數(shù),則可以提高運(yùn)算效率。參考程序(解題思路二)解題思路一解題思路二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所能擴(kuò)展的數(shù)據(jù)個(gè)數(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ǔ)上,我們定義一個(gè)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ù)雜度可以進(jìn)一步降低。參考程序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.解題思路五進(jìn)一步分析,可以得到以下的遞推公式:(1)當(dāng)i為奇數(shù)時(shí),h(i)=h(i-1);(2)當(dāng)i為偶數(shù)時(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.遞推算法遞推算法是以初始點(diǎn)的值為基礎(chǔ),用相同的運(yùn)算規(guī)律,依次重復(fù)運(yùn)算,直至運(yùn)算結(jié)束。這種從“起點(diǎn)”重復(fù)相同的方法直至到達(dá)一定“邊界”,猶如單向運(yùn)動(dòng),用循環(huán)可以實(shí)現(xiàn)。遞推關(guān)系是一種簡(jiǎn)潔高效的常見數(shù)學(xué)模型,在這種類型的問(wèn)題中,每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)有一定的關(guān)聯(lián),這種關(guān)聯(lián)一般是通過(guò)一個(gè)遞推關(guān)系式來(lái)表示的。應(yīng)用舉例——斐波那契數(shù)列題目描述斐波那契數(shù)列:0,1,1,2,3,5,8,13,21,34,55,…,從第三項(xiàng)起,每一項(xiàng)都是緊挨著的前兩項(xiàng)的和。用遞歸程序求斐波那契數(shù)列的任意一項(xiàng)。輸入一個(gè)整數(shù):所求的基數(shù)n(1<=n<=35)輸出一個(gè)整數(shù):第n項(xiàng)數(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,請(qǐng)計(jì)算一共有多少種鋪設(shè)的方法。輸入輸入的第一行包含一個(gè)正整數(shù)T(T<=20),表示一共有T組數(shù)據(jù),接著是T行數(shù)據(jù),每行包含一個(gè)正整數(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個(gè)連續(xù)奇數(shù)相加的形式。(2)尋找連續(xù)奇數(shù)的第一個(gè)數(shù)字:若n是奇數(shù),則n3divn則是奇數(shù)中間的那個(gè)數(shù)字,向前遞減2*(ndiv2)則是第一個(gè)數(shù)字。若n是偶數(shù),則n3divn則是奇數(shù)中間的那個(gè)偶數(shù),向前遞減2*(ndiv2)+1則是第一個(gè)數(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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年中國(guó)300#溶劑油數(shù)據(jù)監(jiān)測(cè)報(bào)告
- 2025至2030年中國(guó)領(lǐng)航舵琉璃擺件市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)銀色激光膜市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)郵政客戶服務(wù)跟蹤系統(tǒng)市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)虛擬網(wǎng)計(jì)費(fèi)卡市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)耐曬品藍(lán)色淀市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)磨床油霧收集處理器市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)電顯組合氣扳機(jī)市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)烤地瓜機(jī)市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)油田加熱器市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 空調(diào)安裝報(bào)價(jià)表
- 酒店住宿水單模板2020
- 23J916-1:住宅排氣道(一)
- 公司財(cái)務(wù)審計(jì)報(bào)告怎么做 自來(lái)水公司財(cái)務(wù)審計(jì)報(bào)告
- 2021??低曅聠T工入職培訓(xùn)考試
- 第十章開箱包檢查課件
- 樹蘭中學(xué)拱墅校區(qū)2021分班考卷
- 國(guó)家開放大學(xué)《應(yīng)用概率統(tǒng)計(jì)》綜合作業(yè)1-4參考答案
- 實(shí)驗(yàn)九 三相同步發(fā)電機(jī)的并聯(lián)運(yùn)行
- YY/T 0882-2013麻醉和呼吸設(shè)備與氧氣的兼容性
- JJG 596-2012電子式交流電能表
評(píng)論
0/150
提交評(píng)論