刘谦春晚魔术揭秘:约瑟夫环的数学魅力,JS实现下!

更新日期: 2024-02-21阅读: 494标签: 算法

今年春晚刘谦的魔术堪称惊艳全场,那么他这个魔术实现的原理是什么呢?今天,就让咱们使用 JS 是实现这个魔术。

约瑟夫环问题简介

约瑟夫环问题源自古罗马,由历史学家约瑟夫斯提出,而其数学模型则在19世纪被命名。问题设定如下:n个人围成一圈,从第一人开始报数,每报到第k个人,该人就会被淘汰。游戏继续进行,直到最后只剩下一个人。我们的目标是找出这个幸存者的编号。


用扑克牌解读约瑟夫环

情景一:最简单的情况

设想我们有两张牌,编号为1和2。我们先将1号放到底部,然后移除2号。结果,最初位于顶部的1号牌幸存下来。

情景二:牌数为2的n次幂

设想有8张牌,编号从1到8。在第一轮中,我们会移除所有偶数编号的牌(2、4、6、8),剩余1、3、5、7。这些剩下的牌按顺序放到底部,问题就变成了4张牌的情况。

重复这个过程,最终我们发现,如果牌数是2^n张,幸存的总是最初位于顶部的那张牌。

情景三:任意数量的牌

对于任意数量的牌(比如11张),我们可以将其表示为2^n+m(在这个例子中是8+3)。通过重复上述过程,我们会发现最终幸存的牌是最初位于顶部第m+1位的牌(在这个例子中是7号牌)


见证奇迹的时刻!

  1. 从4张牌开始,对折撕成8张排成ABCDABCD。
  2. 根据名字长度将顶部牌放到底部,位置变化不影响结果。譬如2次,最后变成CDABCDAB;譬如3次,最后换成DABCDABC。但无论怎么操作,第4张和第8张牌都是一样的。
  3. 将顶部3张牌随意插入中间,确保第1张和第8张牌相同。这一步非常重要!因为操作完之后必然出现第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步拿掉的那张牌!

下面是完整的 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}`);

通过上述代码,我们可以模拟刘谦春晚魔术的整个过程,并验证其背后的数学逻辑。

转自:程序员Sunday

链接: https://fly63.com/article/detial/12654

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!