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

1、，每次只能移動(dòng)1個(gè)盤子,步可走 1級或2級。顯遞歸應(yīng)用一：漢諾塔問題將5個(gè)大小不等的盤子從位置1移到位置3 （可以借助位置2）且大盤子不能壓在小盤子上面，問如何移法？（用遞歸過程完成）123Program Han oi;Var total:i nteger;Procedure move( n, a,b,c:i nteger);Begi n If n=1 the n write(a,'',c)Else begi nMove( n-1,a,c,b); Writeln(a,'',c);Move( n-1,b,a,c);En d;En d;Beg inRead(tota

2、l);Move(total,1,2,3);End.遞歸應(yīng)用二：上樓梯問題一個(gè)n層的臺階(1<=n<=1O0 , 一個(gè)人從臺階下走到臺階上, 示出所有方案，并統(tǒng)計(jì)其總數(shù)。如n=4時(shí)，有下列方案：1 1 1 11 1 21 2 12 1 12 2方案總數(shù)：total=5Program taijie;Var way:arraybyte of byte; Total, nn teger;Procedure prin t(s:byte);Var i:byte;Begi nFor i:=1 to s do write(wayi, ');Writeln;Total:=total+1;En

3、d;Procedure search(s,n:byte);BeginIf n=0 then print(s)Else begin Ways+1:=1; Search(s+1,n-1); If n>1 then BeginWays+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ù) 問題描述 我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù) ( 包含輸入的自然數(shù) n):先輸入一個(gè)自然數(shù)n(n < 100

4、0)，然后對此自然數(shù)按照如下方法進(jìn)行處理 I 不作任何處理：2在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；3加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。 樣例 輸入： 6滿足條件的數(shù)為 6 ( 此部分不必輸出 )162612636136輸出： 6輸入：10 滿足條件的數(shù)為 14( 此部分不必輸出 )101102101210310131041014102410124105101510251012510解法一：遞推算法：beginRead(n);Fillchar(f,sizeof(f),0);F1:=1;For i:=2 to n doFor j:=1 to I div 2

5、 doFi:=fi+fj;End;Write(fn);End;解法二：遞歸算法Procedure count(x:integer);Var i:integer;BeginInc(num);For i:=1 to x div 2 doCount(i);End;BeginNum:=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+15=2+35=2+2+12、任何一個(gè)正整數(shù)都可以用 2 的冪次方表示 .例如：137=2A7+2A3+2A0同時(shí)約定次方用括號來表示，即aAb可表示為a(b) 由此可知,137可表示為：2(7)+2(3)+2(0)進(jìn)一步： 7=2A2+2+2A0(2A1 用 2表示)3=2+2A0所以最后 137可表示為 ：2(2(2)+2+2(0)+2(2+2(0)+2(0) 又如：1315=2八10+2八8+2八5+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*2A7+0*2A6+0*2A5+0*2A