数学题 - 2. 约瑟夫环 - 《算法》

传说罗马人占领了乔塔帕特，41 个犹太人被围堵在一个山洞里。他们拒绝被俘虏，而决定集体自杀，大家决定了一个自杀方案，41 个人围成一个圈，由第 1 个人开始顺时针报数，每报数为 3 的人立刻自杀，然后再由下一个人重新从 1 开始报数，依旧是每报数为 3 的人立刻自杀，依次循环下去。其中两位犹太人并不想自杀，是数学家约瑟夫和他的朋友，他们发现了自杀方案的规律，选了两个特定的位置，最后只剩下他们两人，而活了下来。那么这两个位置分别是什么？

这个问题转化成要解决的通用问题：即 n 个人围成一个圈，这 n 个人的编号从 0——(n-1)，第一个人（编号为 0 的人）从 1 开始报数，报数为 m 的人离开，再从下一个开始从 1 开始报数，报数为 m 的人离开，依次循环下去，直到剩下最后一个人（也可以剩最后两个，少循环一次就是了），那么，把最后一个人的编号打印出来。

方法一：数组解决

function countOff(num,m){
  let players=[];
  for(let i=1;i<=num;i++){
    players.push(i);
  }
  let flag=0;
  while(players.length>1){// 剩下一人，结束条件
    let outPlayerNum=0,len=players.length;
    for(let i=0;i<len;i++){
      flag++;
      if(flag===m){
        flag=0;
        console.log("出局："+players[i-outPlayerNum]);
        players.splice(i-outPlayerNum,1);
        outPlayerNum++;
      }
    }
  }
  // return players[0];
  console.log("剩下："+players[0]);
}
// console.log("剩下："+find(100,5))
countOff(100,5)

方法二：循环队列实现
队列数据结构是遵循先进先出（也可以说成先来先服务）原则的一组有序的项。队列的尾部添加新元素，并从顶部（头部）移除元素。最新添加的元素必须排在队列的末尾。

function MyCircularQueue() {
  var items = [];
  //向队列插入元素
  this.enQueue = function (value) {
    return items.push(value);
  }
  //删除元素
  this.deQueue = function () {
    return items.shift();
  }
  //查看队列长度
  this.size = function () {
    return items.length;
  }
}
function countOff(m, n) {
  var queue = new MyCircularQueue();
  //将名单存入队列
  for (var i = 1; i <= m; i++) {
    queue.enQueue(i);
  }
  var loser = '';
  while (queue.size() > 1) {
    for (var i = 0; i < n - 1; i++) {
      queue.enQueue(queue.deQueue());
    }
    loser = queue.deQueue();
    console.log('被淘汰的人为：' + loser);
  }
  // return queue.deQueue();
  console.log('获胜者：' + queue.deQueue());
}
// console.log('获胜者：' + countOff(100, 5));
countOff(100, 5)

方法三：循环链表实现
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称为指针或链接）组成。双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向下一个元素。循环链表可以像链接一样只是单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针，不是引用 null，而是指向第一个元素。

方法四：递归

function countOff(N, M) {
  if (N < 1 || M < 1) {
    return;
  }
  let source=[];
  for(let i=1;i<=N;i++){
    source.push(i);
  }
  // const source = Array(...Array(N)).map((_, i) => i + 1);
  let index = 0;
  while (source.length>1) {// 剩下一人，结束条件
    index = (index + M - 1) % source.length;
    console.log('出局：'+source[index]);
    source.splice(index, 1);
  }
  console.log('剩下：'+source[0])
}
countOff(100,5)