前端面试 - 算法篇(约塞夫环)
程序员文章站
2022-07-02 13:55:08
在上一篇《前端面试 - 算法篇(二分法)》的评论中,有朋友提出了一个“循环杀人游戏” 就在我为之苦恼的时候,一位同事在我身旁经过,突然说了一句:“咦,这不是约塞夫问题吗?” 一、面试题 原题目不太明朗(一号到底杀不杀?) 于是把题目优化一下,更接近于原本的约塞夫问题 假设有100人,分别编号 1~1 ......
在上一篇的评论中,有朋友提出了一个“循环杀人游戏”
就在我为之苦恼的时候,一位同事在我身旁经过,突然说了一句:“咦,这不是约塞夫问题吗?”
一、面试题
原题目不太明朗(一号到底杀不杀?)
于是把题目优化一下,更接近于原本的约塞夫问题
假设有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 就淘汰,最后剩下谁?