约瑟夫环问题 JS

create by db on 2021-7-8 15:53:37
Recently revised in 2021-7-8 19:51:30

本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！

闲时要有吃紧的心思，忙时要有悠闲的趣味

题目描述

返回目录

问题来历

传说罗马人占领了乔塔帕特，41 个犹太人被围堵在一个山洞里。他们拒绝被俘虏，而决定集体自杀，大家决定了一个自杀方案，41 个人围成一个圈，由第 1 个人开始顺时针报数，每报数为 3 的人立刻自杀，然后再由下一个人重新从 1 开始报数，依旧是每报数为 3 的人立刻自杀，依次循环下去。其中两位犹太人并不想自杀，是数学家约瑟夫和他的朋友，他们发现了自杀方案的规律，选了两个特定的位置，最后只剩下他们两人，而活了下来。那么这两个位置分别是什么？

问题描述

这个问题转化成要解决的通用问题：即 n 个人围成一个圈，这 n 个人的编号从 0——(n-1)，第一个人（编号为 0 的人）从 1 开始报数，报数为 m 的人离开，再从下一个开始从 1 开始报数，报数为 m 的人离开，依次循环下去，直到剩下最后一个人（也可以剩最后两个，少循环一次就是了），那么，把最后一个人的编号打印出来。

思路分析

思路一：循环标记

用一个数组来存储 n 个人在圈内的状态，全部标识为 1，即长度为 n 的数组所有元素都为 1 ，用一个报数器来记录报数了几次，只有被标识为 1 的人才能够报数，当报数器的值与 m 相等时，就让这个人离开，则标识为 0，并且让记录出圈人数的变量加 1，然后将报数器清零，当纪录变量等于 n-1 时，游戏结束。

思路二：递归标记

过程同上，不过我们用递归取代第一层循环。

思路三：动态规划

所谓动态规划就是：找关系。本题基本逻辑是这样的：n 个人出局一个时，总人数就变成了 n-1 个人，此时要处理的问题实际上就是 n-1 个人的问题，以此类推下去，要处理的就是 n = 2 的问题，因为当 n = 1 时，游戏就结束了。那么用一个方程来表示 n = 2 的解决过程：f(2,m) 很容易看到的规律是：m 是双数留下的就是 0，m 是单数留下的就是 1，用 m%2 来表示结果（此为递归算法的基本条件）。然后要找到 f(3,m) 和 f(2,m) 的对应关系，更精确点来说是 f(n,m) 和 f(n-1,m)
步骤为：先找基准条件，再通过一个简单的例子来找 f(n,m) 和 f(n-1,m) 的对应关系。

首先举一些简单的例子，找下规律：

这是要处理的问题：n = 5，m = 2

0 1 2 3 4 从第 0 位开始报数，第 1 位报数为 2
0 2 3 4 离开第一个人

2 3 4 0 (*) 上面的数字可以写成这样，因为从第 2 位开始报数
0 1 2 3 (**) 这是 n = 4， m = 2，要处理的问题，接下来就处理这个问题
0 2 3 离开第二个人

比较(*)式和(**)式，你可以找到规律：((**)+2)%5 则转化为(*)式了

2 3 0 (*) 上面的数字可以写成这样，因为从第 2 位开始报数
0 1 2 (**) 这是 n = 3，m = 2，要处理的问题，接下来就处理这个问题
0 2 离开第三个人

比较(*)式和(**)式，你可以找到规律：((**)+2)%4 则转化为(*)式了

2 0 (*) 上面的数字可以写成这样，因为从第 2 位开始报数
0 1 (**) 这是 n = 2，m=2，要处理的问 题，我们已经知道答案了，即 2%2 = 0

比较(*)式和(**)式，你可以找到规律：((**)+2)%3 则转化为(*)式了

0 离开第四个人， 游戏结束，那么要往上层回溯了

上面的公式可以让(**)式等价于(*)式，即在(**)式处理问题，得到的结果，通过这个公式就能得出(*)式的结果
复制代码

因此我们可以得出对应关系的公式：f(n,m) = (f(n-1,m)+m)%n

即当我们得到了 f(n-1,m) 的解答时，f(n,m) 的解答也就出来了

动态规划（递归）的思路是从上往下分解，再一层层往上回溯的。当 n = 2，m = 2 时，我们得到的解是 0，将这个 0 套入公式，往上回溯一层，所以当 n = 3，m = 2 时，我们得到的解是 (0+2)%3 = 2，将这个 2 套入公式，往上回溯一层，所以当 n = 4，m = 2 时，我们得到的解是 (2+2)%4 = 0，将这个 0 套入公式，往上回溯一层，所以当 n = 5，m = 2 时，我们得到的解是 (0+2)%5 = 2，因此我们解决了 f(5, 2) 的问题。

