约瑟夫环算法

什么是约瑟夫环呢？
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

image.png

例如：耶稣有13个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：13人围坐一圈，从第一个开始报号：1，2，3，1，2，3…。凡是报到“3”就退出圈子，最后留在圈子内的人就是出卖耶稣的叛徒。
思路：

首先假设，当数字为1的时候则表示活着的人，0为死了，这样我们就可以用数组来表示；
要考虑的几个问题，要形成一个环，就是说报数到第十三人的时候，从头开始报数；
报数为3的时候，那个人退出游戏，这里假设死了，数值为0；
还有一个问题，就是当报数到第四个人的时候，因为第三个人‘死了’，所以第四个人要从1开始报数；
5.当最后只剩下一个人的时候，则结束。

<script>
    var arr = [1,1,1,1,1,1,1,1,1,1,1,1,1];
    var count = 0;
    var num = 0;
    for(var i=0;i<arr.length;i++){
        // 判断活着
        if(arr[i]==1){
            // 开始计数
            count++;
            // 当报数到第四个的时候，从第一个开始报数
            if(count==4){
                count = 1;
            }
            // 当报数报到第三个人的时候，第三个人就死了
            if(count == 3){
                arr[i]=0;
                num++;
                // 当计数到最后的时候，游戏结束
                if(num == arr.length-1){
                    break;
                }
            }
        }
        // 当数到最后一个人的时候，从第一个人重头数，如果i=0的时候，i++就变成了2,所以i要为0
        if(i==arr.length-1){
            i = -1;
        }
    }
    console.log(arr);
</script>

结果：

1.png

过了两年，学习了数据结构，用队列解决这种问题再简单不过，特此补上

// 思路： 定义一个队列，队列先进先出，故先进来的数字先出去，再定义个index用来记录当前元素在队列中的位置，位置是3的倍数，则删除
  function isPt(arr) {
    let queue = [];
    let index = 0;
    for (let i = 0; i < arr.length; i++) {
      queue.push(arr[i]);
    }
    while (queue.length !== 1) {
      let item = queue.shift();  // 将环中数据一一删除
      index += 1;
      if (index % 3 !== 0) { // 不是3的倍数，再从环尾加入
        queue.push(item);
      }
    }
    return queue[0];
  }
  // 测试
  let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];
  isPt(arr);

约瑟夫环算法

推荐阅读更多精彩内容