插入前面：这段内容本来在下面猴子分桃题目之前是没有的，想看题，可以先看后面的题目，然后看着插入在前面的关于递归实现下面问题的代码，为什么要突然放在前面，因为这是一部分比较重要的内容，是个思想锻炼的结果和总结，另外最后吗还给出了错误的代码以及错误的原因可以对比理清思路：
1 #include2 using namespace std; 3 4 5 int recursion(int time,int n) 6 { 7 int sum; 8 if (time == 0) { 9 return n;10 }11 if (n%4 == 0) {12 n = recursion(time-1,n);13 }14 if (n%4 == 0) {15 sum = n/4*5+1;16 }else{17 sum = -1;18 }19 return sum;20 }21 22 int main(int argc,const char * argv[])23 {24 cout << recursion(5,1020) << endl;25 int i,result;26 while (true) {27 result = recursion(5, i);28 if (result!=-1) {29 cout << result << endl;30 break;31 }32 33 i++;34 }35 return 0;36 }
如何思考用递归解决这个问题，根据前面两个递归的编码(约瑟夫环f(100)=f(99)+f(98)，reserve链表方向)经验，都有类似下面的递归代码执行过程。
注意事项：在调用函数的时候，实参如果用比如这里的time－－或者time＋＋，而不用time－1或者time＋1会报错。
另外的错误思路写的错误的代码：｛思路错误的原因：第12步就错误了，调用函数会得到一个返回值，这个返回值要先进行％4判断，然后才能接着进行／4*5+1的运算，然而这里不是，所以造成了错误。｝
1 #include2 using namespace std; 3 4 int recursion(int time,int n) 5 { 6 int sum,t,ti; 7 ti = time; 8 if (time == 0) { 9 return 0;10 }11 if (n%4 == 0) {12 t = recursion(time-1,n)/4*5+1;13 if (time == ti) {14 return t;15 }16 if (t%4 == 0) {17 sum = t;18 }else{19 sum = 0;20 }21 }22 return sum;23 }24 25 int main(int argc , const char* argv[])26 {27 cout << recursion(5, 1020);28 cout << "Hello World!" << endl;29 return 0;30 }
1、猴子分桃：海滩上有一堆桃子，五只猴子来分，第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份，第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三，第四，第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？
1 #include2 3 using namespace std; 4 5 //猴子分桃：海滩上有一堆桃子，五只猴子来分，第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份，第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三，第四，第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？ 6 7 //根据剩下的桃子，得到桃子的初始值 8 int get_taozi(int x){ 9 int n = x*5/4+1;10 return n;11 }12 13 //根据猴子的个数和最后一个猴子剩下的桃子个数，返回第一个猴子的桃子初始值14 int get_init(int n,int y){15 for (int i = n; i>0; i--) {16 if (y%4 != 0) {17 //退出循环，并返回一个值-118 return -1;19 }20 y = get_taozi(y);21 }22 return y;23 }24 //测试，从最后一个猴子的个数，从0开始测试得出结果25 void test(int n){26 int i,m;27 while (true) {28 m = get_init(n, i);29 if (m != -1) {30 //当算出结果，输出后，当然需要break了31 cout << "正确的结果是：" << m << endl;32 break;33 }34 i++;35 }36 }37 int main(int argc,char** argv)38 {39 test(5);40 return 0 ;41 }
