c++约瑟夫问题怎么解
时间: 2023-06-13 11:03:18 浏览: 65
约瑟夫问题是经典的数学问题,描述如下:有n个人围成一圈,从第一个人开始报数,报到m的人出圈,然后从出圈的下一个人开始重新报数,仍然是报到m的人出圈,直到所有人都出圈为止。问最后剩下的人是谁?
解决这个问题的一个经典方法是使用递归。具体步骤如下:
1. 定义一个递归函数,传入当前围成圈的人数n和要出圈的第m个人的编号。
2. 在函数中,判断当前圈中是否只剩下一个人,如果是,则返回该人的编号。
3. 如果圈中不止一个人,则从第一个人开始报数,报到m的人出圈,剩下的人组成新的圈。
4. 递归调用函数,传入新的圈中的人数和要出圈的第m个人的编号。
5. 返回递归调用的结果,即最后剩下的人的编号。
下面是C语言实现的递归解法:
```c
int Josephus(int n, int m) {
if (n == 1) {
return 1;
} else {
return (Josephus(n - 1, m) + m - 1) % n + 1;
}
}
```
其中,n表示围成圈的人数,m表示要出圈的第m个人的编号。函数返回最后剩下的人的编号。
相关问题
c++约瑟夫问题图解
约瑟夫问题是一个经典的数学问题,描述如下:有n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,直到所有人都出圈。求出出圈的顺序。
解决这个问题的一种常见方法是使用循环链表。首先创建一个循环链表,将n个人依次加入链表中。然后从第一个人开始,依次报数,每报到m就将该节点从链表中删除。直到链表中只剩下一个节点时,该节点即为最后一个出圈的人。
以下是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 (cur != cur->next) {
for (int i = 1; i < m; i++) {
cur = cur->next;
}
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
}
int ans = cur->val;
delete cur;
return ans;
}
int main() {
int n = 5, m = 3;
cout << josephus(n, m) << endl; // 输出3
return 0;
}
```
c++约瑟夫问题思路
约瑟夫问题是一个经典的数学问题,具体描述为:已知 n 个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出列;他的下一个人又从 1 开始报数,数到 m 的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。求出列顺序。
解决这个问题的一种常见方法是使用循环链表。具体思路如下:
1. 创建一个循环链表,包含 n 个节点,每个节点表示一个人。
2. 从第 k 个节点开始,依次遍历链表,数到第 m 个节点就将其删除。
3. 重复步骤 2 直到链表为空,每次删除的节点即为出列的顺序。
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 k, 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;
Node* prev = cur;
cur = head;
while (cur->next != cur) {
for (int i = 1; i < k; i++) {
prev = cur;
cur = cur->next;
}
for (int i = 1; i < m; i++) {
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
cout << cur->val << " ";
Node* tmp = cur;
cur = prev->next;
delete tmp;
}
int ans = cur->val;
delete cur;
return ans;
}
int main() {
int n = 5, k = 2, m = 3;
cout << josephus(n, k, m) << endl; // 输出:3 1 5 2
return 0;
}
```