【腾讯面试题】猴子分桃-轻识

故事起源

有这么一天，森林里有一袋桃子🍑，来了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 = 1while i <= 5: #-1后才能分平均五份，不就代表着模5要等于1嘛     if peach % 5 == 1:#每次分完后，就剩下原数量的 - 1后的五分之四了，所以每次要将这个数更新一下         peach = peach // 5 * 4    i += 1

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

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

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

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


i = 1peach = 1while 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个桃子。

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

桃桃复盘

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

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

---------------- END---------------

最后，欢迎加入帅地的知识星球，帅地会在星球知无不言，无论是 学习规划，offer 选择，简历修改，还是学习路线，帅地都会在 48 小时以内答复你的问题，并且根据你自身的情况，为你量身定制学习路线。

同时超全学习攻略也已经更新好了，小白跟着帅地的学习攻略学就行了

各类学习资料，项目资料都会提供给大家。

而且你有任何的疑惑，帅地都会答复你，并且星球里也有一群和你相同年龄的小伙伴在奋斗，都是未来的卷王

帅地会在星球会提供如下服务

1、【一对一咨询服务】48 小时以内超详细回答你的任何问题，包括写作等等，这是知识星球最重要的功能。最近一周就回答了十几个 offer 选择，校招等学习路线问题。

2、【学习攻略】校招这方面比较有经验，帅地会提供完整的学习攻略，并且随着时间的积累，这份攻略会越来越完善哦。

3、简历修改，项目等学习资源，offer 收割机嘉宾分享等等。

目前星球是专注于校招，在校生学习指导这块，一定可以让你少走弯路，已经有 670+ 位小伙伴加入，这里还有一些 20 元的优惠卷，如果你信的过帅地，那么欢迎你的加入。

点击阅读原文可以了解详情