josephus问题c语言
时间: 2023-10-05 10:09:56 浏览: 47
Josephus 问题是一个经典的问题,描述如下:在固定的人数 N 中,从编号为 1 的人开始报数,报到 M 的人出圈,直到最后只剩下一人,问剩下的人原来的编号是多少?
以下是使用 C 语言解决 Josephus 问题的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
int josephus(int n, int m) {
int i, s = 0;
for (i = 2; i <= n; i++) {
s = (s + m) % i;
}
return s + 1;
}
int main() {
int n, m;
printf("请输入人数 N 和报数 M:\n");
scanf("%d%d", &n, &m);
int survivor = josephus(n, m);
printf("最后幸存者的编号是:%d\n", survivor);
return 0;
}
```
在上述代码中,`josephus` 函数使用了数学公式求解最后幸存者的编号,`main` 函数则是读入输入,调用 `josephus` 函数并输出结果。
相关问题
c语言josephus问题解决步骤
C语言中解决Josephus问题的步骤如下:
1. 首先,需要定义一个循环链表来表示参与游戏的人员。可以使用结构体来表示每个人员的编号和下一个人的指针。
2. 然后,需要根据输入的人数和计数的步长来初始化循环链表。使用循环语句创建指定数量的结点,并将结点编号和下一个结点的指针设置正确。
3. 接下来,需要确定一个起始位置,这个位置是从哪个人开始计数。可以让用户输入一个起始编号,或者设置默认值。
4. 确定起始位置后,就可以开始计数并淘汰人员。使用一个循环计数器,从起始位置开始一次计数,当计数器达到指定步长时,将当前结点从链表中删除。
5. 删除结点后,需要更新链表的指针,确保链表仍然形成一个循环。具体操作是将当前结点的下一个结点指针赋值给前一个结点,从而跳过被删除的结点。
6. 重复上述步骤,直到循环链表中只剩下一个结点为止。这个结点即为最终幸存者的位置。
7. 最后,输出最终幸存者的编号,游戏结束。
总结起来,解决Josephus问题的步骤包括:定义循环链表、初始化链表和起始位置、计数和删除结点、更新链表指针、重复直到只剩一个结点、输出幸存者的编号。
josephus问题(ⅲ)c语言
下面是使用递推公式求解 Josephus 问题的 C 语言代码:
```c
#include <stdio.h>
int josephus(int n, int m) {
int f = 0;
for (int i = 2; i <= n; i++) {
f = (f + m) % i;
}
return f + 1;
}
int main() {
int n, m;
printf("请输入人数 n 和出圈间隔 m:");
scanf("%d%d", &n, &m);
int ans = josephus(n, m);
printf("最后剩下的人的编号为:%d\n", ans);
return 0;
}
```
可以看到,C 语言的代码与 Python 代码的结构基本相同,只是语法有所区别。在 C 语言中,需要使用循环来计算最后剩下的人的编号。同时,需要注意整数除法的问题。在 C 语言中,两个整数相除的结果是整数,因此需要将计算过程中的中间结果转换为浮点数,再进行除法运算。