100个苹果，如何拿到最后一个

去鹅厂参加面试的时候，一道笔试题，当时没有做出来，这里做一下记录和总结。

题面

有一堆苹果，一共100个，由你和另外一个人依次拿，每次拿的数目不小于1个，并且不大于5个，问要如何拿，才能保证你拿到最后一个。

分析

1. 100个苹果，想要拿到最后一个，说明你倒数第二次拿的数目刚好大于5个，也就是6个，也就是说你要拿到94个苹果中的最后一个；
2. 接上一步的结果，如何拿到94个苹果中的最后一个，思路是相同的，也就是要拿到88个苹果中的最后一个；
3. 继续，想要拿到88个苹果的最后一个，就要拿到82个苹果中的最后一个；
4. 以此类推，每次刚好要剩余6个，100/6=16...4，所以要拿到第4个苹果中的最后一个
5. 由此可知，应该由你先拿4个苹果，后面根据另一个人拿的数目，保证你们本轮拿到的评估的数目的和为6即可（即是解题的方法）

第1步中可不可以剩7个，答案是不行的，如果剩下7个苹果，那么另一人可以先拿1个，最后剩余6个，你就拿不到最后一个
那如果剩5个呢，那就被另一人一次性都拿走了。
所有重点就是每一轮两个人取走的苹果的数量和一定是6.

结论

应该由你先拿4个苹果，后面根据另一个人拿的数目，保证你们本轮拿到的苹果的数目的和为6即可

思想

从上面的推理过程可以看出，就是使用了一种递归的解题思路，递归是一种非常常见的解题思想，有兴趣的小伙伴可以更详细的了解一下

扩展

1. 递归思想
2. 扩展到n个苹果，如何拿到最后一个
3. 拿的数目改变为最多拿X个，那每轮拿的总和为X+1个即可
4. 该类题目的最后解答，结果一定是自行可控的，也就是说一定是自己先拿，并拿了确定的数目，接下来才能控制每一轮的总和；如果换成另一个人先拿，那结果便不可控，这一点很重要。