猴子分桃 - Ryan in C++ - 博客园

猴子分桃 - Ryan in C++ - 博客园
猴子分桃的故事大体有两种描述：
描述 1 ：五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了个数相等的五堆，多出一只；于是，它吃掉了一个，拿走了一堆。第二只猴子起来一看，只有四堆桃，于是把四堆合在一起，分成相等的五堆，又多出一个；然后，它也吃掉了一个，拿走了一堆。剩下的三只猴子也都是这样分的。问：这堆桃至少有多少个？
描述 2 ：海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子平均分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份。第三、第四、第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？

分析

程序猿一般这样看问题：总之桃子数目是整数，me 就从 1 开始试，然后分给猴子们，如果可以按题目要求的分法(去掉 1 个然后平均分 5 份，剩下 4 份)分 5 个猴子不就可以了 ？ 真是不动脑筋的思考方案呀，尼玛 ! 不过这的确是一种万能的解决方案，对于本题来说，程序也不会运行很久。
现在从一个非程序猿的角度看问题。这里主要是要捕捉到它们的数量关系。
假设第二个猴子拿了 x₂ 个桃子，第三个猴子拿了 x₃ 个，那么有这么个关系： 4 x₂ = 5 x₃ + 1 ，这是类似于 4 a = 5 b + 1 的式子。毫无疑问的是 a 、b 都是整数了。4 a = 5 b + 1 = 4 b + (b + 1)，那么可想而知 b + 1 = 4 k，于是有：
a = 5 k - 1  b = 4 k - 1
因为 (x₁, x₂)， (x₂, x₃)， (x₃, x₄)，(x₄, x₅) 均满足类似于 4 a = 5 b + 1 的式子，也自然满足上面的 a, b 关系。假设对应的 k 分别是k₁  k₂  k₃  k₄，根据 x₂ = 4 k₁ - 1 = 5 k₂ - 1 ，可以得出 k₁ : k₂ = 5 : 4，所以会有 ：
k₁ : k₂ = 5 : 4  k₂ : k₃ = 5 : 4  k₃ : k₄ = 5 : 4
k₁  k₂  k₃  k₄ 均是整数，所以不难找到最小的 k₁ 是 5×5×5，当然可以加任意倍数。那么的出来的桃子总数应该是 z = 5 x₁+1 = 5 (5 k₁ - 1) + 1 = 3125 k - 4 ,(k ∈ N)

解答

尼玛，如果知道公式了 x = 3125 k - 4 ，答案不就是掏出来计算器然后计算一下的问题叻嚒 ! 前 10 个结果是 ：

3121 6246 9371 12496 15621 18746 21871 24996 28121 31246

int monkey(int n)
 2 {
 3     int res, left, count;    // 桃子总数 、 剩下的桃子数 、 可以分的猴子数
 4    
 5     left = res = 1;
 6     count = 0;
 7     while(1){
 8         if((left - 1) % 5 == 0){    // 可以再分一个猴子
 9             ++count;
10             left = (left - 1) / 5 * 4;
11         }else if(count != n){    // 不可以再分猴子了
12             left = ++res;
13             count = 0;
14         }
15         if(count == n)    // 满足猴子总数， okay， 找到了
16             return res;
17     }
18 }

在上面程序的基础上很容易修改，然后求出来多个结果来，下面给出一个简单的扩展程序，max 用来限定桃子不超过的数目 ：

int monkey2(int n, int max, int *sum)
 2 {
 3     int res, left, count;    // 桃子总数 、 剩下的桃子数 、 可以分的猴子数
 4     int i = 0;    // 找到的解的个数
 5    
 6     left = res = 1;
 7     count = 0;
 8     while(1){
 9         if((left - 1) % 5 == 0){    // 可以再分一个猴子
10             ++count;
11             left = (left - 1) / 5 * 4;
12         }else if(count != n){    // 不可以再分猴子了
13             left = ++res;
14             count = 0;
15         }
16         if(count == n){    // 满足猴子总数， okay， 找到了
17             sum[i++] = res;
18             left = ++res;
19             count = 0;
20         }
21         if(res > max)
22             return i;
23     }
24 }

Read full article from 猴子分桃 - Ryan in C++ - 博客园