约瑟夫问题-学习笔记

约瑟夫问题简介

据说着名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫问题算法分析

明显只要找到剩余最后两个位置，就可以逃脱。因此该题就是求解自杀顺序。

解法1：循环链表

根据问题很容易联想到循环链表。它的时间复杂度也很容易分析：每查找3次要有一人自杀，一共41人，就要查找41次。时间复杂度O(m*n)。(刚开始学JavaScript，就用js来写代码了)

function NodeData(i) {this.data = i;this.next = null; }function createList(n) {var fnode = new NodeData(1);var beginNode = fnode;for (let i = n; i > 1; i--) {let node = new NodeData(i);node.next = fnode;fnode = node;}beginNode.next = fnode;return beginNode; }function josephus(nodeList, n, m) {var currentNode = new NodeData(0);currentNode.next = nodeList;var node = currentNode.next;var indexArray = [];while(indexArray.length < n-1) {for (let i = 1; i < m; i++) {node = node.next;currentNode = currentNode.next; }indexArray.push(node.data);currentNode.next = node.next;node.next = null;node = currentNode.next;}indexArray.push(node.data);return [node.data, indexArray]; } 复制代码

解法2：根据规律推到公式

当有5个人，找第三个时：n=5，m=3

0 1 2 3 4

第一轮删除index=3的人，剩4个人时顺序：

3 4 0 1

按照这个顺序继续往下删index=3的人，直到剩余一人。

此时看下n=4，m=3时，人的排序：

0 1 2 3

此时看下2和3行，他们都只有4个人，那此后要删除的人的顺序也就是index是完全相同，完全相互对应的。因此剩余的最后一个人也是相互对应的。再看下每组相互对应的数据之间的关系：

x -> (x+m) mod (n+1)

如：2->(（2+3）% (4+1) = 0 )。这下就可以得出：求解 m个人时最后一个被杀的人的结果同求解m-1个人时最后一个被杀的人的结果的关系是：

f(n) = (f(n-1) + m) mod n

因此，知道了n-1的结果就可以求n的结果了。用代码实现：

function josephus(n, m) {var lastResult = 0; // 1个人时for(let i = 2; i <= n; i++) {lastResult = (lastResult + m) % i; // 当i个人时}return lastResult; } 复制代码

注意：此种方式仅适用于index从0开始，且只能求解最后一个人。

时间复杂度O(n)，空间复杂度O(1)。

其余解法待补充。

转载于:https://juejin.im/post/5bd179056fb9a05d0e2ea78e

总结

以上是生活随笔为你收集整理的约瑟夫问题-学习笔记的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。