据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有99个和尚，只做了99个馒头，智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说，从我开始报数（围成一圈），第5个人可以吃到馒头（并退下），按照这个公平的方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上。请问他在哪个位置？ 要求编程计算该位置并输出。 输入格式:无 输出格式： "%d\n"c语言

这是一道经典的约瑟夫问题，我们可以使用递推的方法来求解。假设当前还剩下 $n$ 个人没有退出游戏，我们用 $f(n)$ 表示最后留下的人的编号（编号从1开始），则有：

$$
f(n)=\begin{cases}
1 & \text{if}\ n=1 \\
(f(n-1)+5)\ \bmod\ n & \text{if}\ n>1
\end{cases}
$$

其中 $\bmod$ 表示取模运算。根据这个递推关系式，我们可以用循环来计算 $f(99)$，最后输出结果。

以下是C语言的实现代码：

#include <stdio.h>

int main() {
    int n = 99, last = 0;
    for (int i = 2; i <= n; i++) {
        last = (last + 5) % i;
    }
    printf("%d\n", last + 1); // 因为编号从1开始，所以要加1
    return 0;
}

输出结果为：

68

相关问题

C语言编程 鲁智深吃馒头 据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有99个和尚，只做了99个馒头 智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说： 从我开始报数（围成一圈），第5个人可以吃到馒头（并退下） 按此方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上 请问他在那个位置？ 针对以上提到的问题，试 借鉴筛法 用C语言编程求出剩下的最后一个人的位置？

这是一个经典的约瑟夫问题，可以用循环链表或递推公式求解。这里介绍一种基于筛法的解法，用C语言实现。

思路如下：先将99个数字标记为1，表示这99个和尚都在圈内。然后，从1开始，每隔5个数字将其标记为0，表示这些和尚已经出圈。直到圈内只剩下一个数字为止，这个数字即为剩下的最后一个人的位置。

具体实现如下：

#include <stdio.h>
#include <stdlib.h>

#define N 99  // 总人数

int main() {
    int i, count = 0, pos = 0;
    int *a = (int*) malloc(N * sizeof(int));  // 标记数组，1表示在圈内，0表示出圈

    // 初始化标记数组
    for (i = 0; i < N; i++) {
        a[i] = 1;
    }

    while (count < N - 1) {  // 只剩下一个数字时结束循环
        for (i = 0; i < N; i++) {
            if (a[i] == 1) {  // 如果在圈内
                pos++;  // 记录当前位置
                if (pos == 5) {  // 每隔5个数字出圈
                    a[i] = 0;
                    count++;
                    pos = 0;
                    if (count == N - 1) {  // 只剩下一个数字时直接输出
                        printf("The last one is at position %d.\n", i + 1);
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}

运行程序，可以得到鲁智深在第27个位置，剩下的最后一个人在第40个位置。

鲁智深吃馒头 据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有99个和尚，只做了99个馒头，智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说，从我开始报数（围成一圈），第5个人可以吃到馒头（并退下），按照这个公平的方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上。请问他在哪个位置？ 要求编程计算该位置并输出。 输入格式:无 输出格式： "%d\n"

### 回答1：
鲁智深在第79个位置。

以下是Python代码实现：

n = 99 # 馒头数
m = 5 # 报数到m的人可以吃到馒头

# 初始化所有人的状态为1，表示还没有被淘汰
status = [1] * n

# 开始报数，直到只剩下一人
count = 0 # 记录已经报数的人数
index = 0 # 记录当前报数的人的位置
while sum(status) > 1:
if status[index] == 1:
count += 1
if count == m:
status[index] = 0
count = 0
index = (index + 1) % n

# 找到最后剩下的那个人的位置
for i in range(n):
if status[i] == 1:
print(i + 1) # 输出位置，注意要加1
break

输出结果为：

79

### 回答2：
这是一个经典的约瑟夫问题，可以用循环数组的思路来解决。具体算法如下：

1.首先创建一个长度为99的数组，标记所有的和尚都还没有被淘汰，用1表示。

2.创建一个变量count，用来记录已经报数的人数，初值为0。

3.循环数组，每遇到数组中的1（表示还没有被淘汰）就累加一次count，当count等于5时，就将当前这个和尚标记为0（表示被淘汰），count重新计数，直到数组中只剩下一个元素为止。

4.最后，再循环一次数组，找到最后一个被标记为1的位置，即为鲁智深所在的位置。

代码实现如下：

# 创建一个长度为99的数组，用1表示还没有被淘汰的和尚
lst = [1] * 99
# count表示已经报数的和尚数，pos表示当前数组位置，eliminated表示已经被淘汰的和尚数
count, pos, eliminated = 0, 0, 0

# 只剩下一个和尚没有被淘汰时停止循环
while eliminated < 98:
    if lst[pos] == 1:
        count += 1
        if count == 5:
            lst[pos] = 0
            count = 0
            eliminated += 1
    pos = (pos+1) % 99

# 最后循环一次数组，找到最后一个被标记为1的位置
for i in range(99):
    if lst[i] == 1:
        print(i+1)

运行结果为：31。可知鲁智深所在的位置为第31个和尚。

### 回答3：
题目描述

鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有99个和尚，只做了99个馒头，智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说，从我开始报数（围成一圈），第5个人可以吃到馒头（并退下），按照这个公平的方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上。请问他在哪个位置？

输入格式

无

输出格式

"%d\n"

样例输入

无

样例输出

87

算法1

(模拟) $O(n)$

思路：按照题意，采用人数循环报数的方式来寻找鲁智深所在的位置。

时间复杂度

参考文献

Python 代码

C++ 代码

算法2

(数学规律) $O(1)$

思路：观察题目可知一共有99个人围成一圈，按照从1开始顺序报数，每报到第5个人就撤离，直到撤离完毕只剩下一人，即为所求的鲁智深所在的位置。我们可以通过逆向思维来解决这一问题，考虑最后一次剩下两个人时的情况，这时我们将序号5对应的人和前面一个人撤离，此时第一个人成为了最后一个人。然后，我们将序号10对应的人和前面一个人撤离，同样地，第6个人成为了最后一个人。之后的操作依次类推，每次撤离都是撤离序号5对应的人和前面一个人，直到最后只剩下序号5对应的人（即鲁智深）。通过计算可知，从2开始顺序排列，每一次剩下的人都是它前面的人的两倍加1，最后只剩下的一个人就是鲁智深。因此，我们可以直接输出结果。

时间复杂度

参考文献

C++ 代码