約瑟夫斯環(huán)問(wèn)題

大體思路是使用循環(huán)鏈表結(jié)合一個(gè)帶模的計(jì)數(shù)器,計(jì)數(shù)器遞增的同時(shí)鏈表向前遍歷,計(jì)數(shù)器抵達(dá)指定次數(shù)時(shí)將鏈表當(dāng)前節(jié)點(diǎn)從環(huán)中刪除,如此往復(fù)直至最終剩余規(guī)定人數(shù)。

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.');
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 1 序 2016年6月25日夜,帝都,天下著大雨,拖著行李箱和同學(xué)在校門口照了最后一張合照,搬離寢室打車去了提前租...
    RichardJieChen閱讀 5,372評(píng)論 0 12
  • 9.3.3 快速排序 ??快速排序?qū)⒃瓟?shù)組劃分為兩個(gè)子數(shù)組,第一個(gè)子數(shù)組中元素小于等于某個(gè)邊界值,第二個(gè)子數(shù)組中的...
    RichardJieChen閱讀 1,949評(píng)論 0 3
  • 【聲明】歡迎轉(zhuǎn)載,但請(qǐng)保留文章原始出處→_→文章來(lái)源:http://www.itdecent.cn/p/08d08...
    夢(mèng)工廠閱讀 3,847評(píng)論 3 31
  • 從三月份找實(shí)習(xí)到現(xiàn)在,面了一些公司,掛了不少,但最終還是拿到小米、百度、阿里、京東、新浪、CVTE、樂(lè)視家的研發(fā)崗...
    時(shí)芥藍(lán)閱讀 42,787評(píng)論 11 349
  • 不覺(jué)冬歸與春到,但知無(wú)事日偏長(zhǎng)。一聲春雷響,萬(wàn)物始新生。立春剛過(guò),驚蟄就來(lái)了,意味著冬天已經(jīng)結(jié)束,伸個(gè)懶腰,新的歷...
    芳芳_4a89閱讀 520評(píng)論 0 2

友情鏈接更多精彩內(nèi)容