遞推cc教學(xué)內(nèi)容

遞推cc2解題思路: 假定A、B、C、D、E五人的編號分別為1、2、3、4、5，整數(shù)數(shù)組fish[k]表示第k個人所看到的魚數(shù)。fish[1]表示A所看到的魚數(shù)，fish[2]表示B所看到的魚數(shù)…… fish[1]為五人合伙捕魚的總魚數(shù) fish[2]=(fish[1]-1)*4/5 fish[3]=(fish[2]-1)*4/5 fish[4]=(fish[3]-1)*4/5 fish[5]=(fish[4]-1)*4/53寫成一般式

fish[i]=(fish[i-1]–1)*4/5

i=2,3,…,5

這個公式可用于知A看到的魚數(shù)去推算B看到的，再推算C看到的，…….?，F(xiàn)在要求的是A看到的，能否倒過來，先知E看到的再反推D看到的，……，直到A看到的。為此將上式改寫為：

fish[i-1]=fish[i]*5/4+1 i=5,4,…,24分析上式１.當(dāng)i=5時，fish[5]表示E醒來所看到的魚數(shù)，該數(shù)應(yīng)滿足被５整除后余１，即 fish[5]%5==12.當(dāng)i=5時，fish[i-1]表示D醒來所看到的魚數(shù)，這個數(shù)既要滿足 fish[4]=fish[5]*5/4+1又要滿足 fish[4]%5==1顯然，fish[4]不能不是整數(shù)，這個結(jié)論同樣可以用至fish[3],fish[2]和fish[1]53.按題意要求5人合伙捕到的最少魚數(shù)，可以從小往大枚舉，可以先讓E所看到的魚數(shù)最少為6條，即fish[5]初始化為6來試，之后每次增加5再試，直至遞推到fish[1]得整數(shù)且除以5之后的余數(shù)為1。根據(jù)上述思路，我們可以構(gòu)思如下的程序框圖：67該圖可分為三部分(1)

是說明部分：包含定義數(shù)組fish[6]，并初始化為1和定義循環(huán)控制變量i，并初始化為0。(2)

是do….while直到型循環(huán)，其循環(huán)體又含兩塊：

(2).1

是枚舉過程中的fish[5]的初值設(shè)置，一開始fish[5]=1+5;以后每次增5。

(2).2

是一個for循環(huán)，i的初值為4，終值為1，步長為-1，該循環(huán)的循環(huán)體是一個分支語句，如果fish[i+1]不能被4整除，則跳出for循環(huán)（使用break語句）;否則，從fish[i+1]算出fish[i]。8 當(dāng)由break語句讓程序退出循環(huán)時，意味著某人看到的魚數(shù)不是整數(shù)，當(dāng)然不是所求，必須令fish[5]加5后再試，即重新進(jìn)入直到型循環(huán)dowhile的循環(huán)體。 當(dāng)著正常退出for循環(huán)時，一定是控制變量i從初值4，一步一步執(zhí)行到終值1，每一步的魚數(shù)均為整數(shù)，最后i=0，表示計算完畢，且也達(dá)到了退出直到型循環(huán)的條件。(3)

輸出計算結(jié)果9//************************************//*程序名：3-30.cpp（五人合伙捕魚）*//*作者：ghq*//*編制時間：2011年3月2日*//*主要功能：遞推算法的實現(xiàn)*//************************************#include<iostream> //預(yù)編譯命令usingnamespacestd;intmain() //主函數(shù){intfish[6]={1,1,1,1,1,1};//整型數(shù)組，記錄每人醒來后看到的魚數(shù)inti=0;do{fish[5]=fish[5]+5;//讓E看到的魚數(shù)增5。

