递推与递归练习题

练习1.（用递归做）5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人（10岁），再往回推。2.（用递归做）商人渡河问题是这样的：有三个商人，三个强盗，和一条船（船每次只可以载小于等于两个人）他们同在河的一边，想渡过河去，但是必须保证在河的任何一边必须保证商人的数目大于等于强盗的数目，应该怎么过这条河呢？注意：开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件）3.（用递推做）猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半多一个。到第30天早上想再吃时，见只剩下1个桃子了。求第一天共摘了多少。4.（用递推做）已知一对兔子每一个月能生一对小兔子，而一对小兔子出生后第二个月就开始生小兔子，假如一年内没有发生死亡，则以对兔子一年能繁殖成多少对？答案：1.#includestdio.hintage(intn){if(n==1)return(10);elsereturnage(n-1)+2;}voidmain(){intn;n=5;printf(Thefifthageis%d.\n,age(n));}2.#includeconio.h#includestdio.h#includestdlib.hstructnode/*建立一个类似栈的数据结构并且可以浏览每一个数据点*/{intx;inty;intstate;structnode*next;};typedefstructnodestate;typedefstate*link;linkPPointer1=NULL;linkPPointer2=NULL;inta1,b1;inta2,b2;/*栈中每个数据都分为0，1状态*/voidPush(inta,intb,intn){linknewnode;newnode=(link)malloc(sizeof(state));newnode-x=a;newnode-y=b;newnode-state=n;newnode-next=NULL;if(PPointer1==NULL){PPointer1=newnode;PPointer2=newnode;}else{PPointer2-next=newnode;PPointer2=newnode;}}voidPop()/*弹栈*/{linkpointer;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;}inthistory(inta,intb,intn)/*比较输入的数据和栈中是否有重复的*/{linkpointer;if(PPointer1==NULL)return1;else{pointer=PPointer1;while(pointer!=NULL){if(pointer-x==a&&pointer-y==b&&pointer-state==n)return0;pointer=pointer-next;}return1;}}intjudge(inta,intb,intc,intd,intn)/*判断这个状态是否可行，其中使用了history函*/{if(history(a,b,n)==0)return0;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){case1:{if(a==3){Push(a,b,n);return1;}elseif(a==0){Push(a,b,n);return1;}elseif(a==b){Push(a,b,n);return1;}elsereturn0;}case0:{if(a==3){Push(a,b,n);return1;}elseif(a==0){Push(a,b,n);return1;}elseif(a=b){Push(a,b,n);return1;}elsereturn0;}}}elsereturn0;}intDuhe(inta,intb,intn)/*递归法解决商人渡河问题，如果这一个状态符合*/{/*则判断下一个状态，直至问题解决*/if(a==0&&b==0)return1;if(n==0)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a-1,b-1,4-a,4-b,1)){if(Duhe(a-1,b-1,1)==1)return1;}if(judge(a,b-2,3-a,5-b,1)){if(Duhe(a,b-2,1)==1)return1;}if(judge(a-2,b,5-a,3-b,1)){if(Duhe(a-2,b,1)==1)return1;}if(judge(a-1,b,4-a,3-b,1)){if(Duhe(a-1,b,1)==1)return1;}if(judge(a,b-1,3-a,4-b,1)){if(Duhe(a,b-1,1)==1)return1;}else{Pop();return0;}}if(n==1)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a+1,b+1,2-a,2-b,0)){if(Duhe(a+1,b+1,0)==1)return1;}if(judge(a,b+2,3-a,1-b,0)){if(Duhe(a,b+2,0)==1)return1;}if(judge(a+2,b,1-a,3-b,0)){if(Duhe(a+2,b,0)==1)return1;}if(judge(a+1,b,2-a,3-b,0)){if(Duhe(a+1,b,0)==1)return1;}if(judge(a,b+1,3-a,2-b,0)){if(Duhe(a,b+1,0)==1)return1;}else{Pop();return0;}}return0;}main(){linkpointer;Push(3,3,0);Duhe(3,3,0);pointer=PPointer1;while(pointer!=NULL){printf(%d,%d---%d\n,pointer-x,pointer-y,pointer-state);pointer=pointer-next;}getch();}3.#includestdio.h#includestdlib.h#defineN30voidmain(){intn,si,si1;si1=1;for(n=N-1;n=1;n--)//倒数第二天开始{si=(si1+1)*2;//算出当天的桃子数si1=si;}printf(共有%d天，第一天的桃子数为%4d\n,N,si);}4.程序源代码：main(){longf1,f2;­inti;f1=f2=1;for(i=1;i=20;i++){printf(%12ld%12ld,f1,f2);if(i%2==0)printf(\n);/*控制输出，每行四个*/­f1=f1+f2;/*前两个月加起来赋值给第三个月*/­f2=f1+f2;/*前两个月加起来赋值给第三个月*/­}}上题还可用一维数组处理­#includestdio.h#defineN20voidmain(){inta[N];inti;a[0]=a[1]=1;for(i=2;iN;i++){a[i]=a[i-1]+a[i-2];}for(i=1;i=N;i++){printf(%12d,a[i-1]);if(i%4==0)printf(\n);}}