有n个人围成一圈,顺序排号。从第一人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。 程序的运行示例如下: 请输入人数:30 30个人中最后留下的是第29号。 输入提示:"请输入人数:" 输入格式:"%d" 输出提示: "%d个人中最后留下的是第%d号。" 用c语言编写程序
时间: 2024-03-14 16:46:10 浏览: 9
好的,这是一个经典的约瑟夫问题,可以用循环链表或者递归的方式解决。我这里给您提供一种循环链表的实现方式,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int num; // 编号
struct Node *next; // 下一个节点指针
} Node;
// 初始化循环链表,返回头节点
Node *initList(int n) {
Node *head = (Node *)malloc(sizeof(Node));
head->num = 1;
head->next = NULL;
Node *cur = head;
for (int i = 2; i <= n; i++) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->num = i;
newNode->next = NULL;
cur->next = newNode;
cur = newNode;
}
cur->next = head; // 将链表首尾相连,形成循环链表
return head;
}
// 模拟游戏过程,返回最后一个节点(即获胜者)
Node *playGame(Node *head) {
Node *cur = head;
while (cur->next != cur) { // 循环直到链表中只剩一个节点
Node *prev = cur;
for (int i = 0; i < 2; i++) { // 每次找到第三个节点(即报数为3的节点),并删除
prev = cur;
cur = cur->next;
}
prev->next = cur->next; // 删除节点
free(cur);
cur = prev->next; // 继续从下一个节点开始报数
}
return cur; // 返回最后一个节点(即获胜者)
}
int main() {
int n;
printf("请输入人数:");
scanf("%d", &n);
Node *head = initList(n);
Node *winner = playGame(head);
printf("%d个人中最后留下的是第%d号。\n", n, winner->num);
return 0;
}
```
代码中用 `Node` 结构体表示链表节点,包含编号和下一个节点指针。`initList` 函数初始化循环链表,返回头节点。`playGame` 函数模拟游戏过程,返回最后一个节点(即获胜者)。`main` 函数中读入人数,初始化链表,模拟游戏过程,输出获胜者的编号。
希望可以帮到您!