for(i=4;i>=1;i--){ if(fish[i+1]%4!=0) break; //跳出for循環(huán)

else fish[i]=fish[i+1]*5/4+1;//計算第i人看到的魚數(shù)}}while(i>=1);//當(dāng)i>=1繼續(xù)做do循環(huán)for(i=1;i<=5;i++)cout<<fish[i]<<endl;//輸出計算結(jié)果return0;}10intmain() //主函數(shù){

intfish[6]={1,1,1,1,1,1};//數(shù)組，記錄每人看到的魚數(shù)inti=0;do{fish[5]=fish[5]+5;//讓E看到的魚數(shù)增5。

for(i=4;i>=1;i--){ if(fish[i+1]%4!=0) break; //跳出for循環(huán)

else fish[i]=fish[i+1]*5/4+1;//計算第i人看到的魚數(shù)}}while(i>=1);//當(dāng)i>=1繼續(xù)做do循環(huán)for(i=1;i<=5;i++)//輸出計算結(jié)果 cout<<fish[i]<<endl;

return0;}11do{

fish[5]=fish[5]+5;//讓E看到的魚數(shù)增5。

for(i=4;i>=1;i--){Tif(fish[i+1]%4!=0)F

break;

//跳出for循環(huán)else

fish[i]=fish[i+1]*5/4+1;

//計算第i人看到的魚數(shù)}}while(i>=1);//當(dāng)i>=1繼續(xù)做do循環(huán)

12//輸出計算結(jié)果for(i=1;i<=5;i++) cout<<fish[i]<<endl;3121A2496B1996C1596D1276E13遞推數(shù)列的定義一個數(shù)列從某一項起，它的任何一項都可以用它前面的若干項來確定，這樣的數(shù)列稱為遞推數(shù)列。表示某項與前面若干項的關(guān)系稱為遞推公式(表達(dá)式）。例如：1!,2!,…,(n-1)!,n!

令fact(n)為n的階乘

fact(n)=n*fact(n-1)(通項公式)

fact(1)=1(邊界條件)14遞推算法的程序?qū)崿F(xiàn)

自學(xué)90頁內(nèi)容：[任務(wù)6.4]王小二切餅

遞歸及其實現(xiàn) 遞歸算法在可計算性理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。就遞歸算法而言并不涉及高深數(shù)學(xué)知識，只不過初學(xué)者要建立起遞歸概念不十分容易。16[任務(wù)6.5]用遞歸算法求n!定義：函數(shù)fact(n)=n! fact(n-1)=(n-1)!

則有 fact(n)=n

fact(n-1)

已知 fact(1)=1該問題也可以用遞推方法解決17為了表述得直觀清晰，我們定義兩個結(jié)點：或結(jié)點和與結(jié)點。圖示的直觀性與思維助力。1、或結(jié)點A為“或結(jié)點”，A依不同條件會有兩種不同的取值,B或C。結(jié)點用表示。18如果有多于2種取值，可用下圖：條件為Z1,Z2,…,Zn,取值為B或C,…或G192、與結(jié)點 與結(jié)點要涂黑，相關(guān)聯(lián)的B與C之間要用弧線連起來。 A為與結(jié)點，A的最終取值為C結(jié)點的值，但為了求得C的值，得先求出B結(jié)點的值，C是B的函數(shù)。20仍以求n!為例畫出如下與或圖 A為或結(jié)點；B為直接可解結(jié)點，值為1； C為與結(jié)點，當(dāng)n>1時，A的取值即C的值，而C的值即E的值，為了求得E的值，需要先求出D的值。D值fact(n-1)乘以n即為E的值。21與結(jié)點可能有多個相關(guān)聯(lián)的點，這時可描述為下圖 A結(jié)點的值最終為D的值，但為了求D需先求B和C。從圖上看,先求左邊的點才能求最右邊的點的值，我們約定最右邊D點的值就是A結(jié)點的值。22 下面我們以3！為例來畫與或結(jié)點圖，目的是體會遞歸的含義。C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=623下面畫出了調(diào)用和返回的遞歸示意圖24 從圖可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剝一顆圓白菜，從外向里，一層層剝下來，到了菜心，遇到1的階乘，其值為1，到達(dá)了遞歸的邊界。然后再用fact(n)=n*fact(n-1)這個普遍公式，從里向外倒推回去得到fact(n)的值。 為了把這個問題說得再透徹一點。我們畫了如下的流程圖：2526為了形象地描述遞歸過程，將上圖改畫成下圖27 在這個圖中“內(nèi)層”與“外層”有著相同的結(jié)構(gòu)。它們之間“你中有我，我中有你”，呈現(xiàn)相互依存的關(guān)系。 為了進(jìn)一步講清遞歸的概念，將遞歸與遞推做一比較。仍以求階乘為例。 遞推是從已知的初始條件出發(fā)，逐次去求所需要的階乘值。如求3！初始條件 fact(1)=1 fact(2)=

2*fact(1)=2 fact(3)=3*fact(2)=628 這相當(dāng)于從菜心“推到”外層。而遞歸算法的出發(fā)點不放在初始條件上，而放在求解的目標(biāo)上，從所求的未知項出發(fā)逐次調(diào)用本身的求解過程，直到遞歸的邊界（即初始條件）。就本例而言，讀者會認(rèn)為遞歸算法可能是多余的，費力而不討好。但許多實際問題不可能或不容易找到顯而易見的遞推關(guān)系，這時遞歸算法就表現(xiàn)出了明顯的優(yōu)越性。下面我們將會看到，遞歸算法比較符合人的思維方式，邏輯性強(qiáng)，可將問題描述得簡單扼要，具有良好的可讀性，易于理解，許多看來相當(dāng)復(fù)雜，或難以下手的問題，如果能夠使用遞歸算法就會使問題變得易于處理。下面舉一個盡人皆知的例子哈諾（Hanoi）塔問題。29故事： 相傳在古代印度的Bramah廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現(xiàn)，如以每秒移動一只盤子的話，按照上述規(guī)則將64只盤子從一個柱子移至另一個柱子上，所需時間約為5800億年。30怎樣編寫這種程序？思路上還是先從最簡單的情況分析起，搬一搬看，慢慢理出思路。1、在A柱上只有一只盤子，假定盤號為1，這時只需將該盤從A搬至C，一次完成，記為

move1fromAtoC(演示)ABC1312、在A柱上有二只盤子，1為小盤，2為大盤。第（1）步將1號盤從A移至B，這是為了讓2號盤能移動；第（2）步將2號盤從A移至C；第（3）步再將1號盤從B移至C； 這三步記為（演示）：ABC21move1fromAtoB;move2fromAtoC;move3formBtoC;323、在A柱上有3只盤子，從小到大分別為1號，2號，3號第（1）步將1號盤和2號盤視為一個整體；先將二者作為整體從A移至B，給3號盤創(chuàng)造能夠一次移至C的機(jī)會。這一步記為move(2,A,C,B)意思是將上面的2只盤子作為整體從A借助C移至B。第（2）步將3號盤從A移至C，一次到位。記為

move3fromAtoC第（3）步處于B上的作為一個整體的2只盤子，再移至C。這一步記為 move(2,B,A,C) 意思是將2只盤子作為整體從B借助A移至C。 所謂借助是什么意思，等這件事做完了不言自明。33move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213演示：移動3個盤子的分解34move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213354、從題目的約束條件看，大盤上可以隨便摞小盤，相反則不允許。在將1號和2號盤當(dāng)整體從A移至B的過程中move(2,A,C,B)實際上是分解為以下三步 第（1）.1步：move1formAtoC; 第（1）.2步：move2formAtoB; 第（1）.3步：move1formCtoB;36 經(jīng)過以上步驟，將1號和2號盤作為整體從A

移至B，為3號盤從A

移至C

創(chuàng)造了條件。同樣，3號盤一旦到了C，就要考慮如何實現(xiàn)將1號和2號盤當(dāng)整體從B

移至C的過程了。實際上move(2,B,A,C)

也要分解為三步： 第（3）.1步：move1formBtoA; 第（3）.2步：move2formBtoC; 第（3）.3步：move1formAtoC;375、看move(2,A,C,B)

是說要將2只盤子從A

搬至B，但沒有

C

是不行的，因為第（1）.1步就要將1盤從A

移到C，給2盤創(chuàng)造條件從A

移至B，然后再把1盤從C

移至B?？吹竭@里就能明白借助C

的含義了。因此，在構(gòu)思搬移過程的參量時，要把3個柱子都用上。386、定義搬移函數(shù)move(n,A,B,C)，物理意義是將n只盤子從A經(jīng)B搬到C 考慮到前面已經(jīng)研究過的(1)(2)(3)步，可以將搬移過程用如下的與或結(jié)點圖表示。39 這里用與或結(jié)點的含義是分解為(1)(2)(3)步。這3步是相關(guān)的，相互依存的，而且是有序的，從左至右執(zhí)行。move(n,A,B,C)

分解為3步(1)move(n-1,A,C,B)理解為將上面的n-1只盤子作為一個整體從A經(jīng)C移至B；(2)輸出n：AtoC，理解將n號盤從A移至C，是直接可解結(jié)點；(3)move(n-1,B,A,C)理解為將上面的n-1只盤子作為一個整體從B經(jīng)A移至C。40 這里顯然是一種遞歸定義，move(n-1,A,C,B)可分解為3步：第1步：將上面的n-2只盤子作為一個整體從A經(jīng)B到C，move(n-2,A,B,C)；第2步：第n-1號盤子從A直接移至B，即n-1:AtoB；第3步：再將上面的n-2只盤子作為一個整體從C經(jīng)A移至B，move(n-2,C,A,B)；下面，我們還是以3只盤子為例畫出遞歸的與或圖。41這個圖很象一顆倒置著的樹，結(jié)點move(3,A,B,C)是樹根，與結(jié)點是樹的分枝，葉子都是直接可解結(jié)點。424344//*******************************************//*程序名：6_hanoi2002.cpp*//*作者：wuwh*//*編制時間：2002年10月13日*//*主要功能：用遞歸求解Hanoi問題*//*******************************************#include<iostream> //預(yù)編譯命令usingnamespacestd;intstep=1; //整型全局變量,預(yù)置1,步數(shù)voidmove(int,char,char,char); //聲明要用到的被調(diào)用函數(shù)intmain() //主函數(shù){ //主程序開始 intn; //整型變量,n為盤數(shù), cout<<"請輸入盤數(shù)n="; //提示信息 cin>>n; //輸入正整數(shù)n cout<<"在3根柱子上移" //輸出提示信息 <<n<<"只盤的步驟為:"<<endl;move(n,'a','b','c'); //調(diào)用函數(shù)move(n,'a','b','c')return0;} //主函數(shù)結(jié)束45//以下函數(shù)是被主程序調(diào)用的函數(shù)//函數(shù)名：move//輸入：m，整型變量，表示盤子數(shù)目// p，q，r為字符型變量，表示柱子標(biāo)號//返回值：無voidmove(intm,charp,charq,charr){ //自定義函數(shù)體開始 if(m==1) //如果m為1,則為直接可解結(jié)點, { //直接可解結(jié)點,輸出移盤信息 cout<<"["<<step<<"]move1#from"<<p<<"to"<<r<<endl; step++; //步數(shù)加1 } else //如果不為1,則要調(diào)用move(m-1) { move(m-1,p,r,q); //遞歸調(diào)用move(m-1) //直接可解結(jié)點,輸出移盤信息 cout<<"["<<step<<"]move"<<m