C语言,有n个人,从头开始报数,第m个退出,后面的人继续从一开始报数,找出最后一个未退出的人的序号
时间: 2023-10-03 07:10:08 浏览: 76
这道题是经典的约瑟夫问题,可以使用链表或者循环数组来解决。
以下是使用循环数组的方法:
```c
#include <stdio.h>
int josephus(int n, int m) {
int a[n];
for (int i = 0; i < n; i++) {
a[i] = i + 1; // 初始化数组,编号从1开始
}
int i = -1, count = 0;
while (count < n - 1) { // 只剩一个人时退出循环
// 找到下一个要出局的人
int step = 0;
while (step < m) {
i = (i + 1) % n;
if (a[i] != 0) { // 如果这个人还没出局
step++;
}
}
a[i] = 0; // 标记这个人已经出局
count++;
}
// 找到最后一个未出局的人
for (int i = 0; i < n; i++) {
if (a[i] != 0) {
return a[i];
}
}
return -1;
}
int main() {
int n, m;
printf("请输入总人数n和报数m:");
scanf("%d%d", &n, &m);
int result = josephus(n, m);
printf("最后一个未退出的人的序号为:%d\n", result);
return 0;
}
```
该算法的时间复杂度为O(nm),空间复杂度为O(n)。如果使用链表,时间复杂度可以优化到O(n),但需要额外的空间来存储链表节点。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)