约瑟夫环

2016-01-11

传说 41 个犹太人被罗马人围堵在一个山洞里，他们拒绝被俘虏，决定集体自杀，大家商量了一个自杀方案，41 个人围成一个圈，由第 1 个人开始顺时针报数，每报数为 3 的人立刻自杀，然后再由下一个人重新从 1 开始报数，依旧是每报数为 3 的人立刻自杀，依次循环下去，直到最终只剩下一个人。其中数学家约瑟夫和他的朋友不想死，他们发现了自杀方案的规律，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

  • 模拟游戏法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function josephus(n, step) {
  // 创建一个数组表示环中的人
  let people = Array.from({ length: n }, (_, index) => index + 1)
  let index = 0

  while (people.length > 1) {
    // 计算下一个要移除的位置
    index = (index + step - 1) % people.length
    // 移除当前位置的人
    people.splice(index, 1)
  }

  // 返回最后剩下的人的标识号
  return people[0]
}

// 示例：在一个有 41 个人的环中，每次数 3 个人，找到最后剩下的人
josephus( 41 , 3) // 31
  • 规模扩散

从小规模问题出发，逐步递推到大规模问题。这种解法的核心思想是利用之前计算的结果来构建更大规模问题的解。

1
2
3
4
5
6
7
8
9
function josephus(n, k) {
  let result = 1 // 当只有一个人时，该人即为最后剩下的人

  for (let i = 2; i <= n; i++) {
    result = (result + k - 1) % i + 1
  }

  return result
}
  • 数学递归关系法
，其中， 表示在 个人，每次数 步的约瑟夫问题的解。 
1
2
3
4
5
6
7
function josephusMath(n, k) {
  if (n === 1) {
    return 1 // 当只有一个人时，该人即为最后剩下的人
  } else {
    return (josephusMath(n - 1, k) + k - 1) % n + 1
  }
}