用C语言编程以前有这么一个益智游戏,沙滩上有n个猴子和一堆香蕉,晚上有一只猴子偷偷起来把香蕉分成n份,自己拿走了一份,多出来一根,扔进了海里,然后去睡觉了,后面所有的猴子都进行了同样的操作,分成n份,扔掉一根,拿走一份。问最少需要多少香蕉才能让所有猴子都完成该操作。(最后一只猴子扔掉后可以拿走0个,也算是n份均分)给定一个整数m,表示猴子的个数,题目要求输出最初的香蕉数。题目保证有解。 输入格式: 第一行输入n,后面依次输入n个数m。 输出格式: 所有输出在一行内完成,行末不能有多余空格,最后无回车结尾
时间: 2024-03-29 09:37:07 浏览: 119
C语言编一个数字益智小游戏
这道题目是经典的约瑟夫问题,可以使用逆推的方法求解。具体做法如下:
假设最初有 x 根香蕉,那么最后一个猴子拿走了 $\frac{x-1}{n}$ 根香蕉,剩下 $(n-1) \times \frac{x-1}{n}$ 根香蕉。那么倒数第二个猴子拿走了 $(n-1) \times \frac{x-1}{n^2}$ 根香蕉,剩下 $(n-1) \times (n-1) \times \frac{x-1}{n^2}$ 根香蕉。以此类推,可以得到第一个猴子拿走的香蕉数,即为 $(n-1) \times (n-1) \times \cdots \times (n-1) \times \frac{x-1}{n^n}$,其中共有 n-1 个 (n-1)。
因为题目保证有解,所以最终剩下的香蕉数必须是大于等于 n 的。因此,我们可以从 n 开始逐步增加 x 的值,直到满足所有猴子都能完成操作为止。
以下是 C 语言的代码实现:
阅读全文