约瑟夫环问题

本文主要是介绍约瑟夫环问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一个0, n-1的队列, 循环轮流报数, 报到m的退出, 再接着从0开始报数

普通的方式就是一直遍历, 索引到头了就还从0开始, 一直循环n * m次, 但是这种方式会超时

那么可以这样看, 每次到m的时候, 下一轮重新开始, 也就是一个新的数组, 从被删除的索引下一个开始为索引0

依次向后, 并且当做一个环, 前面的会向后接上

当出列到最后一个人的时候, 他的索引一定是0

那么可以向上推到在还有两个人的时候, 它的索引是多少, 有两个人的推出来了, 向上再推三个人的时候索引是多少, 一直推到当有n个人的时候, 索引是多少

那么0和1就不用考虑了, 就是0, 从2开始推, 由1个人的时候推2个人的时候

2个人的时候效果不是太直观, 就说从7个人推到8个人的时候, 设m = 3

当n = 7的时候, 索引是3, 如果恢复到n = 8的时候, 就是上一轮删除之前的, 现在把上一轮删除的C添加到末尾（因为上一轮的C删除后，索引从C的下一个开始了， 并且C的之前的由于循环接到上一轮的末尾）

先不看第一行， 第二行就是把C接上之后的模样， 那么怎么恢复它所在的索引

首先可以知道， 每一轮都是计数到m时, m之后的从索引0开始, 那么m之前的就移动到了末尾

所以先向右移动m个位置(+m), 把删除之后,移动之前的位置空出来, 也就是第三行

这时, 索引越界了, 当前的索引刚好到A之前， 需要取个模将超出索引的移动到该在的位置，因为已经+m了, 所以直接 % 当前行的数组长度即可, 恰好可以将后面移动后超出的数据(上一次删除的位置的前面的)放到正确的位置

这个时候, 就由 n = 7 得到了 n = 8时的索引

上面的结论可以得出从0推到1, 1推到2,… n - 1 推到 n

将前面的过程总结下来就是 f n = (f (n -1) + m ) % (n - 1), 注意是 % 当前行的长度

则有如下代码

const lastRemaining = (n, m) => {
// 最终的索引是0, 即n = 1时
  let ans = 0
  for (let i = 2; i <= n; i++) {
  // (上一次的结果 + m) % 当前行的长度
    ans = (ans + m) % i
  }
}

这篇关于约瑟夫环问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！