强盗分赃的金币数目探索

本题是一道编程题，涉及到了强盗分赃的数学问题，题目描述了一个情景：五个强盗抢得了一批金币，他们试图平均分配，但由于金币数量不能被完美地均分为五份，强盗们决定每晚轮流拿走一个金币，然后将剩余金币分成五等份，直到最后一天晚上。问题是求出什么样的初始金币数量可以满足这个分赃规则。 首先，题目提供了三种不同的解题思路： 1. **程序实现**: - 使用递归算法：定义一个函数 `func`，输入当前金币数量 `num`，检查它减去1后能否被5整除。如果可以，并且已经找到了5种可能的分配方式（`count` 达到5），则返回递归调用 `func(num/5*4)`。如果无法整除或者达到5次递归，返回相应的结果。通过遍历所有可能的金币数量，找出满足条件的那些。 2. **数学分析**: - 方法二通过逆向思维：从最后一个强盗开始，依次计算每个强盗分完后剩余的金币数，直到第一个强盗。发现金币总数与 x 的关系式为 `(12x+8)+53(x+1)/256`，其中 x 最小为255，因此初始金币总数最少为3121。 - 方法三：观察分赃过程，引入4个假想金币来保持每次分赃后剩余的金币数量不变。这意味着金币总数 n 必须是5^5的倍数加4，即 n = k * (5^5) + 4，k 是大于1的整数。最小的 n 就是 5^5 - 4 = 3121。 3. **代码示例**: - 提供的 C++ 代码片段展示了如何用递归实现该问题。函数 `makeDivsion` 通过枚举从1到n的所有可能的初始金币数，对于每个数，检查是否能被分给5个强盗后每人分到整数个金币，如果可以，输出该数字，否则继续下一次循环。如果没有找到任何可能，最后输出 "impossible"。 解决这个问题的关键在于找到初始金币数量，它必须满足每个强盗拿走一个后，剩余的金币可以被均匀分成5份。通过递归、数学公式分析或者编程实现，我们可以确定可能的初始金币数范围，其中最小的为3121，其他则是5^5的倍数加4。如果输入的n小于3121，那么不会有合适的初始金币数，输出 "impossible"。