编码练习：猴子捡桃

插入前面：这段内容本来在下面猴子分桃题目之前是没有的，想看题，可以先看后面的题目，然后看着插入在前面的关于递归实现下面问题的代码，为什么要突然放在前面，因为这是一部分比较重要的内容，是个思想锻炼的结果和总结，另外最后吗还给出了错误的代码以及错误的原因可以对比理清思路：

 1 #include <iostream>
 2 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 #include <iostream>
 2 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 #include <iostream>
 2  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 //退出循环，并返回一个值-1 18 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 }