点击蓝字 关注我们
第二节 约瑟夫环问题
在2024年春节联欢晚会上，魔术师刘谦时隔五年再次登台，带着电视机前的观众朋友们见证奇迹！现在我们回顾一下这次生动的魔术表演。
首先我们有四张扑克牌，我们把它们标记为A，B，C，D。然后我们将这些扑克牌对折，撕开，并叠在一起。
1.起始状态：
A1 B1 C1 D1 A2 B2 C2 D2
当然，魔术中的一个步骤（按照我们的名字汉字个数将牌重新排序），这并不影响。比如我的名字是三个字，结果为：
D1 A2 B2 C2 D2 A1 B1 C1
我们将此作为起始状态吧！
第二步是将最前面三张插到中间任何一个位置。比如我这样做。
2.第二次操作后：
C2 D2 D1 A2 B2 A1 B1 C1
我们可以看到第一张排和最后一张牌是相同的，这是魔术的关键。
我们把第一张牌C2取出来。
D2 D1 A2 B2 A1 B1 C1
第三步按照南北方或者自定义方式将前面的牌插到中间。比如我是北方人，我这样做。
3.第三次操作后：
A2 B2 A1 B1 D2 D1 C1
我们可以看到最后一张仍然是C。
第四步按照性别将前面一张或两张扔掉。
4.第四次操作后：
B2 A1 B1 D2 D1 C1
第五步按照“见证奇迹的时刻”七个字放牌，每念一遍放一张牌到最后面，七次过后。
5.第五次操作后：
A1 B1 D2 D1 C1 B2
这次我们的C牌到了倒数第二个位置。
6.第六次操作：
好运留下来：
B1 D2 D1 C1 B2 A1
烦恼丢出去：
D2 D1 C1 B2 A1
好运留下来,烦恼丢出去:
C1 B2 A1 D2
好运留下来,烦恼丢出去:
A1 D2 C1
好运留下来,烦恼丢出去:
C1 A1
好运留下来,烦恼丢出去:
C1
此时我们就剩最后一张牌，C1牌，就是取出来的C2牌的另一半。
这是巧合吗？不是的，这在数学上称为约瑟夫环问题，接下来我们用编程的思想去思考一下约瑟夫环问题。
约瑟夫环问题是一个古老而经典的数学问题，它描述了一个有 n 个人的圆圈，每个人都有一个编号，从某个位置开始报数，报到第 m 个人的时候，该人出列，然后重新开始报数。
让我们通过一个简单的例子来讲解约瑟夫环问题的解决过程：
假设现在有6个人，我们给他们编号1-6，报数间隔为2,从1号开始。我们用X来表示此人已经出列。
1.起始状态：
1 2 3 4 5 6
2.第一轮报数后，6移除后下一个为1，所以移除3：
1 X 3 X 5 X
3.第二轮报数后,3移除后从5开始，所以移除1：
1 X X X 5 X
3.第三轮报数后：
X X X X 5 X
我们可以看到，剩下的是编号为5的人。
用代码表示这个过程：
#include <iostream>using namespace std;#include<vector>void circle(int n, int m) {// 创建一个大小为 n 的数组，表示约瑟夫环vector<int> circle(n);// 初始化数组，表示每个人的编号for (int i = 0; i < n; ++i) {circle[i] = i + 1;}int index = 0; // 当前索引位置// 循环直到只剩一个人while (n > 1) {// 找到下一个被移除的位置index = (index + m - 1) % n;// 输出当前被移除的人cout << "位置" << circle[index] << "出列" << endl;// 将当前位置的人移除，并将后面的人前移for (int i = index; i < n - 1; ++i) {circle[i] = circle[i + 1];}// 减少人的数量--n;}// 输出最后剩下的人的编号cout << "最后一个幸存者的位置为:" << circle[0] << endl;}int main() {int n = 6; // 人的总数int m = 2; // 报数的间隔circle(n, m);system("pause");return 0;}
结果如下：
位置2出列位置4出列位置6出列位置3出列位置1出列最后一个幸存者的位置为:5
与魔术结合起来看，这个5号代表的就是C1牌，经过循环筛选后，留下来的就是我们需要的那张牌。
我们用c++代码来解决这个问题，用来求当给出总个数和间隔值时，经过循环筛选最后留下的值是哪个位置：
#include <iostream>using namespace std;#include <list>int circle(int n, int m) {list<int> people;// 初始化队列for (int i = 1; i <= n; ++i) {people.push_back(i);}auto it = people.begin();// 循环直到队列中只剩一个人while (people.size() > 1) {// 移动到第 m 个人for (int i = 1; i < m; ++i) {++it;if (it == people.end()) {it = people.begin(); // 循环到队列开头}}// 移除当前位置的人，并重新初始化迭代器it = people.erase(it);if (it == people.end()) {it = people.begin(); // 循环到队列开头}}// 返回最后剩下的人的位置return *people.begin();}int main() {int n, m;cout << "输入总人数为: ";cin >> n;cout << "输入报数间隔为: ";cin >> m;int survivor = circle (n, m);cout << "最后一个幸存者的位置为: " << survivor << endl;system("pause");return 0;}
手动输入后结果为：
输入总人数为: 6输入报数间隔为: 2最后一个幸存者的位置为: 5
我们根据这个程序可以得出结果，报数间隔为2，每当个数为2的n次方时，幸存者的位置总是1，读者可以尝试一下。
END
往期推荐
