C++程序模拟2024春晚刘谦魔术《守岁共此时》约瑟夫环问题 ！_刘谦的魔术时光c++

网上冲浪发现有大佬模拟了2024春晚刘谦魔术《守岁共此时》，感觉非常有趣！！于是乎便借鉴改写成了C++程序。
参考：春晚刘谦魔术的模拟程序

**约瑟夫环（Josephus problem）**是一个经典的数学问题，最早由古罗马历史学家弗拉维奥·约瑟夫斯提出，但它的名字是在19世纪由德国数学家约瑟夫·乔瑟夫斯（Josef Stein）命名的。
**问题的描述是这样的：**假设有n个人（编号从1到n）站成一个圆圈，从第一个人开始报数，报到某个数字（例如k）的人就被杀死，然后从下一个人开始重新报数并继续这个过程，直到只剩下一个人留下来。
分析：
（1）假设有2张牌，编号分别是1和2。首先将1放到后面，扔掉2。剩下的就是最开始放在最上边的那张1。
（2）比如有8张牌，编号分别是1、2、3、4、5、6、7、8。
第一轮会把2、4、6、8扔掉，剩下1、3、5、7按顺序放在后面，又退化成了4张牌的情况。
第二轮会把3、7扔掉，剩下1、5按顺序放在后面，又退化成了2张牌的情况。
第三轮把5扔掉，剩下1，就是最初在最前面的那张。
**结论：**如果牌的张数是2^n，最后剩下的一定是最开始放在牌堆顶的那张。

魔术流程：
1、4张牌对折后撕开，就是8张，叠放在一起就是ABCDABCD。注意，ABCD四个数字是完全等价的。
2、根据名字字数，把顶上的牌放到下面，但怎么放都不会改变循环序列的相对位置。譬如2次，最后变成CDABCDAB；譬如3次，最后换成DABCDABC。但无论怎么操作，第4张和第8张牌都是一样的。
3、把顶上3张插到中间任意位置。这一步非常重要！因为操作完之后必然出现第1张和第8张牌是一样的！以名字两个字为例，可以写成BxxxxxxB（这里的x是其他和B不同的牌）。
4、拿掉顶上的牌放到一边，记为B。剩下的序列是xxxxxxB，一共7张牌。
5、南方人/北方人/不确定，分别拿顶上的1/2/3张牌插到中间，但是不会改变剩下7张牌是xxxxxxB的结果。
6、男生拿掉1张，女生拿掉2张。也就是男生剩下6张，女生剩下5张。分别是xxxxxB和xxxxB。
7、循环7次，把最顶上的放到最底下，男生和女生分别会是xxxxBx和xxBxx。
8、最后执行约瑟夫环过程！操作到最后只剩下1张。当牌数为6时（男生），剩下的就是第5张牌；当牌数为5时（女生），剩下的就是第3张牌。Bingo！就是第4步拿掉的那张牌！

下面是C++模拟代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// 定义一个函数，用于把牌堆顶n张牌移动到末尾
vector<char> moveCardBack(int n, vector<char>& arr) {
    // 循环n次，把队列第一张牌放到队列末尾
    for (int i = 0; i < n; i++) {
        char moveCard = arr[0]; // 第一张牌
        arr.erase(arr.begin()); // 删除第一张牌
        arr.push_back(moveCard); // 放到末尾
    }
    return arr;
}

// 定义一个函数，用于把牌堆顶n张牌移动到中间的任意位置
vector<char> moveCardMiddleRandom(int n, vector<char>& arr) {
    // 插入在arr中的的位置，随机生成一个idx
    // 这个位置必须是在n+1到arr.size()-1之间
    int idx = rand() % (arr.size() - n - 1) + n + 1;
    // 执行插入操作
    vector<char> newArr;
    newArr.insert(newArr.end(), arr.begin() + n, arr.begin() + idx);
    newArr.insert(newArr.end(), arr.begin(), arr.begin() + n);
    newArr.insert(newArr.end(), arr.begin() + idx, arr.end());
    return newArr;
}

