猴子选大王问题 用c++代码写出来
时间: 2023-06-15 07:07:33 浏览: 93
猴子选大王问题是一个经典的约瑟夫问题,可以使用链表来实现。以下是一个用C++实现的代码示例:
```c++
#include <iostream>
using namespace std;
struct Node {
int num;
Node* next;
};
int main() {
int n, m;
cout << "请输入猴子的总数:";
cin >> n;
cout << "请输入报数的数字:";
cin >> m;
// 创建循环链表
Node *head, *p, *q;
head = new Node;
head->num = 1;
p = head;
for (int i = 2; i <= n; i++) {
q = new Node;
q->num = i;
p->next = q;
p = q;
}
p->next = head; // 形成循环链表
// 开始选大王
p = head;
while (p != p->next) {
for (int i = 1; i < m; i++) {
p = p->next; // 报数
}
cout << "猴子" << p->num << "被淘汰了!" << endl;
p->num = p->next->num; // 将下一个猴子的编号赋值给当前猴子
q = p->next; // 删除下一个猴子
p->next = q->next;
delete q;
}
cout << "猴子" << p->num << "成为了大王!" << endl;
return 0;
}
```
该程序会在控制台上依次输出每个被淘汰的猴子的编号,并最终输出选出的大王的编号。