原创 用javascript循环单链表演练犹太约瑟夫/猴子选大王问题 WalkthroughforJewishJosephus/MonkeysProblem viaCircularSingleLinkedList 一群孩儿的游戏 一群孩儿共M个人，每人都有编号，编号是1，2，3...
用 javascript 循环单链表演练犹太约瑟夫/猴子选大王问题
Walkthrough for Jewish Josephus/Monkeys Problem
via Circular Single Linked List
一群孩儿的游戏
一群孩儿共M个人，每人都有编号，编号是1，2，3 ...M。按照1--M
的顺序依次围坐一圈。从1号开始数，数到第N个，这个孩子就要离开此圈。然后，从下一个孩子开始，再数到第N个，这个孩子就要离开此圈。
这样依次下来，
1. 直到圈中只剩下最后两个人，这两个人的编号是多少？(犹太约瑟夫问题Jewish Josephus Problem )
2. 直到圈中只剩下最后一个人，这一个人的编号是多少？(猴子选大王问题 The monkeys elect their king)
其实，为选择规则所输入的数字，为最后留下的成员个数.
演示见：
http://runjs.cn/detail/mevhmdap
http://sandbox.runjs.cn/show/mevhmdap
参考：
http://www.pudn.com/downloads409/sourcecode/book/detail1743390.html
http://blog.sina.com.cn/s/blog_7027c3cf0100w9nn.html
1. [图片] Monkey_Josephus_1.png
2. [图片] monkey_josephus_2.png
3. [文件] Josephus_Monkey.html ~ 7KB 下载(2)
<!protrammer: Xu Tongchun, June 30, 2016
猴子选大王
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（M个）按照1--M
的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，
这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
Jewish Josephus Problem
传说在公元1世纪的犹太战争中，犹太约瑟夫是公元一世纪著名的历史学家。在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，
39个犹太人决定宁愿死也不要被敌人俘虏，于是决定了一个流传千古的自杀方式，
41 (M)个人排成一个圆圈，由第1个人开始报数，每报 到第3(N)人该人就必须自杀，
然后再由下一个人重新报数，直到所有人都自杀身亡为止。
然而约瑟夫和他的朋友并不想遵从这个约定，约瑟夫要他的朋友先假装遵从，
他将朋友与自己安排在第_个和第_个位置，于是逃过了这场死亡游戏,
你知道安排在了第几个嘛？
>
<html>
<head>
<title>Cercular Linked List</title>
<meta charset="utf-8">
<script type="text/javascript">
function Node(data){ // 创建一个结点的构造方法
this.data = data;
this.next = null;
}
function CList(data) { //循环链表的构造方法
this.head = new Node(data); //数据成员
this.head.next = this.head; //数据成员
this.count=1; //数据成员
this.find = find; //成员方法
this.stepForward = stepForward; //成员方法
this.insertLast = insertLast;//成员方法
this.traversal = traversal; //成员方法
this.findPrevious = findPrevious; //成员方法
this.remove = remove; //成员方法
}
/*循环链表 Clist 的成员方法 find(data)的定义.
* 查询数据为 data 的结点。
* 若找到，返回该结点的引用。 若没有找到， 返回 空
*/
function find(data) {
var p = this.head;
while(p.data!=data && p.next != this.head)
p=p.next;
if (p.data==data)
return p;
else
return null;
}
/*循环链表 Clist 的成员方法 stepForward(p,n) 的定义.
* 从 p 结点开始报数，报到第 n 个结点，返回第 n 个结点
*/
function stepForward(p,n) {
var q = p;
for (var i=1; i<n; i++)
q = q.next;
return q;
}
/*循环链表 Clist 的成员方法 insertLast(data) 的定义.
* 将 数据项为 data 的结点，插入循环链表的尾部。
*/
function insertLast(data) {
var newNode = new Node(data);
var p = this.head;
while(p.next!=this.head)
p=p.next;
newNode.next=this.head;
p.next=newNode;
this.count++;
}
/*循环链表 Clist 的成员方法 : 遍历 traversal() 的定义.
*/
function traversal() {
var p = this.head;
var s = "Total Number: " + this.count + "<br>";
do{
s += p.data + " ";
p=p.next;
} while (p != this.head);
return s;
}
/*循环链表 Clist 的成员方法 findPrevious(p) 的定义.
* 返回 p 结点的 前继(前一个)结点。
*/
function findPrevious(p) {
var q = this.head;
while (q.next != p && q.next != this.head)
q=q.next;
return q;
}
/*循环链表 Clist 的成员方法 remove(data) 的定义.
* 删除 数据项为 data 的结点、 返回被删除的结点。
* 若结点不存在，则返回 空。
*/
function remove(data) {
var p = this.find(data);
if (p) {
var q= this.findPrevious(p);
if ( p == this.head)
this.head=p.next;
q.next=q.next.next;
this.count--;
return p;
} else
return null;
}
function solution(){ // 用按钮触发的方法
/* 起始有 M 个人. 由第 1 个人开始报数，每报到第 N 个人,
* 该人就从循环链表被清除
* 若是“猴子选大王”问题，g 取 1.
* 若是"犹太约瑟夫"问题，g 取 2.
*/
var M= document.forms[0].elements[0].value;
var N= document.forms[0].elements[1].value;
var g= document.forms[0].elements[2].value;
/* 用户输入的数据 M 和 N 数必须是一个大于 1 的整数
* 检查 M 和 N 的 合法性 guard for validity
*/
if( isNaN(M) || M%1 != 0 || M <= 1) {
alert("初始总数必须是一个大于 1 的整数");
return ;
}
if( isNaN(N) || N%1!=0 || N <= 1) {
alert("数到数 N 必须是一个大于 1 的整数");
return ;
}
var s = ""; // 记录演练过程的字符串
if (g==1)
s+="演练规则：猴子选大王 The rule adopted for \"Monkeys elect their king\".";
else
s+="演练规则：犹太约瑟夫 The rule adopted for \"Jewish Josephus Problem \".";
s+="<br>演练过程如下(结果见最后一行) Thewalkthrough is reported as follows. The final result is seen at the last line:<br>";
var list = new CList(1);
for (var i = 2; i <= M; i++)
list.insertLast(i);
s+=list.traversal() + "<br>";
var cur=list.head;
/* 若是“猴子选大王”问题，g 取 1.
* 若是"犹太约瑟夫"问题，g 取 2.
*/
while(list.count>g ){
var p_deleted = list.remove((list.stepForward(cur,N)).data);
cur=p_deleted.next;
s+=p_deleted.data + " is deleted. ";
s+=list.traversal() + "<br>";
// 将 s 显示于容器 <div id="display"></div> 之中
document.getElementById("display").innerHTML=s;
}
}
</script>
<style>
.inner{
width:500px;
}
.out{
width:100%;
border:solid #0F0;
margin-bottom:5px;
}
td{
height:40px;
width=250px;
border:solid #FF0;
}
</style>
</head>
<body>
<table class="out" width=100%><tr><td>
<form onSubmit="solution();return false" name='example'>
<table class="inner"><caption>用循环单链表演练犹太约瑟夫/猴子选大王问题<br>Walkthrough for Jewish Josephus/Monkeys Problem <br>via Circular Single Linked List</caption>
<tr><td>
初始总数 M<br>initial numbber M :</td><td> <input type="text" name="initial_number" >
</td></tr><tr><td>
数到第 N 个<br>counting to N each time:</td><td><input type="text" name="step_width" ></td>
</tr><tr><td>选择规则 The rule adopted for</td><td>
<input name="text" type="text" /></td></tr>
<tr><td><input type="Submit" value="演练 Walkthroug"></td></tr>
</table>
</form>
</td><td>
<div>选择规则说明：<br>
输入的数字，为最后留下的成员个数.<br>
输入 1 为选择 "猴子选大王 Monkeys elect their king"<br>
输入 2 为选择 "犹太约索夫 Jewish Josephus" </div>
</td></tr></table>
<div id="display"></div>
</body>
</html>