遞推與遞歸練習(xí)題

1、練習(xí)1. （用遞歸做）5個(gè)人坐在一起，問第五個(gè)人多少歲？他說比第4個(gè)人大2歲。問第4個(gè)人歲數(shù)，他說比第3個(gè)人大2歲。問第三個(gè)人，又說比第2人大兩歲。問第2個(gè)人，說比第一個(gè)人大兩歲。最后問第一個(gè)人，他說是10歲。請問第五個(gè)人多大？程序分析：利用遞歸的方法，遞歸分為回推和遞推兩個(gè)階段。要想知道第五個(gè)人歲數(shù)，需知道第四人的歲數(shù)，依次類推，推到第一人（10歲），再往回推。2. （用遞歸做）商人渡河問題是這樣的：有三個(gè)商人，三個(gè)強(qiáng)盜，和一條船（船每次只可以載小于等于兩個(gè)人）他們同在河的一邊，想渡過河去，但是必須保證在河的任何一邊必須保證商人的數(shù)目大于等于強(qiáng)盜的數(shù)目，應(yīng)該怎么過這條河呢？注意：開始時(shí)商人，

2、強(qiáng)盜所在的河的這邊設(shè)為0狀態(tài)，另一邊設(shè)為1狀態(tài)（也就是船開始時(shí)的一邊設(shè)為0，當(dāng)船駛到對岸是設(shè)為1狀態(tài)，在這兩個(gè)狀態(tài)時(shí)，都必須符合條件）3. （用遞推做）猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)，第二天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半多一個(gè)。到第30天早上想再吃時(shí)，見只剩下1個(gè)桃子了。求第一天共摘了多少。4. （用遞推做）已知一對兔子每一個(gè)月能生一對小兔子，而一對小兔子出生后第二個(gè)月就開始生小兔子，假如一年內(nèi)沒有發(fā)生死亡，則以對兔子一年能繁殖成多少對？答案：1. #include <stdio.h>int age(in

3、t n) if(n=1) return(10);else return age(n-1)+2;void main() int n;n=5;printf("The fifth age is %d.n",age(n); 2. #include<conio.h>#include<stdio.h>#include <stdlib.h>struct node /*建立一個(gè)類似棧的數(shù)據(jù)結(jié)構(gòu)并且可以瀏覽每一個(gè)數(shù)據(jù)點(diǎn)*/ int x;int y;int state;struct node *next;typedef struct node state;t

4、ypedef state *link;link PPointer1=NULL;link PPointer2=NULL;int a1,b1;int a2,b2;/*棧中每個(gè)數(shù)據(jù)都分為0，1狀態(tài)*/void Push(int a,int b,int n)link newnode;newnode=(link)malloc(sizeof(state);newnode-> x=a;newnode-> y=b;newnode-> state=n;newnode-> next=NULL;if(PPointer1=NULL)PPointer1=newnode;PPointer2=new

5、node;elsePPointer2-> next=newnode;PPointer2=newnode;void Pop() /*彈棧*/link pointer;if(PPointer1=PPointer2)free(PPointer1);PPointer1=NULL;PPointer2=NULL;pointer=PPointer1;while(pointer-> next!=PPointer2)pointer=pointer-> next;free(PPointer2);PPointer2=pointer;PPointer2-> next=NULL;int hist

6、ory(int a,int b,int n) /*比較輸入的數(shù)據(jù)和棧中是否有重復(fù)的*/ link pointer;if(PPointer1=NULL)return 1;elsepointer=PPointer1;while(pointer!=NULL)if(pointer-> x=a&&pointer-> y=b&&pointer-> state=n)return 0;pointer=pointer-> next;return 1;int judge(int a,int b,int c,int d,int n) /*判斷這個(gè)狀態(tài)是否可行，

7、其中使用了history函*/if(history(a,b,n)=0) return 0;if(a>=0&&b>=0&&a<=3&&b<=3&&c>=0&&d>=0&&c<=3&&d<=3&&a+c=3&&b+d=3) switch(n)case 1:if(a=3)Push(a,b,n);return 1;else if(a=0)Push(a,b,n);return 1;else if(a=b)Push(

8、a,b,n);return 1;else return 0;case 0:if(a=3)Push(a,b,n);return 1;else if(a=0)Push(a,b,n);return 1;else if(a>=b)Push(a,b,n);return 1;else return 0;else return 0;int Duhe(int a,int b,int n) /*遞歸法解決商人渡河問題，如果這一個(gè)狀態(tài)符合*/ /*則判斷下一個(gè)狀態(tài)，直至問題解決*/if(a=0&&b=0) return 1;if(n=0) /*判斷0狀態(tài)時(shí)，商匪狀態(tài)是否符合要求*/if(ju

9、dge(a-1,b-1,4-a,4-b,1)if(Duhe(a-1,b-1,1)=1)return 1;if(judge(a,b-2,3-a,5-b,1)if(Duhe(a,b-2,1)=1)return 1;if(judge(a-2,b,5-a,3-b,1)if(Duhe(a-2,b,1)=1)return 1;if(judge(a-1,b,4-a,3-b,1)if(Duhe(a-1,b,1)=1)return 1;if(judge(a,b-1,3-a,4-b,1)if(Duhe(a,b-1,1)=1)return 1;elsePop();return 0;if(n=1) /*判斷0狀態(tài)時(shí)，

10、商匪狀態(tài)是否符合要求*/ if(judge(a+1,b+1,2-a,2-b,0)if(Duhe(a+1,b+1,0)=1)return 1;if(judge(a,b+2,3-a,1-b,0)if(Duhe(a,b+2,0)=1)return 1;if(judge(a+2,b,1-a,3-b,0)if(Duhe(a+2,b,0)=1)return 1;if(judge(a+1,b,2-a,3-b,0)if(Duhe(a+1,b,0)=1)return 1;if(judge(a,b+1,3-a,2-b,0)if(Duhe(a,b+1,0)=1)return 1;elsePop();return 0

11、;return 0;main()link pointer;Push(3,3,0);Duhe(3,3,0);pointer=PPointer1;while(pointer!=NULL)printf( "%d,%d-%dn ",pointer-> x,pointer-> y,pointer-> state); pointer=pointer-> next;getch(); 3. #include <stdio.h>#include <stdlib.h>#define N 30void main()int n, si,si1;si1

12、=1;for(n=N-1;n>=1;n-)/倒數(shù)第二天開始si=(si1+1)*2; /算出當(dāng)天的桃子數(shù)si1=si;printf("共有%d天，第一天的桃子數(shù)為 %4dn",N,si); 4. 程序源代碼：main() long f1,f2;­int i;f1=f2=1;for(i=1;i<=20;i+) printf("%12ld %12ld",f1,f2);if(i%2=0) printf("n"); /*控制輸出，每行四個(gè)*/­ f1=f1+f2; /*前兩個(gè)月加起來賦值給第三個(gè)月*/­ f2=f1+f2; /*前兩個(gè)月加起來賦值給第三個(gè)月*/­ 上題還可用一維