有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。用c++实现
时间: 2023-12-23 18:24:42 浏览: 70
基于Java的银行排号系统的设计与实现.zip
5星 · 资源好评率100%
这道题可以使用循环链表来解决。首先,我们可以创建一个循环链表,将n个人依次加入链表中。然后,从第一个人开始报数,每报到3的人就将其从链表中删除。直到链表中只剩下一个人为止,这个人就是最后留下的人。
以下是C++实现代码:
```
#include <iostream>
using namespace std;
struct Node {
int num;
Node* next;
};
int main() {
int n = 0, m = 3;
cout << "请输入围成圈的人数:";
cin >> n;
// 创建循环链表
Node* head = new Node{1, nullptr};
Node* cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new Node{i, nullptr};
cur = cur->next;
}
cur->next = head;
// 报数并删除
Node* pre = cur;
cur = head;
int count = 0;
while (cur->next != cur) {
count++;
if (count == m) {
pre->next = cur->next;
cout << "编号为:" << cur->num << " 的人出局" << endl;
delete cur;
cur = pre->next;
count = 0;
} else {
pre = cur;
cur = cur->next;
}
}
// 输出最后留下的人
cout << "最后留下的是:" << cur->num << " 号" << endl;
return 0;
}
```
阅读全文