js约瑟夫环算法

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

以下是代码:
<!DOCTYPE HTML>

<html>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=utf-8″>
<title>无标题文档</title>
<script>
function Node(element){
this.element = element;
this.next = null;
}
function LList(){
this.head = new Node(‘head’);
this.head.next = this.head;
this.length = 0;
}
LList.prototype.find = function(item){
var currNode = this.head;
while( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
};
LList.prototype.findPrevious = function(item){
var currNode = this.head;
while( currNode!=null && currNode.next.element != item ){
currNode = currNode.next;
}
return currNode;
};
LList.prototype.insert = function(newElement , item){
var newNode = new Node(newElement);
var currNode = this.find(item);
newNode.next = currNode.next;
currNode.next = newNode;
this.length++;
};
LList.prototype.remove = function(item){
var prevNode = this.findPrevious(item);
var currNode = this.find(item);
prevNode.next = currNode.next;
this.length–;
};
LList.prototype.display = function(){
var currNode = this.head;
var result = [];
while( currNode.next != null && currNode.next.element != ‘head’ ){
result.push( currNode.next.element );
currNode = currNode.next;
}
return result;
};
function killGame(num , step){
var people = new LList();
people.insert(1,’head’);
for(var i=1;i<num;i++){
people.insert(i+1,i);
}
console.log( people.display() );
var iNow = 0;
var dir = ‘head’;
function whileFn(){
if( people.length < step ){
return;
}
iNow++;
dir = people.find(dir).next.element;
if(dir == ‘head’){
dir = people.find(dir).next.element;
}
if(iNow == step){
var removeDir = dir;
dir = people.findPrevious(dir).element;
people.remove(removeDir);
iNow = 0;
}
whileFn();
}
whileFn();
console.log(‘幸存的位置是:’ + people.display());
}
killGame( 100  , 5 );
</script>
</head>
<body>
</body>
</html>
原文链接:,转发请注明来源!

发表评论