约瑟夫斯环问题

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

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.');
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,172评论 0 12
  • 9.3.3 快速排序   快速排序将原数组划分为两个子数组,第一个子数组中元素小于等于某个边界值,第二个子数组中的...
    RichardJieChen阅读 1,870评论 0 3
  • 【声明】欢迎转载,但请保留文章原始出处→_→文章来源:http://www.jianshu.com/p/08d08...
    梦工厂阅读 3,788评论 3 31
  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,372评论 11 349
  • 不觉冬归与春到,但知无事日偏长。一声春雷响,万物始新生。立春刚过,惊蛰就来了,意味着冬天已经结束,伸个懒腰,新的历...
    芳芳_4a89阅读 481评论 0 2