【腾讯面试题】猴子分桃

小伙伴们，国庆假期有去哪些好玩的地方吗？

牛牛因为打羽毛球把脚崴了，只能在家里眼巴巴地望着，之前还在担心被拉去各种亲戚家串门，实际证明是我想太多😭😭😭

牛牛也只好化悲愤为动力，在家肝文，今天先暖个场，来道算法题，看看大家的技艺有没有生疏！

故事起源

有这么一天，森林里有一袋桃子🍑，来了5只猴子。

第一只猴子把这堆桃子平分为五份，多了一个。这只猴子把多的一个扔掉了，拿走了一份。

第二只猴子把剩下的桃子又平分成五份，又多了一个，它同样把多的一个扔掉了，拿走了一份。

第三、第四、第五只猴子也都是一样的情况，问袋子里原来最少有多少个桃子?

每只猴子的分桃情形

## 数学方法

看到这个题目的第一反应应该是——这是一个数学问题。

那么数学问题我们就用数学方法来解。下面牛牛就跟大家一起推演一下。

假设原有桃子x个，最后剩下y个。

第一只猴子扔了1个，又拿走了剩下的(x-1)个的1/5，相当于拿走的桃子数量一共为：1/5(x-1)+1；

剩下的桃子数量y = 4/5(x-1)；

第二只猴子来了，进行了同样的操作，相当于一共拿走的桃子数量为：1/5(4/5(x-1)-1)+1；

剩下的桃子数量为：y = 4/5(4/5(x-1)-1)

......

找到规律了吗？

每来一个猴子，剩下的桃子数量就从原数中减1，再乘4/5。这里有5只猴子，所以最后剩下的桃子个数为：

整理一下，得到式子：

因为x，y均为正整数，所以(x+4)必须是5×5×5×5×5的倍数。

题目中要求出最小的x，所以x+4=5^5，x=3125-4=3121。即开始最少有3121个桃子，最后剩余的桃子个数为1020个。

程序解法

我们接下来看看在程序世界里又如何解决这个问题呢！

根据题目我们只知道一个数字，那就是5个猴子。

所以桃子总共被分割了5次，每次分桃时候的桃子数量有5份多1个，至于每份是多少，不确定。

这也是本题最难的地方，每份的桃子个数不确定，而且每次分完桃子后，桃子的数量也不确定。

但是通过读题，我们发现，每个猴子都是进行同样的操作，即将桃子数先-1，然后再拿走1/5数量的桃子，只剩下4/5的桃子，并且下一个猴子又将重复这一操作。

这个操作总共重复5次，想到了什么？

这不就是程序里的循环嘛！一共循环了5次。

那我们先弄一个循环出来：

i = 1；// 循环的条件变量，表示是第几只猴子在操作
while i <= 5：
//分桃操作......
i++
复制代码

分桃具体怎么表示呢，通过上面的分析，就是将一个数-1，然后再乘以4/5，并且这个数要是正整数。

既然是桃子个数，那我们定义这个数为peach，分桃操作就表示为peach = (peach 整除 5) * 4，但有个条件，那就是每次分完会多出1个，所以得加上一个if条件：peach % 5 == 1。

整体代码如下：

i = 1
while i <= 5: 
#-1后才能分平均五份，不就代表着模5要等于1嘛 
    if peach % 5 == 1:
#每次分完后，就剩下原数量的 - 1后的五分之四了，所以每次要将这个数更新一下 
        peach = peach // 5 * 4
    i += 1
复制代码

现在的难点就只剩下peach该初始化为多少了。

内心os：要定义为啥数我也不知道，要是我知道的话那就不用求这个数了。。。

不要急，既然不知道，那我们就按照程序的思想，一个一个往上试嘛，大不了从1开始，找到那个能满足这个循环条件5次的数peach。

所以peach又将是一个循环的过程。于是得到以下代码：

i = 1
peach = 1
while i <= 5: 
#-1后才能分平均五份，不就代表着模5要等于1嘛 
    if peach % 5 == 1:
#每次分完后，就剩下原数量的 - 1后的五分之四了，所以每次要将这个数更新一下 
        peach = peach // 5 * 4
        i += 1
        continue
    i += 1
    peach += 1
复制代码

但仔细推敲，这个代码是有问题的。

因为这5次循环必须作为一个整体，连续满足，即i从1变化到5的过程中，要一直满足peach % 5 == 1，然后更新peach = peach // 5 * 4。

当5次中出现一次不满足时，i又要从1开始变化到5，而这个代码当出现不满足peach % 5 == 1时，peach会继续+1向上尝试，但是i却没有重置为1，这样就不满足题意了。

所以关于i的变化，在一次循环中要么+1，要么重置为1，但是peach却要从第一个数开始不断向上尝试，不重复。

所以要有一个数来记录已经尝试到的桃子个数，我们定义为count，于是最终代码如下：

def sum_peach():
      i = 1
      peach = 1
      count = 1
      while i <= 5: 
            #-1后才能分平均五份，不就代表着模5要等于1嘛 
            if peach % 5 == 1:
            #每次分完后，就剩下原数量的 - 1后的五分之四了，所以每次要将这个数更新一下 
                  peach = peach // 5 * 4
                  i += 1
            else:
                  i = 1
                  count += 1
                  peach = count
      return count
复制代码

最终求得count为3121，所以原来海滩上最少有3121个桃子。

这个解题思路其实是用到了程序的暴力求解，根据题目的限定条件，一个数一个数的去尝试判断，哪个数能符合题意就代表数值找到了。

桃桃复盘

之前我们就提到了，算法大多都是通过暴力法、贪心算法以及动态规划能够解决的，很多小伙伴花了大把时间研究后两者，但其实暴力法也是非常重要的，有些算法还只能通过这样简单粗暴的方式解决。

所谓大道至简，只要我们做足了准备，要真在面试时遇到了这样只能用暴力法解决的问题，不要怀疑，相信自己的判断！