n个人围成一圈,按1到n的顺序编号。从第一个人开始报数(从1到m报数),凡报到m的人退出圈子,问最后留下的是原来的第几号。 请用c++语言来实现编程
时间: 2024-02-21 08:58:19 浏览: 67
好的,这是一个经典的约瑟夫问题,可以使用循环链表来解决。以下是使用C++语言的代码实现:
```c++
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
Node(int x) : val(x), next(NULL) {}
};
int josephus(int n, int m) {
Node* head = new Node(1);
Node* cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new Node(i);
cur = cur->next;
}
cur->next = head;
while (n > 1) {
for (int i = 1; i < m; i++) {
cur = cur->next;
}
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
n--;
}
int result = cur->val;
delete cur;
return result;
}
int main() {
int n = 5, m = 3;
cout << josephus(n, m) << endl;
return 0;
}
```
在这个代码中,我们首先创建一个循环链表,然后从头节点开始遍历,每次遍历到第m个节点就将其删除,直到只剩下一个节点。最后返回剩下节点的编号即可。
阅读全文