详解基于C++实现约瑟夫环问题的三种解法
约瑟夫问题
约瑟夫问题是一个经典的问题,是一个圆圈里面有$n$个数字,从中每次删除第$m$个数字,求出每次删除的数字。简单的说,约瑟夫问题就是$n$个人围成一圈,从第一个人开始报数,报到$m$的人出圈,直到计算到最后一个人。
解法一:使用递推(模拟游戏过程)
思路:利用递归的思想模拟即可。假如最后剩下一个数据,则保留该数据,否则位置为 $s=(f+m)\ mod\ i $,$f$表示上一轮已经被删除数字的位置,$i$表示上一轮剩余数字个数,$m$为给定的数字。
代码:
int Josephus(int n, int m) {
if (n == 1) {
return 1;
}
return (Josephus(n - 1, m) + m - 1) % n + 1;
}
递归较为简便,但是处理的数据规模过大,会引起栈溢出等问题。
解法二:循环链表
思路:使用循环链表模拟过程,进行删除操作,直到链表剩下一个节点。
代码:
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
};
int Josephus(int n, int m) {
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;
while (head->next != head) {
int cnt = m % (n--);
if (cnt == 0) {
cnt = n;
}
Node* pre;
for (pre = head; pre->next != head; pre = pre->next) {
if (--cnt == 0) {
break;
}
}
Node* temp = pre->next;
pre->next = temp->next;
head = temp->next;
delete temp;
}
int res = head->val;
delete head;
return res;
}
int main() {
cout << Josephus(5, 3) << endl; // 输出3
cout << Josephus(8, 4) << endl; // 输出6
return 0;
}
解法三:数学归纳
思路:可以通过利用数学归纳法来证明一种对称性,然后根据对称性来推导出约瑟夫环问题的答案。设 $f(n)$ 表示当有$n$个人时最后留下的人在数列中的位置,则:
当 $n=1$ 时,$f(1)=0$。
当 $n>1$ 时,将编号改为从 $0$ 开始,第一个人编号为 $0$ ,对 $n-1$ 取模,设结果为 $x$,则:
$$ f(n,m)=\left{\begin{aligned} & 0 & n=1 \ & \left(f(n-1,m)+m\right)\ \% \ n & n>1 \end{aligned}\right. $$
代码:
int Josephus(int n, int m) {
int res = 0;
for (int i = 2; i <= n; i++) {
res = (res + m) % i;
}
return res + 1;
}
示例说明
例如,有 $5$ 个人 $(0, 1, 2, 3, 4)$ 依次报数,编号为 $0$ 的人从 $1$ 开始报数,假设报到 $3$ 的人出局,依次出局的顺序为 $2, 0, 4, 3$,因此最后剩下的是编号为 $1$ 的人。
可以通过调用以下代码进行验证:
cout << Josephus(5, 3) << endl;
输出为 $3$。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:详解基于C++实现约瑟夫环问题的三种解法 - Python技术站