猴子分桃的故事大体有两种描述:
描述 1 :五只猴子分桃。半夜,第一只猴子先起来,它把桃分成了个数相等的五堆,多出一只;于是,它吃掉了一个,拿走了一堆。第二只猴子起来一看,只有四堆桃,于是把四堆合在一起,分成相等的五堆,又多出一个;然后,它也吃掉了一个,拿走了一堆。剩下的三只猴子也都是这样分的。问:这堆桃至少有多少个?
描述 2 :海滩上有一堆桃子,五只猴子来分。第一只猴子把这堆桃子平均分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子把剩下的桃子又平均分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份。第三、第四、第五只猴子都是这样做的,问海滩上原来最少有多少个桃子?
分析
程序猿一般这样看问题:总之桃子数目是整数,me 就从 1 开始试,然后分给猴子们,如果可以按题目要求的分法(去掉 1 个然后平均分 5 份,剩下 4 份)分 5 个猴子不就可以了 ? 真是不动脑筋的思考方案呀,尼玛 ! 不过这的确是一种万能的解决方案,对于本题来说,程序也不会运行很久。
现在从一个非程序猿的角度看问题。这里主要是要捕捉到它们的数量关系。
假设第二个猴子拿了 x2 个桃子,第三个猴子拿了 x3 个,那么有这么个关系: 4 x2 = 5 x3 + 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
因为 (x1, x2), (x2, x3), (x3, x4),(x4, x5) 均满足类似于 4 a = 5 b + 1 的式子,也自然满足上面的 a, b 关系。假设对应的 k 分别是k1 k2 k3 k4,根据 x2 = 4 k1 - 1 = 5 k2 - 1 ,可以得出 k1 : k2 = 5 : 4,所以会有 :
k1 : k2 = 5 : 4 k2 : k3 = 5 : 4 k3 : k4 = 5 : 4
k1 k2 k3 k4 均是整数,所以不难找到最小的 k1 是 5×5×5,当然可以加任意倍数。那么的出来的桃子总数应该是 z = 5 x1+1 = 5 (5 k1 - 1) + 1 = 3125 k - 4 ,(k ∈ N)
解答
尼玛,如果知道公式了 x = 3125 k - 4 ,答案不就是掏出来计算器然后计算一下的问题叻嚒 ! 前 10 个结果是 :
3121 6246 9371 12496 15621 18746 21871 24996 28121 31246
Read full article from 猴子分桃 - Ryan in C++ - 博客园