约瑟夫斯环问题

2016-11-06  本文已影响0人  假装会编程

大体思路是使用循环链表结合一个带模的计数器,计数器递增的同时链表向前遍历,计数器抵达指定次数时将链表当前节点从环中删除,如此往复直至最终剩余规定人数。

var Node = function(element){
  this.element = element;
  this.next = null;
};
var LinkedList = function(){
  this.head = new Node();
  this.head.next = this.head;
  this.findPrev = function(item){
    var prev, node = this.head;
    while(node.next!==this.head){
      prev = node;
      node = node.next;
      if(node===item)
        return prev;
    }
    return -1;
  };
  this.append = function(item){
    var node = this.head;
    while(node.next!==this.head){
      node = node.next;
    }
    item.next = node.next;
    node.next = item;
  };
  this.remove = function(item){
    var prev = this.findPrev(item);
    if(prev!==-1){
      prev.next = item.next;
      delete item;
      return true;
    }
    return false;
  }
  this.toString = function(){
    var result = 'head', node = this.head;
    while(node.next){
      node = node.next;
      result += (' > ' + node.element);
    }
    return result;
  }
}
var findSurvivor = function(){
  var i, l = new LinkedList();
  for(i=1;i<42;i++){
    l.append(new Node(i));
  }
  console.log('Once upon a time, there\'re 41 men trapped.');
  console.log('Some of them decided to kill themselves.');
  console.log('While two of them would rather not.');
  console.log('How do they survive?');
  var count = 0, left =41, node = l.head.next;
  while(left>2){
    var tmp = node;
    node = node.next;
    if(count===2){
      console.log(tmp.element + ' is going to kill himself.');
      l.remove(tmp);
      left--;
    }
    count = (count + 1) % 3;
    if(node===l.head)
      node = node.next;
  }
  console.log('In the end, ' + l.head.next.element + ' and ' + l.head.next.next.element + ' survived.');
}
上一篇 下一篇

猜你喜欢

热点阅读