前端面试 - 算法篇（约塞夫环）

在上一篇的评论中，有朋友提出了一个“循环杀人游戏”

就在我为之苦恼的时候，一位同事在我身旁经过，突然说了一句：“咦，这不是约塞夫问题吗？”

 

一、面试题

原题目不太明朗（一号到底杀不杀？）

于是把题目优化一下，更接近于原本的约塞夫问题

假设有100人，分别编号 1~100

从 1 号开始报数，报数到 3 号时，3 号就被淘汰，然后由下一人从 1 报数，以此类推

最后谁会活下来？

 

二、面向过程

最开始我按照自己的思路，模拟了整个过程

虽然能解决问题，但一旦遇到较大的数据量，查询的次数太多，性能太低

不过这种方法最容易理解

/**
 * 面向过程的约塞夫环解决办法
 * @param {array} peoples 参与游戏的数组
 * @param {number} kill 淘汰的报数数字
 * @return {object} 幸存者
 */

function killer(peoples, kill) {
  
  let flag = 0 // 初始化报数

  while(peoples.length > 1) { // 只剩下一个人时，循环结束

    let len = peoples.length // 剩余人数
    let out = 0 // 已淘汰的人数

    for (let i = 0; i < len; i++) {
      flag++ // 报数+1

      if (kill == flag) { // 当报数到指定数字，淘汰该玩家
        // 淘汰后剩余人数(数组)会发生变化，所以被淘汰玩家下标应为 i-out
        peoples.splice(i-out, 1)

        flag = 0 // 重置报数
        out++ // 淘汰人数+1
      }
    }
  }
  return peoples[0]
}

 

二、面向对象

在数据结构中，具有链式存储结构的线性表被称为链表

其特点是每个数据元素在存储本身的信息之外，还要存储其直接后继的信息

数据元素之间不要求在存储空间中连续

而当这些数据元素构成一个逻辑上的环，任意元素都有一个前驱和后继，这就构成了一个循环链表

 

在这个游戏中，可以将玩家抽象成一个对象，然后由玩家组成了一个环

根据循环链表的特性，每个玩家除了存储本身的信息（编号），还需要存储前后的编号

class player { // 创建玩家
  constructor(n) {
    this.index = n; // 玩家编号
    this.before = {}; // 前一个玩家
    this.after = {}; // 后一个玩家
  }
}

 

然后分析整个环，除了构造函数之外，还应当具备淘汰玩家、开始游戏的功能

为了保证环的完整，需要一个起点和一个终点，这两个点在逻辑上是相邻的

在整个游戏过程中，我们只需要关心环的完整（起点、终点、玩家的前驱与后继）就可以了

/**
 * 面向对象的约塞夫环解决办法
 * @param {number} length 玩家总数
 * @param {number} kill 淘汰的报数数字
 * @return
 */
class cycle { // 创建循环链表
  constructor (length) {
    this.count = 0; // 玩家总数
    this.start = new player(1) // 链表起点
    this.end = new player(length) // 链表终点

    for(let i = 1; i <= length; i++) {
      // 创建玩家
      let player = new player(i)
      this.count++

      if (this.count <= 1) {
        // 只有一个玩家的时候，起点和终点为同一个玩家
        this.start = this.end = player
      } else {
        // 新创建的玩家一定位于链表终点之后
        this.end.after = player
        player.before = this.end
        // 而该玩家即为新的链表终点
        this.start.before = player
        player.after = this.start
        this.end = player
      }
    }
  }

  delete (player) {
    if (this.count <= 1) { // 错误校验
      this.start = this.end = null
      return
    } else {
      // 将前后的玩家关联起来
      player.before.after = player.after
      player.after.before = player.before
      // 如果处于终点或起点，则修改相关信息
      if (player == this.start) {
        this.start = player.after
      } else if(player == this.end) {
        this.end = player.before
      }
    }
    // 淘汰该玩家
    player = null
    this.count--
  }

  play (kill) {
    let flag = 0 // 初始化报数
    let k = this.start // 从起点开始游戏
    while (this.count > 1) { // 只剩一个玩家，循环结束
      flag++
      if (flag == kill) { // 报数到目标数字，淘汰玩家
        flag = 0
        this.delete(k)
      }
      // 无论淘汰与否，让下一个玩家报数
      k = k.after
    }
    return `幸存者：${k.index}`
  }
}

new cycle(100).play(3)

  

三、递归算法 

在吃透了整个游戏规则之后。。。

function joseph(sum, value, n) {
    if ( n==1 ) {
        return ( sum + value - 1) % sum;
    } else {
        return ( joseph( sum - 1, value, n - 1) + value ) % sum;
    }
}

console.log("剩下的人号数为：" + (joseph(100, 3, 100) + 1))

emmmmmmmmmm

难怪《美丽心里》里开头就说，是数学家改变了世界

  

四、问题拓展

1. 如何用 js 快速创建一个 1~100 的数组？

2. 如果报数到 2 就淘汰，最后剩下谁？