2024春晚刘谦魔术与约瑟夫环问题

各位小伙伴们大家——过~年~好~~！[]~(￣▽￣)~*

昨晚播出了2024春节联欢晚会，本着在乡下无聊也是无聊不如看看今年春晚有没有什么乐子的心态从晚上20点到次日0点40共4个多小时的时间在人生中首次看完了一整场春晚直播

(((φ(◎ロ◎;)φ)))

刘谦的魔术节目经我和另外一位唯一也看了全场直播的小伙伴一致认为是全场最佳！春晚刚结束网上就有大佬给出了第二个魔术（拼扑克牌）的数学模拟，也有大佬发布了代码程序。今天博主在模拟了魔术过程之后，也分享一下程序代码。

顺便，借此回顾一下约瑟夫环问题。

一、拼扑克牌魔术编程揭秘

1.过程图解

2.Python代码

二、约瑟夫环问题

1.问题介绍

2.数组实现

思路模拟

代码实现

3.循环链表实现

4.递归实现

一、拼扑克牌魔术编程揭秘

1.过程图解

假设初始的4张完整的牌为 [7,8,9,10]：

2.Python代码

用Python语言是因为它对列表操作（切片、拼接等）特别方便：

import random# 初始卡片cards队列，4张牌，假设为 7，8，9，10
cards = [7, 8, 9, 10]# 一、把4张牌撕开成8张，放到原来4张牌后
cards += cards
# print(cards)# 二、名字有几个字，名字有几个字就从队头拿几张牌放到队尾
# 从队头取name_len个元素插入队尾
name_len = int(input('名字长度(2~7的整数)：'))  # 名字长度
for _ in range(name_len):cards.append(cards.pop(0))
# print(cards)# 三、拿起最上面三张，把这三张整体插进剩下卡片的中间任意位置
first_three = cards[:3]  # 队首3个元素，待插入 
other_cards = cards[3:]  # 剩下5个元素# 队首3个元素插入到剩下5个元素的位置是随机的
index = random.randint(1, 4)  # index 可取 1,2,3
cards = other_cards[:index] + first_three + other_cards[index:]
# print(cards)# 四、把第一张牌放到屁股下
key_card = cards.pop(0)# 五、按南北方人取牌,重复上述过程
south_north = int(input('南北方人(南方1,北方2,分不清3)：'))  # 南方人还是北方人
first_cards = cards[:south_north]
other_cards = cards[south_north:]# 插入的位置是随机的
index = random.randint(1, 7 - south_north - 1)
cards = other_cards[:index] + first_cards + other_cards[index:]
# print(cards)# 六、按性别取牌,并撒出去
gender = int(input('性别(男1,女2)：'))  # 性别
for _ in range(gender):cards.pop(0)
# print(cards)# 七、洗牌，“见证奇迹的时刻”
for _ in range(7):cards.append(cards.pop(0))
# print(cards)
# 此时若为女，队尾元素调整至倒数第3；若为男，倒数第2# 八、好运留下来，烦恼丢出去
while len(cards) > 1:# 好运留下来cards.append(cards.pop(0))# 烦恼丢出去cards.pop(0)# print(cards)print(f"assert cards[0] == key_card ? :{cards[0] == key_card}")

运行结果：

二、约瑟夫环问题

1.问题介绍

“约瑟夫环问题”也叫“丢手绢问题”。百度百科介绍了此问题的起源：

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

可以把分析约瑟夫环问题的过程总结成以下步骤：

总共有 n 个人围成一桌坐下，编号从 1 到 n，从编号为 1 的人开始报数。
报数也从 1 开始，报到 m 的人出局，从出局者的下一位在座成员开始继续从 1 开始报数。
重复这个过程求各成员的出局次序，或求最后一个在座的成员编号。

为了便于接下来的讨论，这里取约瑟夫环问题的一个具体的变式：

30个人在一条船上，船只超载，现需15人下船。于是人们排成一队，排队的位置即为他们的编号。人们循环报数，从1开始，数到9的人下船。如此循环，直到船上仅剩15人为止，问：都有哪些编号的人下船了？

2.数组实现

思路模拟

