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