【正文】 條件。一般用一個(gè)表達(dá)式或者計(jì)數(shù)器來判斷迭代式是否應(yīng)該終止。本題中迭代式中i+=1，i的初始值為1；sum+=n or sum=n這通過一個(gè)標(biāo)志變量flag來控制，flag==1時(shí)sum+=n，flag==0時(shí)sum=n，sum的初始值為1。終止條件為。【代碼】cCODE:includeincludeincludeint main (int argc, char **argv){ int flag=0,i=1。double n=1,sum=1。while(n=pow(10,6)){n=(double)1/(2*i+1)。i+=1。 if(1==flag){sum+=n。flag=0。}else{sum=n。flag=1。} }sum*=4。printf(%lf,sum)。 system(PAUSE)。return 0。}【問題描述】編寫一個(gè)c程序，把下列數(shù)組延長到第50項(xiàng)：1，2，5，10，21，42，85，170，341，682【思路】由給定的數(shù)組元素可以看出偶數(shù)項(xiàng)是前一項(xiàng)的2倍，奇數(shù)項(xiàng)是前一項(xiàng)的2倍加1。即，這是一中遞推關(guān)系由前項(xiàng)推出后項(xiàng)，此題可以通過遞推關(guān)系求解。遞推解題和迭代解題是很相似的，遞推是通過其他變量來演化，而迭代則是通過自身不斷演化。遞推法的運(yùn)用也有三個(gè)關(guān)鍵： 尋找遞推關(guān)系。這是最重要的問題。遞推關(guān)系有解析和非解析兩種。解析遞推關(guān)系是指能用一般數(shù)學(xué)公式描 述的關(guān)系，也稱遞推公式。例如，本題的遞推關(guān)系就是解析的。非解析遞推關(guān)系是指不能用一般的數(shù)學(xué)公式描述的關(guān)系，這類關(guān)系的描述，也許本身就是一個(gè)過程。 這類問題一般比較復(fù)雜，要結(jié)合其他的策略如分治法來解決。 遞推關(guān)系必須有始基，即最小子解（針對初始規(guī)模的子解的值），沒有始基，遞推計(jì)算就不能開始。例如本題a1=1就是始基。 遞推計(jì)算。即根據(jù)遞推關(guān)系進(jìn)行遞推計(jì)算。遞推計(jì)算可以由遞歸解析和非遞歸兩種，遞歸計(jì)算是采用遞歸法，其形式是自頂向下，而非遞歸則是自底向上。本題是非遞歸的。解此題還須注意一點(diǎn)：數(shù)列的項(xiàng)必須定義為double型，因?yàn)檠娱L到第50項(xiàng)如果定義為int or float型，數(shù)列的項(xiàng)會(huì)被截?cái)嗉闯^int和float的表示范圍。【代碼】cCODE:includeincludeint main (int argc, char **argv){double a1=1,a=0。int i=1。while(i=50){printf(%.0lf ,a1)。 //39。.0’ is just for do not output the decimal placei++。if(i%2==1)a=2*a1+1。elsea=2*a1。a1=a。 } system(PAUSE)。return 0。}【問題描述】 用遞歸算法實(shí)現(xiàn)求一個(gè)數(shù)組中的最大元素?！舅悸贰拷鉀Q遞歸問題可以分為兩個(gè)部分，第一部分是一些特殊（基礎(chǔ)）情況，用直接法解，即始基；第二部分與原問題相似，可用類似的方法解決（即遞歸），但比原問題的規(guī)模要小。本題顯然始基是a[0],關(guān)鍵是要找出遞歸關(guān)系，定義一個(gè)函數(shù)int max(int a[],int n)，其中整型a[]是一個(gè)數(shù)組，n是數(shù)組長度減1，即數(shù)組最大有效元素的下標(biāo)，因?yàn)閏語言中數(shù)組元素下標(biāo)是從0開始的。 如果0==n，則a[0]就是最大的元素 如果n0，則先求出a[0]到a[n1]的最大元素，然后與a[n]比較，較大者即為最大元素。其中a[0]到a[n1]又可以用這種方式求，此時(shí)需要將a[0],a[1]...a[n1]看成一個(gè)由n1個(gè)元素構(gòu)成的一維數(shù)組?！敬a】cCODE:includeincludeint max(int a[],int n)。int main (int argc, char **argv){ int a[]={1,2,3,4,5,6,7,6}。printf(The max element is %d!\n,max(a,7))。/*caution:he length of a is 8,but the argument is 7*/ system(PAUSE)。return 0。}int max(int a[],int n){if(0==n)return a[n]。else return (a[n]max(a,n1)?a[n]:max(a,n1))。 }【問題描述】自然數(shù)的拆分：任何一個(gè)大于1的自然數(shù)N，總可以拆分成若干個(gè)自然數(shù)之和，并且有多種拆分方法。例如自然數(shù)5，可以有如下一些拆分方法：5=1+1+1+1+15=1+1+1+25=1+2+25=1+45=2+3【思路】自然數(shù)的拆分可以用回溯法。知識(shí)點(diǎn)：回 溯法解題時(shí)，對任一解的生產(chǎn)，一般采用逐步擴(kuò)大解的方式。每進(jìn)行一步，都試圖在當(dāng)前部分解的基礎(chǔ)上擴(kuò)大該部分解。擴(kuò)大時(shí)，首先檢查擴(kuò)大后是否違反了約束條 件，若不違反，則擴(kuò)大之，然后繼續(xù)在此基礎(chǔ)上按照類似的方法進(jìn)行，直至為完全解；若違反，則放棄該步以及它生成的部分解，然后按照類似的方法嘗試其他可能 的擴(kuò)大方式，直到已經(jīng)嘗試了所有的擴(kuò)大方式?；厮莘ń忸}通常包含以下三個(gè)步驟： 針對所給問題，定義問題的解空間；如本題對5的拆分來說，1=拆分的數(shù)=5。 確定易于搜索的解空間結(jié)構(gòu)；如本題對5的拆分來說，用x[]數(shù)組來存儲(chǔ)解，每個(gè)數(shù)組元素的取值范圍都是1=拆分的數(shù)=5，從1開始搜索直到5。 搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。如本題對5的拆分來說，為了避免重復(fù)，x=x[j](ij)，如x[]={2,3}滿足條件而x[]={3,2}就不滿足條件不是可行解即無效?；厮莘ㄍǔＳ袃煞N實(shí)現(xiàn)方式，一種是遞歸的方式，另一種是迭代的方式。在此就用遞歸方式，當(dāng)然迭代的方式也可以?！　　敬a】cCODE:includeincludevoid splitN(int n,int m)。//n是需要拆分的數(shù)，m是拆分的進(jìn)度。int x[1024]={0},total=0 。//total用于計(jì)數(shù)拆分的方法數(shù)，x[]用于存儲(chǔ)解int main(){int n 。printf(please input the natural number n:)。scanf(%d,amp。n)。splitN(n,1)。printf(There are %d ways to split natural number %d.\n,total,n)。system(PAUSE)。return 0 。}void splitN(int n,int m){//n是需要拆分的數(shù)，m是拆分的進(jìn)度。int rest,i,j。 for(i=1。i=n。i++){//從1開始嘗試拆分。 if(i=x[m1]){//拆分的數(shù)大于或等于前一個(gè)從而保證不重復(fù)x[m]=i 。//將這個(gè)數(shù)計(jì)入結(jié)果中。 rest=ni 。//剩下的數(shù)是ni，如果已經(jīng)沒有剩下的了，并且進(jìn)度(總的拆分個(gè)數(shù))大于1，說明已經(jīng)得到一個(gè)結(jié)果。if(rest==0amp。amp。m1){total++。printf(%d\t,total)。for(j=1。jm。j++){printf(%d+,x[j])。}printf(%d\n,x[m])。}else{splitN(rest,m+1)。//否則將剩下的數(shù)進(jìn)行進(jìn)度為m+1拆分。}x[m]=0。//取消本次結(jié)果，進(jìn)行下一次拆分。環(huán)境恢復(fù)，即回溯}}}【問題描述】用遞歸函數(shù)求解兩個(gè)正整數(shù)的最大公約數(shù)的過程。【思路】此題不需太多的思考就是運(yùn)用歐幾里得算法（Euclid’s algorithm）。摘自《The Artof Computer Programming》volume 1：(Euclid’s algorithm )Give two postiveintegers m and n, find their greatest mon divisor, that is ,the largestpositive integer that evenly divide both m and n.Step1.[Find remainder.]Divide m by n andlet r be the remainder.(We will have 0=rn.)Step2.[Is it zero?]If r=0,the algorithmterminates。 n is the answer.Step3.[Reduce.]Set m=n,n=r, and go backto Step1.【代碼】cCODE:includeincludeint GCD(int m,int n)。/*function is to find the greatest mon divisor between mand n*/int main (int argc, char **argv){ int m,n,temp。printf(Please input m and n:\n)。scanf(%d %d,amp。m,amp。n)。 if(mn){/*This is just ensure mn*/temp=m。m=n。n=temp。}printf(The greatest mon divisor of (%d,%d) is%d!\n,m,n,GCD(m,n))。 system(PAUSE)。return 0。}int GCD(int m,int n){if(m%n==0)return n。else return GCD(n,m%n)。}【問題描述】 已知Ackerman函數(shù)對于整數(shù)m=0和n=0有如下定義：ack(0,n)=n+1ack(m,0)=ack(m1,1)ack(m,n)=ack(m1,ack(m,n1))【思路】此題明顯用遞歸方法解，由上述定義可得遞歸公式如下：| n+1, 當(dāng)m=0時(shí)；ack(m,n)= | ack(m1,1), 當(dāng)n=0時(shí)； | ack(m1,ack(m,n1)),其他情況?！敬a】cCODE:includeincludeint ack(int m,int n)。int main (int argc, char **argv){ int m,n。printf(Please input m and n:\n)。scanf(%d %d,amp。m,amp。n)。printf(The result of ack(%d,%d) is%d!\n,m,n,ack(m,n))。 system(PAUSE)。return 0。}int ack(int m,int n){if(0==m)return n+1。else if(0==n)return ack(m1,1)。else return ack(m1,ack(m,n1))。}