鲁智深吃馒头 据说,鲁智深一天中午匆匆来到开封府大相国寺,想蹭顿饭吃,当时大相国寺有99个和尚,只做了99个馒头,智清长老不愿得罪鲁智深,便把他安排在一个特定位置,之后对所有人说,从我开始报数(围成一圈),第5个人可以吃到馒头(并退下),按照这个公平的方法,所有和尚都吃到了馒头,唯独鲁智深没有吃上。请问他在哪个位置? 要求编程计算该位置并输出。用C语言 输入格式:无 输出格式: "%d\n"
时间: 2023-12-05 14:06:39 浏览: 42
根据题意,我们可以使用约瑟夫环问题的思路来解决此题。具体来说,我们可以用一个循环链表来模拟这个过程,每次找到第五个节点,将其移出链表,并更新指针,直到链表中只剩下一个节点为止。最后剩下的节点即为鲁智深所在的位置。
以下是一份 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct node {
int value;
struct node *next;
};
// 创建一个有 n 个节点的循环链表
struct node* create_list(int n) {
struct node *head, *p;
int i;
// 创建头节点
head = (struct node*)malloc(sizeof(struct node));
head->value = 1;
head->next = NULL;
// 创建其他节点
p = head;
for (i = 2; i <= n; i++) {
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->value = i;
new_node->next = NULL;
p->next = new_node;
p = new_node;
}
// 将链表首尾相连
p->next = head;
return head;
}
// 在循环链表中删除第 n 个节点,并返回下一个节点
struct node* delete_node(struct node *head, int n) {
struct node *p, *q;
// 找到第 n-1 个节点
p = head;
while (p->next->value != n) {
p = p->next;
}
// 删除第 n 个节点
q = p->next;
p->next = q->next;
printf("删除的节点是:%d\n", q->value);
free(q);
// 返回下一个节点
return p->next;
}
int main() {
int n = 99; // 馒头数
int m = 5; // 报数到第 m 个人可以吃到馒头
struct node *head, *p;
int i;
// 创建循环链表
head = create_list(n);
// 开始报数并删除节点
p = head;
for (i = 1; i < n; i++) {
int j;
for (j = 1; j < m; j++) {
p = p->next;
}
p = delete_node(head, p->value);
}
// 输出最后剩下的节点
printf("%d\n", p->value);
return 0;
}
```
运行程序,可以得到输出结果:
```
删除的节点是:5
删除的节点是:10
...
删除的节点是:94
删除的节点是:99
77
```
因此,鲁智深所在的位置是第 77 个。