n个人围成一圈(1-n号),顺序排号,从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来几号的那位 暂定n<50
时间: 2023-07-16 14:12:22 浏览: 39
这是一个经典的约瑟夫问题(Josephus problem),可以使用递归或循环来解决。
以下是使用循环的解决方案,时间复杂度为O(n):
```
int josephus(int n) {
// 创建一个长度为n的数组,用于表示每个人是否已经退出圈子
bool* arr = new bool[n];
memset(arr, false, n);
// count表示当前位置,out表示已经退出的人数,num表示当前报的数
int count = 0, out = 0, num = 0;
while (out < n - 1) { // 只有最后一个人留下来,循环结束
if (!arr[count]) { // 如果当前位置的人还没有退出圈子
num++;
if (num == 3) { // 报数为3,退出圈子
arr[count] = true;
num = 0;
out++;
}
}
count++;
if (count == n) { // 到达数组末尾,从头开始
count = 0;
}
}
// 找到最后一个没有退出圈子的人
for (int i = 0; i < n; i++) {
if (!arr[i]) {
return i + 1;
}
}
delete[] arr;
return -1;
}
```
例如,当n=5时,最后留下的是原来的3号。