用c++实现求猴王号数 让 N 只候选猴子围成一圈(最多100只猴子),从某位置起顺序编号为 1 ~ N 号; 从第 1 号开始报数,每轮从 1 报到 3 ,凡报到 3 的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数; 如此不断循环,最后剩下的一只猴子就选为猴王。
时间: 2023-06-18 21:02:47 浏览: 134
以下是用C++实现求猴王号数的代码:
```c++
#include <iostream>
using namespace std;
const int MAXN = 100;
int main() {
int n, k, m, a[MAXN];
cin >> n >> k >> m;
for (int i = 0; i < n; i++) a[i] = i + 1;
int left = n; // 剩余的猴子数
int i = k - 1, j = n - k; // i, j 分别为当前报数的猴子编号
while (left > 1) {
// 从 i 开始报数
for (int cnt = 0; cnt < m - 1; i = (i + 1) % n) {
if (a[i] > 0) cnt++; // 略过已退出圈子的猴子
}
// 从 j 开始报数
for (int cnt = 0; cnt < m - 1; j = (j + n - 1) % n) {
if (a[j] > 0) cnt++; // 略过已退出圈子的猴子
}
// 输出退出圈子的猴子编号
cout << a[i] << "," << a[j];
if (i != j) {
left -= 2; // 两只猴子同时退出圈子
a[i] = a[j] = 0;
} else {
left--; // 只有一只猴子退出圈子
a[i] = 0;
}
if (left) cout << ","; // 如果还有猴子剩余,输出分隔符
}
// 输出剩余的猴子编号,即猴王
for (int i = 0; i < n; i++) {
if (a[i]) {
cout << a[i] << endl;
break;
}
}
return 0;
}
```
在该代码中,我们使用了一个数组 `a` 来存储猴子的编号,初始时编号为 `1, 2, ..., n`。变量 `left` 表示当前剩余的猴子数,初始值为 `n`。变量 `i` 表示当前报数的猴子编号,初始化为 `k-1`,因为数组下标从0开始,而猴子编号从1开始。变量 `j` 表示距离 `i` 顺时针方向第 `m-1` 个猴子的编号,初始化为 `n-k`,即距离 `i` 逆时针方向第 `m-1` 个猴子的编号。
我们使用两个 `for` 循环分别从 `i` 和 `j` 开始报数,每次报数时略过已退出圈子的猴子,如果报数到 3,则将该猴子从数组 `a` 中标记为退出圈子,将 `left` 减1。如果退出圈子的是两只猴子,则将它们的编号都标记为0,否则只标记退出圈子的猴子的编号为0。
最后,我们遍历数组 `a`,输出剩余的猴子编号,即猴王的编号。
阅读全文