歸納法、遞推法.ppt

《歸納法、遞推法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、歸納法歸納法是由一系列有限的特殊事例得出一般規(guī)律的推理方法。例、求前n個奇數(shù)的和。分析：用S(n)表示前n個數(shù)的和，則S(1)=1,S(2)=1+3=4,S(3)=1+3+5=9,S(4)=1+3+5+7=16,S(5)=1+3+5+7+9=25?？梢钥闯?，當(dāng)1，2，3，4，5時，S(n)=n2?，F(xiàn)在可以歸納出求前n個奇數(shù)的和的一般規(guī)律，即S(n)=n2。上面的歸納法是不完全歸納法，因?yàn)橛伤玫降慕Y(jié)論不一定對任意的n都成立．要證明對所有的n都成立，就必須使用下面介紹的數(shù)學(xué)歸納法．1、證明當(dāng)n取第一個值n0時結(jié)論正確。2、假設(shè)當(dāng)n=k時結(jié)論成立，證明當(dāng)n=k+1時結(jié)論也成立。證明：１、當(dāng)n=１

2、時，左邊＝１，右邊＝１，等式成立。２、假設(shè)當(dāng)n=k時等式成立，即１＋３＋５＋…＋（２k-1)=k2，那么１＋３＋５＋…＋（２k-1）+[2(k+1)-1]=k2+2(k+1)-1=k2+2k+1=(k+1)2例1、Hanoi雙塔問題07年復(fù)賽試題給定A、B、C三根足夠長的細(xì)柱，在A柱上放有2n個中間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；任務(wù)：設(shè)An為2n個圓盤完成上述任務(wù)所需的

3、最少移動次數(shù)，對于輸入的n，輸出An。輸入文件hanoi.in為一個正整數(shù)n，表示在A柱上放有2n個圓盤。輸出文件hanoi.out僅一行，包含一個正整數(shù)，為完成上述任務(wù)所需的最少移動次數(shù)An?！緲永?】hanoi.inhanoi.out12【樣例2】hanoi.inhanoi.out26【限制】對于50%的數(shù)據(jù)，1<=n<=25對于100%的數(shù)據(jù)，1<=n<=200【提示】設(shè)法建立An與An-1的遞推關(guān)系式。解題思路:數(shù)學(xué)歸納+高精度Hanoi單塔的最少移動步數(shù)是2n-1，現(xiàn)在有2層，可以將2層看作1層，便回到了單塔的問題上，每移動想象中的“單個”盤子需要兩步，故Hanoi雙塔=Hanoi

4、單塔*2可得公式：f(n)=2n+1-2高精度只要編個乘法就可以了，不要忘記最后-2beginassign(input,'hanoi.in');assign(output,'hanoi.out');reset(input);rewrite(output);readln(n);ppp(n+1);ifa[1]>=2thena[1]:=a[1]-2elsebegina[1]:=a[1]+8;a[2]:=a[2]-1;end;i:=100;whilea[i]=0doi:=i-1;forj:=idownto1dowrite(a[j]);close(input);close(output);end.va

5、rn,i,j:integer;a:array[1..100]of0..9;procedureppp(k:integer);vari,j,w,s:integer;begina[1]:=1;w:=0;fori:=1tokdo{循環(huán)K次}forj:=1to100dobegins:=a[j]*2+w;a[j]:=smod10;w:=sdiv10;end;end;例2、乘火車(98年復(fù)賽試題)火車從始發(fā)站（稱為第1站）開出，在始發(fā)站上車的人數(shù)為a，然后到達(dá)第2站，在第2站有人上、下車，但上、下車的人數(shù)相同，因此在第2站開出時（即在到達(dá)第3站之前）車上的人數(shù)保持為a人。從第3站起（包括第3站）上、下車的

6、人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點(diǎn)站的前一站（第n-1站），都滿足此規(guī)律。現(xiàn)給出的條件是：共有n個車站，始發(fā)站上車的人數(shù)為a，最后一站下車的人數(shù)是m（全部下車）。試問第x站開出時車上的人數(shù)是多少？輸入文件chc.in：一行四個整數(shù)a，n，m和x（中間用空格隔開）輸出文件chc.out：一行一個整數(shù)（從x站開出時車上的人數(shù)）樣例:chc.in46324chc.out18分析:典型的數(shù)學(xué)題為了找規(guī)律，我們建立一個表:站號123456開車時人數(shù)num[]aa2a2a+b3a+2b4a+4b上車人數(shù)in[]aba+ba+2b2a+3b3a+5b

7、下車人數(shù)out[]0bba+ba+2b2a+3b規(guī)律出來了，設(shè)第k(k>=3)站時上車人數(shù)為f[k-2]*a+f[k-1]*b(f[k]={1,1,2,3,5,8,13,21..}為fibonacci數(shù)列)num[k]=a+in[2]-out[2]+in[3]-out[3]...+in[k]-out[k]而in[2]=out[3],in[3]=out[4]...故num[k]=a-out[2]+in[k]=a