int main() {
    srand(time(0)); // 设置随机数种子

    // 步骤1：初始化8张牌，假设为"ABCDABCD"
    vector<char> arr = {'A', 'B', 'C', 'D', 'A', 'B', 'C', 'D'};
    cout << "步骤1：拿出4张牌，对折撕成8张，按顺序叠放。" << endl;
    cout << "此时序列为：";
    for (const auto &card : arr)
        cout << card;
    cout << "\n---" << endl;

    // 步骤2（无关步骤）：名字长度随机选取，这里取2到5（其实任意整数都行）
    int nameLen = rand() % 4 + 2;
    // 把nameLen张牌移动到序列末尾
    arr = moveCardBack(nameLen, arr);
    cout << "步骤2：随机选取名字长度为" << nameLen << "，把第1张牌放到末尾，操作" << nameLen << "次。" << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤3（关键步骤）：把牌堆顶三张放到中间任意位置
    arr = moveCardMiddleRandom(3, arr);
    cout << "步骤3：把牌堆顶3张放到中间的随机位置。" << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤4（关键步骤）：把最顶上的牌拿走
    char restCard = arr[0]; // 最顶上的牌
    arr.erase(arr.begin()); // 移除最顶上的牌
    cout << "步骤4：把最顶上的牌拿走，放在一边。" << endl;
    cout << "拿走的牌为：" << restCard << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤5（无关步骤）：根据南方人/北方人/不确定，把顶上的1/2/3张牌插入到中间任意位置
    // 随机选择1、2、3中的任意一个数字
    int moveNum = rand() % 3 + 1;
    arr = moveCardMiddleRandom(moveNum, arr);
    string region = (moveNum == 1) ? "南方人" : (moveNum == 2) ? "北方人" : "不确定自己是哪里人";
    cout << "步骤5：我" << region << "，把" << moveNum << "张牌插入到中间的随机位置。" << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤6（关键步骤）：根据性别男或女，移除牌堆顶的1或2张牌
    int maleNum = rand() % 2 + 1; // 随机选择1或2
    for (int i = 0; i < maleNum; i++) { // 循环maleNum次，移除牌堆顶的牌
        arr.erase(arr.begin());
    }
    string gender = (maleNum == 1) ? "男" : "女";
    cout << "步骤6：我是" << gender << "生，移除牌堆顶的" << maleNum << "张牌。" << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤7（关键步骤）：把顶部的牌移动到末尾，执行7次
    for (int i = 0; i < 7; i++) {
        char topCard = arr[0];
        arr.erase(arr.begin());
        arr.push_back(topCard);
    }
    cout << "步骤7：把顶部的牌移动到末尾，执行7次" << endl;
    cout << "此时序列为：" << string(arr.begin(), arr.end()) << endl;
    cout << "---" << endl;

    // 步骤8（关键步骤）：执行约瑟夫环过程。把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。
    cout << "步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。" << endl;
    while (arr.size() > 1) {
        char luck = arr[0]; // 好运留下来
        arr.erase(arr.begin());
        arr.push_back(luck);
        cout << "好运留下来：" << luck << "\t\t此时序列为：" << string(arr.begin(), arr.end()) << endl;
        char sadness = arr[0]; // 烦恼都丢掉
        arr.erase(arr.begin());
        cout << "烦恼都丢掉：" << sadness << "\t\t此时序列为：" << string(arr.begin(), arr.end()) << endl;
    }
    cout << "---\n最终结果：剩下的牌为" << arr[0] << "，步骤4中留下来的牌也是" << restCard << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

步骤1：拿出4张牌，对折撕成8张，按顺序叠放。
此时序列为：ABCDABCD
---
步骤2：随机选取名字长度为4，把第1张牌放到末尾，操作4次。
此时序列为：ABCDABCD
---
步骤3：把牌堆顶3张放到中间的随机位置。
此时序列为：DABCABCD
---
步骤4：把最顶上的牌拿走，放在一边。
拿走的牌为：D
此时序列为：ABCABCD
---
步骤5：我南方人，把1张牌插入到中间的随机位置。
此时序列为：BCABCAD
---
步骤6：我是女生，移除牌堆顶的2张牌。
此时序列为：ABCAD
---
步骤7：把顶部的牌移动到末尾，执行7次
此时序列为：CADAB
---
步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。
好运留下来：C		此时序列为：ADABC
烦恼都丢掉：A		此时序列为：DABC
好运留下来：D		此时序列为：ABCD
烦恼都丢掉：A		此时序列为：BCD
好运留下来：B		此时序列为：CDB
烦恼都丢掉：C		此时序列为：DB
好运留下来：D		此时序列为：BD
烦恼都丢掉：B		此时序列为：D
---
最终结果：剩下的牌为D，步骤4中留下来的牌也是D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33