n个人围成一圈,报到M离开,最后剩下的人编号是多少,用c语言实现,n最大2^31
时间: 2024-03-06 17:47:47 浏览: 52
为了避免整型溢出,我们需要使用 `long long` 类型来表示编号和计数器。
下面是 C 语言实现该问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
long long josephus(int n, int m)
{
long long s = 0;
for (int i = 2; i <= n; i++)
{
s = (s + m) % i;
}
return s + 1;
}
int main()
{
int n, m;
printf("Enter the number of people: ");
scanf("%d", &n);
printf("Enter the count to leave: ");
scanf("%d", &m);
printf("The chosen place is %lld\n", josephus(n, m));
return 0;
}
```
在 `josephus` 函数中,使用循环计算最后剩下的人的编号。
需要注意的是,此代码中使用了动态内存分配来存储编号数组。当 `n` 很大时,程序可能会出现内存不足的错误。如果需要处理更大的输入数据,可以考虑使用其他数据结构或算法来解决该问题。
相关问题
有n个人围成一圈从1-3报数,报道3的人自动退出,一直重复问剩下的最后一个人是几号用c语言来写该程序
以下是使用数组实现的C语言程序,每次报到3的人会被标记为已退出,直到只剩一个人为止:
```c
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i, count, pos = 0;
printf("请输入人数n:");
scanf("%d", &n);
int *arr = (int*)malloc(n * sizeof(int));
// 初始化数组
for (i = 0; i < n; i++) {
arr[i] = 1;
}
// 开始报数
count = 0;
while (1) {
if (arr[pos] == 1) {
count++;
if (count == 3) {
arr[pos] = 0; // 标记为已退出
count = 0;
}
}
pos = (pos + 1) % n;
if (arr[pos] == 1) {
if (--n == 1) {
break;
}
}
}
// 找到最后一个人的编号
for (i = 0; i < n; i++) {
if (arr[i] == 1) {
printf("最后一个人是%d\n", i + 1);
break;
}
}
free(arr);
return 0;
}
```
注意,这个程序使用了一个数组来记录每个人是否已退出。每次报数的时候,我们需要判断当前位置的人是否已退出,并计数。当计数器达到3时,我们将当前位置的人标记为已退出,并将计数器清零。同时,我们需要移动当前位置,跳过已退出的人。当只剩一个人时,我们就找到了最后一个人的编号。
c语言设有n个人围成一个圈,从编号为m的人开始由1开始报数,每次正好报到数k的人退出游戏,后面一个人重新由1开始报数。请求出最后剩下的那个人的编号。
这是一个经典的约瑟夫问题,可以使用递归或数学方法来解决。以下是使用递归的解决方案:
int josephus(int n, int k, int m) {
if (n == 1) {
return (m + k - 1) % n + 1;
} else {
int new_m = (m + k - 1) % n + 1;
return josephus(n - 1, k, new_m);
}
}
int main() {
int n = 10; // n个人围成一个圈
int k = 3; // 每次报数k个人
int m = 4; // 从编号为m的人开始
int last_person = josephus(n, k, m);
printf("最后剩下的人的编号是%d\n", last_person);
return 0;
}
这个程序将输出最后剩下的人的编号是5。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)