春晚刘谦魔术的模拟程序
昨晚春晚上刘谦的两个魔术表演都非常精彩，尤其是第二个魔术，他演绎了经典的约瑟夫环问题！
什么是约瑟夫环问题？
约瑟夫环（Josephus problem）是一个经典的数学问题，最早由古罗马历史学家弗拉维奥·约瑟夫斯提出，但它的名字是在19世纪由德国数学家约瑟夫·乔瑟夫斯（Josef Stein）命名的。
问题的描述是这样的：假设有n个人（编号从1到n）站成一个圆圈，从第一个人开始报数，报到某个数字（例如k）的人就被杀死，然后从下一个人开始重新报数并继续这个过程，直到只剩下一个人留下来。
问题的关键是找出存活下来的那个人的编号。
结合扑克牌解释约瑟夫环问题
1、考虑最简单的情况
假设有2张牌，编号分别是1和2。
首先将1放到后面，扔掉2。剩下的就是最开始放在最上边的那张1。
2、稍微复杂一点的情况，牌的张数是2的n次方
比如有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，最后剩下的一定是最开始放在牌堆顶的那张。
3、考虑任意的情况，牌的张数是2^n+m
比如牌的张数是11，等于8+3。把1放到后面，把2扔掉，把3放到后面，把4扔掉，把5放到后面，把6扔掉，现在剩下的编号序列是7、8、9、10、11、1、3、5，这又是8张牌的情况！最后一定剩下的是现在牌堆顶的7！
因此，只要提前知道牌的张数，就一定能马上推导出最终是剩下哪一张牌。一切的魔法都是数学！！都是算法！！
见证奇迹的时刻！魔术的流程
- 4张牌对折后撕开，就是8张，叠放在一起就是ABCDABCD。注意，ABCD四个数字是完全等价的。
- 根据名字字数，把顶上的牌放到下面，但怎么放都不会改变循环序列的相对位置。譬如2次，最后变成CDABCDAB；譬如3次，最后换成DABCDABC。但无论怎么操作，第4张和第8张牌都是一样的。
- 把顶上3张插到中间任意位置。这一步非常重要！因为操作完之后必然出现第1张和第8张牌是一样的！以名字两个字为例，可以写成BxxxxxxB（这里的x是其他和B不同的牌）。
- 拿掉顶上的牌放到一边，记为B。剩下的序列是xxxxxxB，一共7张牌。
- 南方人/北方人/不确定，分别拿顶上的1/2/3张牌插到中间，但是不会改变剩下7张牌是xxxxxxB的结果。
- 男生拿掉1张，女生拿掉2张。也就是男生剩下6张，女生剩下5张。分别是xxxxxB和xxxxB。
- 循环7次，把最顶上的放到最底下，男生和女生分别会是xxxxBx和xxBxx。
- 最后执行约瑟夫环过程！操作到最后只剩下1张。当牌数为6时（男生），剩下的就是第5张牌；当牌数为5时（女生），剩下的就是第3张牌。Bingo！就是第4步拿掉的那张牌！
下面是完整的 JavaScript 代码实现：
// 定义一个函数，用于把牌堆顶n张牌移动到末尾
function moveCardBack(n, arr) {
// 循环n次，把队列第一张牌放到队列末尾
for (let i = 0; i < n; i++) {
const moveCard = arr.shift(); // 弹出队头元素，即第一张牌
arr.push(moveCard); // 把原队头元素插入到序列末尾
}
return arr;
}
// 定义一个函数，用于把牌堆顶n张牌移动到中间的任意位置
function moveCardMiddleRandom(n, arr) {
// 插入在arr中的的位置，随机生成一个idx
// 这个位置必须是在n+1到arr.length-1之间
const idx = Math.floor(Math.random() * (arr.length - n - 1)) + n + 1;
// 执行插入操作
const newArr = arr.slice(n, idx).concat(arr.slice(0, n)).concat(arr.slice(idx));
return newArr;
}
// 步骤1：初始化8张牌，假设为"ABCDABCD"
let arr = ["A", "B", "C", "D", "A", "B", "C", "D"];
console.log("步骤1：拿出4张牌，对折撕成8张，按顺序叠放。");
console.log("此时序列为：" + arr.join('') + "\n---");
// 步骤2（无关步骤）：名字长度随机选取，这里取2到5（其实任意整数都行）
const nameLen = Math.floor(Math.random() * 4) + 2;
// 把nameLen张牌移动到序列末尾
arr = moveCardBack(nameLen, arr);
console.log(`步骤2：随机选取名字长度为${nameLen}，把第1张牌放到末尾，操作${nameLen}次。`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤3（关键步骤）：把牌堆顶三张放到中间任意位置
arr = moveCardMiddleRandom(3, arr);
console.log(`步骤3：把牌堆顶3张放到中间的随机位置。`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤4（关键步骤）：把最顶上的牌拿走
const restCard = arr.shift(); // 弹出队头元素
console.log(`步骤4：把最顶上的牌拿走，放在一边。`);
console.log(`拿走的牌为：${restCard}`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤5（无关步骤）：根据南方人/北方人/不确定，把顶上的1/2/3张牌插入到中间任意位置
// 随机选择1、2、3中的任意一个数字
const moveNum = Math.floor(Math.random() * 3) + 1;
arr = moveCardMiddleRandom(moveNum, arr);
console.log(`步骤5：我${moveNum === 1 ? '是南方人' : moveNum === 2 ? '是北方人' : '不确定自己是哪里人'}，\
把${moveNum}张牌插入到中间的随机位置。`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤6（关键步骤）：根据性别男或女，移除牌堆顶的1或2张牌
const maleNum = Math.floor(Math.random() * 2) + 1; // 随机选择1或2
for (let i = 0; i < maleNum; i++) { // 循环maleNum次，移除牌堆顶的牌
arr.shift();
}
console.log(`步骤6：我是${maleNum === 1 ? '男' : '女'}生，移除牌堆顶的${maleNum}张牌。`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤7（关键步骤）：把顶部的牌移动到末尾，执行7次
arr = moveCardBack(7, arr);
console.log(`步骤7：把顶部的牌移动到末尾，执行7次`);
console.log(`此时序列为：${arr.join('')}\n---`);
// 步骤8（关键步骤）：执行约瑟夫环过程。把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。
console.log(`步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。`);
while (arr.length > 1) {
const luck = arr.shift(); // 好运留下来
arr.push(luck);
console.log(`好运留下来：${luck}\t\t此时序列为：${arr.join('')}`);
const sadness = arr.shift(); // 烦恼都丢掉
console.log(`烦恼都丢掉：${sadness}\t\t此时序列为：${arr.join('')}`);
}
console.log(`---\n最终结果：剩下的牌为${arr[0]}，步骤4中留下来的牌也是${restCard}`);
这段代码实现了昨晚春晚上刘谦的第二个魔术表演的过程，并提供了详细的解释。享受魔术的魅力吧！
看到观看的人这么多，除了JavaScript，下面我补充了一些其他语言的实现
import random
# 定义一个函数，用于把牌堆顶n张牌移动到末尾
def move_card_back(n, arr):
for i in range(n):
move_card = arr.pop(0)
arr.append(move_card)
return arr
# 定义一个函数，用于把牌堆顶n张牌移动到中间的任意位置
def move_card_middle_random(n, arr):
idx = random.randint(n + 1, len(arr) - 1)
new_arr = arr[n:idx] + arr[0:n] + arr[idx:]
return new_arr
# 步骤1：初始化8张牌，假设为"ABCDABCD"
arr = ["A", "B", "C", "D", "A", "B", "C", "D"]
print("步骤1：拿出4张牌，对折撕成8张，按顺序叠放。")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤2（无关步骤）：名字长度随机选取，这里取2到5（其实任意整数都行）
name_len = random.randint(2, 5)
move_card_back(name_len, arr)
print("步骤2：随机选取名字长度为" + str(name_len) + "，把第1张牌放到末尾，操作" + str(name_len) + "次。")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤3（关键步骤）：把牌堆顶三张放到中间任意位置
arr = move_card_middle_random(3, arr)
print("步骤3：把牌堆顶3张放到中间的随机位置。")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤4（关键步骤）：把最顶上的牌拿走
rest_card = arr.pop(0)
print("步骤4：把最顶上的牌拿走，放在一边。")
print("拿走的牌为：" + rest_card)
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤5（无关步骤）：根据南方人/北方人/不确定，把顶上的1/2/3张牌插入到中间任意位置
# 随机选择1、2、3中的任意一个数字
move_num = random.randint(1, 3)
arr = move_card_middle_random(move_num, arr)
print("步骤5：我" + ("是南方人" if move_num == 1 else "是北方人" if move_num == 2 else "不确定自己是哪里人") + "，把" + str(move_num) + "张牌插入到中间的随机位置。")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤6（关键步骤）：根据性别男或女，移除牌堆顶的1或2张牌
male_num = random.randint(1, 2)
for i in range(male_num):
arr.pop(0)
print("步骤6：我是" + ("男" if male_num == 1 else "女") + "生，移除牌堆顶的" + str(male_num) + "张牌。")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤7（关键步骤）：把顶部的牌移动到末尾，执行7次
for i in range(7):
move_card = arr.pop(0)
arr.append(move_card)
print("步骤7：把顶部的牌移动到末尾，执行7次")
print("此时序列为：" + ''.join(arr) + "\n---")
# 步骤8（关键步骤）：执行约瑟夫环过程。把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。
print("步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。")
while len(arr) > 1:
luck = arr.pop(0)
arr.append(luck)
print("好运留下来：" + luck + "\t\t此时序列为：" + ''.join(arr))
sadness = arr.pop(0)
print("烦恼都丢掉：" + sadness + "\t\t此时序列为：" + ''.join(arr))
print("---\n最终结果：剩下的牌为" + arr[0] + "，步骤4中留下来的牌也是" + rest_card)
java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Main {
public static void main(String[] args) {
List<String> arr = new ArrayList<>();
arr.add("A");
arr.add("B");
arr.add("C");
arr.add("D");
arr.add("A");
arr.add("B");
arr.add("C");
arr.add("D");
System.out.println("步骤1：拿出4张牌，对折撕成8张，按顺序叠放。");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
Random rand = new Random();
int nameLen = rand.nextInt(4) + 2;
moveCardBack(nameLen, arr);
System.out.println("步骤2：随机选取名字长度为" + nameLen + "，把第1张牌放到末尾，操作" + nameLen + "次。");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
moveCardMiddleRandom(3, arr);
System.out.println("步骤3：把牌堆顶3张放到中间的随机位置。");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
String restCard = arr.remove(0);
System.out.println("步骤4：把最顶上的牌拿走，放在一边。");
System.out.println("拿走的牌为：" + restCard);
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
int moveNum = rand.nextInt(3) + 1;
moveCardMiddleRandom(moveNum, arr);
System.out.println("步骤5：我" + (moveNum == 1 ? "是南方人" : moveNum == 2 ? "是北方人" : "不确定自己是哪里人") + "，把" + moveNum + "张牌插入到中间的随机位置。");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
int maleNum = rand.nextInt(2) + 1;
for (int i = 0; i < maleNum; i++) {
arr.remove(0);
}
System.out.println("步骤6：我是" + (maleNum == 1 ? "男" : "女") + "生，移除牌堆顶的" + maleNum + "张牌。");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
for (int i = 0; i < 7; i++) {
String moveCard = arr.remove(0);
arr.add(moveCard);
}
System.out.println("步骤7：把顶部的牌移动到末尾，执行7次");
System.out.println("此时序列为：" + String.join("", arr));
System.out.println("---");
System.out.println("步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。");
while (arr.size() > 1) {
String luck = arr.remove(0);
arr.add(luck);
System.out.println("好运留下来：" + luck + "\t\t此时序列为：" + String.join("", arr));
String sadness = arr.remove(0);
System.out.println("烦恼都丢掉：" + sadness + "\t\t此时序列为：" + String.join("", arr));
}
System.out.println("---\n最终结果：剩下的牌为" + arr.get(0) + "，步骤4中留下来的牌也是" + restCard);
}
private static void moveCardBack(int n, List<String> arr) {
for (int i = 0; i < n; i++) {
String moveCard = arr.remove(0);
arr.add(moveCard);
}
}
private static void moveCardMiddleRandom(int n, List<String> arr) {
Random rand = new Random();
int idx = rand.nextInt(arr.size() - n - 1) + n + 1;
List<String> newArr = new ArrayList<>(arr.subList(n, idx));
newArr.addAll(arr.subList(0, n));
newArr.addAll(arr.subList(idx, arr.size()));
arr.clear();
arr.addAll(newArr);
}
}
以及c++代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
void moveCardBack(int n, std::vector<std::string>& arr) {
for (int i = 0; i < n; i++) {
std::string moveCard = arr[0];
arr.erase(arr.begin());
arr.push_back(moveCard);
}
}
void moveCardMiddleRandom(int n, std::vector<std::string>& arr) {
int idx = rand() % (arr.size() - n - 1) + n + 1;
std::vector<std::string> 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());
arr = newArr;
}
int main() {
srand(time(0));
std::vector<std::string> arr = {"A", "B", "C", "D", "A", "B", "C", "D"};
std::cout << "步骤1：拿出4张牌，对折撕成8张，按顺序叠放。" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
int nameLen = rand() % 4 + 2;
moveCardBack(nameLen, arr);
std::cout << "步骤2：随机选取名字长度为" << nameLen << "，把第1张牌放到末尾，操作" << nameLen << "次。" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
moveCardMiddleRandom(3, arr);
std::cout << "步骤3：把牌堆顶3张放到中间的随机位置。" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
std::string restCard = arr[0];
arr.erase(arr.begin());
std::cout << "步骤4：把最顶上的牌拿走，放在一边。" << std::endl;
std::cout << "拿走的牌为: " << restCard << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
moveCardMiddleRandom(rand() % 3 + 1, arr);
std::cout << "步骤5：我" << (rand() % 2 == 0 ? "是南方人" : "是北方人") << "，把" << rand() % 3 + 1 << "张牌插入到中间的随机位置。" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
int maleNum = rand() % 2 + 1;
for (int i = 0; i < maleNum; i++) {
arr.erase(arr.begin());
}
std::cout << "步骤6：我" << (maleNum == 1 ? "男" : "女") << "生，移除牌堆顶的" << maleNum << "张牌。" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
for (int i = 0; i < 7; i++) {
std::string moveCard = arr[0];
arr.erase(arr.begin());
arr.push_back(moveCard);
}
std::cout << "步骤7：把顶部的牌移动到末尾，执行7次" << std::endl;
std::cout << "此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::cout << "---" << std::endl;
std::cout << "步骤8：把牌堆顶一张牌放到末尾，再移除一张牌，直到只剩下一张牌。" << std::endl;
while (arr.size() > 1) {
std::string luck = arr[0];
arr.erase(arr.begin());
arr.push_back(luck);
std::cout << "好运留下来: " << luck << "\t\t此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
std::string sadness = arr[0];
arr.erase(arr.begin());
std::cout << "烦恼都丢掉: " << sadness << "\t\t此时序列为: ";
for (const std::string& card : arr) {
std::cout << card;
}
std::cout << std::endl;
}
std::cout << "---\n最终结果: " << arr[0] << ", 步骤4中留下来的牌也是" << restCard << std::endl;
return 0;
}
作者：小u
来源：juejin.cn/post/7332865125640044556
来源：juejin.cn/post/7332865125640044556