用数组这种数据结构来描述船上每个人之间的关系。

数组实现的方式非常简单，我们可以先手动进行以下模拟：

由此，便能得到出局的元素序列。将以上模拟过程编码就能得到解答程序。由于数组中每个元素是连续且位置固定的，当我们遍历约瑟夫环时，报数报到 m 的人要出局，此处的“出局”是逻辑删除，而不是物理删除（即只是把该号元素标记为“已出局”，而不是真的把这个元素从数组中删去）。

每次遍历约瑟夫环中元素时，通过判断该元素是否被标记为“已出局”来判断该元素是否需要进行报数，因为报数只在未出局的元素中进行。

需要特别注意的是，上述模拟中我们将第一个元素编号为1，而实际Java数组中第一个元素的下标为0。

代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Solution1 {/*** 数组解决约瑟夫问题* @param n 一共有 n 个人* @param m 报数到 m 就出局* @param peopleLeft 要求最终幸存的人数*/public static List<Integer> JosephusArray(int n, int m, int peopleLeft){// 存放出局元素序列List<Integer> out_items = new ArrayList<>();// 用于标记某位置的人是否还在船上，0表示未出局，1表示已出局// 共n个元素，但由于第一个元素的下标为0，而题干要求从1开始报数，为了和下标匹配，长度定义为n+1，下标为0的元素闲置int[] flag = new int[n + 1];// cnt：目前已出局的人数；i：某编号的人；k：当前报的数int cnt = 0, i = 0, k = 0;while (peopleLeft != n-cnt) {// 从第一个人依次进行报数i++;if (i > n) {i = 1;}if (flag[i] == 0) {  // 如果 i 位置的人未出局k++;  // 就报一个数if (k == m) {  // 如果报到要求出局的数 mflag[i] = 1;  // 标记为出局cnt++;  // 已出局人数+1out_items.add(i);k = 0;  // 清空k，下次重新从0开始报数}}}return out_items;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("数组实现约瑟夫环问题：");System.out.print("共有 n 人：");int n = scanner.nextInt();  // n 为总人数System.out.print("数到数字 m 时出局：");int m = scanner.nextInt();  // 数到 m 时出局System.out.print("要留下多少人：");int peopleLeft = scanner.nextInt();  // 要留下的人数System.out.println(JosephusArray(n, m, peopleLeft));}
}

运行结果：

3.循环链表实现

思路模拟

用循环链表的数据结构来描述船上每个人之间的关系，示意图如下：

遍历约瑟夫环（此时是一个循环链表），每要出局一个元素，就通过更改元素之间next指向的方式将该元素真正从循环链表中删去（物理删除），并记录到出局元素序列。多轮删除后，循环链表中留下的元素即幸存者。

代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;class Node {int data;Node next;Node(int data){this.data = data;}
}public class Solution2 {/*** 循环链表解决约瑟夫问题* @param n 一共有 n 个人* @param m 报数到 m 就出局* @param peopleLeft 要求最终幸存的人数*/static List<Integer> JosephusCircleList(int n, int m, int peopleLeft) {List<Integer> out_items = new ArrayList<>();    // 存放出局元素序列// 1-创建循环链表Node head = new Node(1);    // 节点编号从1开始head.next = head;Node pre = head;for (int i = 2; i <= n; i++) {Node node = new Node(i);pre.next = node;node.next = head;pre = pre.next;}int cnt = 0;    // 已经出局了的人数Node cur = head;// 2-遍历约瑟夫环while(peopleLeft != n-cnt) {    // 当没有达到要求剩下的人数时for (int k = 1; k < m; k++) {pre = cur;cur = cur.next;}out_items.add(cur.data);cnt++;pre.next = cur.next;cur = cur.next;}return out_items;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("循环链表实现约瑟夫环问题：");System.out.print("共有 n 人：");int n = scanner.nextInt();  // n 为总人数System.out.print("数到数字 m 时出局：");int m = scanner.nextInt();  // 数到 m 时出局System.out.print("要留下多少人：");int peopleLeft = scanner.nextInt();  // 要留下的人数System.out.println(JosephusCircleList(n,m,peopleLeft));}
}

运行结果：