信息奧訓(xùn)班講義五遞歸

1、遞歸應(yīng)用一：漢諾塔問(wèn)題將5個(gè)大小不等的盤(pán)子從位置1移到位置3（可以借助位置2），每次只能移動(dòng)1個(gè)盤(pán)子，且大盤(pán)子不能壓在小盤(pán)子上面，問(wèn)如何移法？（用遞歸過(guò)程完成） 1 2 3Program Hanoi; Var total:integer; Procedure move(n,a,b,c:integer); Begin If n=1 then write(a,c) Else begin Move(n-1,a,c,b); Writeln(a,c); Move(n-1,b,a,c); End; End; Begin Read(total); Move(total,1,2,3); End.遞歸應(yīng)用二：上

2、樓梯問(wèn)題一個(gè)n層的臺(tái)階（1=n1 then Begin Ways+1:=2; Search(s+1,n-2); End; End; End; BeginWrite(step:);Readln(n);Total:=0;Search(0,n);Writeln(total=,total); End.數(shù)的計(jì)數(shù) 問(wèn)題描述 我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n): 先輸入一個(gè)自然數(shù)n(n1000)，然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理 l不作任何處理: 2在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過(guò)原數(shù)的一半; 3加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。 樣例 輸入：6 滿(mǎn)足

3、條件的數(shù)為 6 (此部分不必輸出) 16 26 126 36 136 輸出：6輸入：10滿(mǎn)足條件的數(shù)為 14(此部分不必輸出) 101102101210310131041014102410124105101510251012510解法一：遞推算法：beginRead(n);Fillchar(f,sizeof(f),0);F1:=1;For i:=2 to n do For j:=1 to I div 2 do Fi:=fi+fj;End;Write(fn);End;解法二：遞歸算法Procedure count(x:integer);Var i:integer;BeginInc(num);Fo

4、r i:=1 to x div 2 do Count(i);End;Begin Num:=0;Read(n);Count(n);Write(num);End;練習(xí)：1、分解因式,輸入n，輸出它的所有分解因式后的式子。5=1+45=1+1+35=1+1+1+25=1+1+1+1+1 5=2+3 5=2+2+12、任何一個(gè)正整數(shù)都可以用2的冪次方表示.例如: 137=27+23+20同時(shí)約定次方用括號(hào)來(lái)表示,即ab可表示為a(b)由此可知,137可表示為:2(7)+2(3)+2(0)進(jìn)一步: 7=22+2+20 (21用2表示) 3=2+20所以最后137可表示為:2(2(2)+2+2(0)+2(2+2(0)+2(0)又如:1315=210+28+25+2+1所以1315最后可表示為:2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)輸入:正整數(shù)(n=20000)輸出:符合約定的n的0,2表示(在表示中不能有空格)137=10001001 =1*27+0*26+0*25+0*24+1*23+0*22+0*21+1*20=27+23+20=2(22+2+20)+2(2+20)+20=2(2(2)+2+2(