AC 代码

题解一：循环标记

/**
 * @param {number} n 人数
 * @param {number} m 出圈报数
 * @return {number}
 */
function josephRing(n, m) {
  //当参数不满足条件时，这个游戏无法进行
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }

  let arr = new Array(n).fill(1) //长度为n的数组，位置从0——n-1，就代表了 n 个人的编号，并将数组所有元素设定为 1代表未出圈
  let count = 0 //纪录出圈人数
  let num = 0 //报数器

  //设定循环结束条件：当 count = n-1，即只剩下一个人的时候，游戏结束`
  while (count < n - 1) {
    for (let i = 0; i < arr.length; i++) {
      //第二层循环，循环数组
      if (arr[i] === 1) {
        //当这个位置的元素为 1 时，就执行接下来的代码
        num++ //每经过一个元素为 1 的位置时，就让报数器加 1
        if (num === m) {
          //当报数器等于 m 时，就执行接下来的代码
          arr[i] = 0 //让这个位置的元素为 0，表示这个位置已经出圈了
          count++ //纪录出圈人数的变量加 1
          num = 0 //将报数器清零
        }
        //当 m = 1 时，只有当 count = n 才会退出第二层循环（for循环），此时数组内的所有元素都变为了 0，为了避免这个问题，必须要有这个 if 判断句，达到特定条件时强制退出
        //其实当 m = 1时，结果就是 n，也可以将 m = 1 作为特殊情况来处理，即写在 while 循环以外，如此 m = 1 时就不会进入循环
        if (count === n - 1) {
          break
        }
      }
    }
  }
  //找到数组中元素为 1 的位置，将这个位置输出
  let winner = arr.findIndex(item => item === 1) + 1
  console.log(`${winner} is the winner`)
}

//测试上面的代码，并且打印执行的时间，如此可以与其他解决方案的执行时间相比较
let start = new Date().getTime()
josephRing(10000, 3)
let end = new Date().getTime()
console.log('====' + (end - start) + '====')
复制代码

题解二：递归

/**
 * @param {number} n 人数
 * @param {number} m 出圈报数
 * @return {number}
 */
let count = 0 //纪录出圈人数
let num = 0 //报数器
function josephRing(n, m, arr) {
  //当参数不满足条件时，这个游戏无法进行
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }
  //初始调用，创建长度为n的数组，位置从0——n-1，就代表了 n 个人的编号，并将数组所有元素设定为 1代表未出圈
  if (!arr) {
    arr = new Array(n).fill(1) 
  }
  //设定递归结束条件：当 count = n-1，即只剩下一个人的时候，游戏结束，返回胜者
  if (count === n - 1) {
    let winner = arr.findIndex(item => item === 1) + 1
    console.log(`${winner} is the winner`)
    return
  }
  // 循环数组，出圈更改状态
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1) {
      //当这个位置的元素为 1 时，就执行接下来的代码
      num++ //每经过一个元素为 1 的位置时，就让报数器加 1
      if (num === m) {
        //当报数器等于 m 时，就执行接下来的代码
        arr[i] = 0 //让这个位置的元素为 0，表示这个位置已经出圈了
        count++ //纪录出圈人数的变量加 1
        num = 0 //将报数器清零
      }
    }
  }
  // 递归调用
  josephRing(n, m, arr);
}

//测试上面的代码，并且打印执行的时间，如此可以与其他解决方案的执行时间相比较
let start = new Date().getTime()
josephRing(10000, 3)
let end = new Date().getTime()
console.log('====' + (end - start) + '====')
复制代码

题解三：动态规划

/**
 * @param {number} n 人数
 * @param {number} m 出圈报数
 * @return {number[]}
 */
function josephRing(n, m) {
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }

  let r = 0
  for (let i = 2; i <= n; i++) {
    //会先计算 n = 2 时的结果，最终得到的 r 就是胜利者
    r = (r + m) % i
  }
  console.log(r + 1 + ' is the winner.')
}

//测试上面的代码，并且打印执行的时间，如此可以与其他解决方案的执行时间相比较
let start = new Date().getTime()
josephRing(10000, 3)
let end = new Date().getTime()
console.log('====' + (end - start) + '====')
复制代码