孙甲松计算机程序设计基础递归练习约瑟夫环

1、用递归算法解决青蛙过河问题q:一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一 石柱l，面积只容得下一只青蛙落脚，同样右岸也有一石柱r，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，n编号。规定初 始时这队青蛙只能趴在左岸的石头l上，当然是一个摞一个，小的摞在大的上面。不允许大的摞在小的上面。在小溪中有s个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个摞一个，大的在下，小的在上。对于 荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的 石柱r，与左岸的石柱l一样允许多个青蛙落脚，但须一个摞 一个，小的在上，大的在下。当

2、青蛙从左岸的l上跳走后就不 允许再跳回来；同样，从左岸l上跳至右岸r，或从溪中荷叶 或溪中石柱跳至右岸r 上的青蛙也不允许再离开。问在已知 溪中有s根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？解题思路：因为一片荷叶上只能站一只青蛙，相对来说，荷叶是比较好理解的，也就是y片荷叶最多容纳y只青蛙。所以我们对s递推，河右岸的石柱可以认为是河中的第s+1根石柱。如果没有河中石柱，则最多有y+1只青蛙，这样才能实现。河中1个石柱时，首先能把y+1只青蛙运到该石柱上，然后再搬y只青蛙到荷叶上，这时河左岸剩一只青蛙，就把这只大青蛙搬到河右岸，荷叶上的都搬过去，最后搬石柱上的。也即，第n根石柱上的青蛙可以

3、通过前n-1根石柱和y片荷叶和河左岸柱子来实现搬运。(第n根的最大容纳量是f（n）)#include<stdio.h>int frogs(int m,int n)int fr,i;if(m=1) fr=n+1;elsefr=n+1;for(i=m-1;i>0;i-)fr=fr+frogs(i,n);return(fr);main()int s,y;printf("input the number of pillars s and the number of leaves yn");scanf("%d %d",&s,&y)

4、;printf("the max number of frogs is %d.n",frogs(s+1,y); /*相当于求第s+1根柱子上有几只青蛙*/system("pause");q:约瑟夫环问题，有m个人站成一圈，轮着报数，报到n的人死，问最后报数的人一开始站在第几个？解题思路：循环链表#include<iostream> /约瑟夫环#include<cstdlib>using namespace std;int m=3,n=40; /总共n个人，每m个人杀一个class listprivate:class listnod

5、epublic:int data;listnode *next;public:listnode(int k):data(k);listnode *first,*current;public:list(int n);void kill();list:list(int n)int count;listnode *p=new listnode(1);first=current=p;p->next=null;for(count=2;count<=n;count+)p=new listnode(count);current->next=p;p->next=null;current

6、=p;current->next=first;void list:kill()int i=1;listnode *p=current=first;while(current->next!=current)if(i%m!=0) p=current;current=p->next;elsep->next=current->next;delete current;current=p->next;i+;cout<<"the survivor is "<<current->data<<endl;delete

7、 current;void main()class list killing(n);killing.kill();system("pause");q:#include<stdio.h>#include<stdlib.h>#pragma warning(disable:4996)int n,k,method=0;int *broken;int test(int n)if(n>n) return(1);if(n=n) method+; return(1);else return(0);int yn(int sum)int i;for(i=0;i&l

8、t;k;i+)if(sum=*(broken+i) return 1;return(0);void dfs(int sum)int i;for(i=1;i<=3;i+)if(yn(sum+i)|test(sum+i) continue;else dfs(sum+i);return;main()int i;fflush(stdin);printf("input the number of stairs n and the number of broken stairs k: ");scanf("n=%d,k=%d",&n,&k);br

9、oken=(int *)malloc(sizeof(int)*k);for(i=0;i<k;i+)scanf("%d",broken+i);dfs(0);printf("%d",method);free(broken);system("pause");深度优先搜索！关键步：dfs（sum不需要加减 返回上一层时自动减掉i ；同时i是每一层的局部变量 重名不造成影响！）q:字符串回文处理#include<stdio.h>#include<stdlib.h>#include<string.h>#p

10、ragma warning(disable:4996)void chuli(char *s,int n)printf("%c",*s);if(n=1) return;elsechuli(s+1,n-1);printf("%c",*s);return;main()int n;char *s;printf("input the length of the string:");scanf("%d",&n);while(getchar()='0') getchar();s=(char*)malloc

11、(sizeof(char)*n);gets(s);chuli(s,n);system("pause");q:输入n 回形输出一个n阶方阵e.g. 1 8 7 2 9 6 3 4 5#include<stdio.h>#include<stdlib.h>#include<string.h>#pragma warning(disable:4996)int d;void oushu(int *p,int n,int en)int i;if(n=2) *p=en;*(p+d)=en+1;*(p+d+1)=en+2;*(p+1)=en+3;elsef

12、or(i=0;i<n-1;i+,en+)*(p+i*d)=en;for(i=0;i<n-1;i+,en+)*(p+(n-1)*d+i)=en;for(i=0;i<n-1;i+,en+)*(p+(n-1)*d+n-1-i*d)=en;for(i=0;i<n-1;i+,en+)*(p+n-1-i)=en;oushu(p+d+1),n-2,en);return;void jishu(int *p,int n,int en)int i;if(n=1) *p=en;elsefor(i=0;i<n-1;i+,en+)*(p+i*d)=en;for(i=0;i<n-1;i+,en+)*(p+(n-1)*d+i)=en;for(i=0;i<n-1;i+,en+)*(p+(n-1)*d+n-1-i*d)=en;for(i=0;i<n-1;i+,en+)*(p+n-1-i)=en;jishu(p+d+1),n-2,en);return;main()int n,*p,i;printf("input n:");scanf("%d",&