关于约瑟夫问题自己理解过程

约瑟夫环问题

参考 https://blog.csdn.net/u011500062/article/details/72855826

一开始我并没有完全理解这位博主的意思, 我还纳闷这公式是咋来的, 知道最后, 有一句理解这个递推式的核心在于关注胜利者的下标位置是怎么变的, 真是的一语惊醒梦中人

这里说一下我自己的理解, 一开始我其实是完全懵逼的状态, 看了WiKi上的说明, WiKi上是使用数学上的数学归纳法来推到出来的, 其实还是比较懵逼的

我们按照那位博主所说, 只关注那位幸存者, 这样问题一下就变得非常的简单, 我们假设一共有11个人, 每第3个人出局

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

我们假设f(N, M) = 最终幸存者的位置

这样f(11, 3)所表达的意思就是说, 11个人每3个人出局, 最终幸存者的位置

过程

1 2 3 4 5 6 7 8 9 10 11

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 6 3, 4, 5, 6, 7, 8, 9, 10, 0, 1 3 6, 7, 8, 9, 10, 0, 1, 3, 4 0 9, 10, 0, 1, 3, 4, 6, 7 6 1, 3, 4, 6, 7, 9, 10 3 6, 7, 9, 10, 1, 3 0 10, 1, 3, 6, 7 3 6, 7, 10, 1 0 1, 6, 7 1 1, 6 1 6 0

通过这种方式, 每次让出局的那个人的后面那个人出局, 可以让每次都是新的题目, 状态和上下都没有关系了

比如第一次, 是11个人, 每3个出局
到第二次, 就是10个人, 每3个出局, 单独来看的话, 结果是跟上面的没有关系的
不清楚有没有表达清楚
比如, 就拿第二次来说, 我继续从0开始写, 就是0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 这样的话, 状态是和上一次有关系的, 因为再下一次出局的人是5, 而这个5排在第4个位置(从0开始数), 那我写成上面那样的话, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 这样话, 我就相当与重新开始这样

这样, 每次出局一人, 我们就可以理解成每次人数减去1, 幸存者往前移动M个位置

f(N-1, M) = f(N, M) - M

这样公式大体就出来了, 然后, 我们需要再考虑下f(N, M) - M是负数的情况
于是公式就变成了这样
f(N-1, M) = (f(N, M) - M) % (N-1)

然后, 我们用逆向思维, 倒过来
f(N, M) = (f(N-1, M) + M) % N

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <iostream> using namespace std; int main() { // f(1, M) = 0 int r = 0, n = 11, m = 3; for (int i = 2; i <= n; ++i) { r = (r + m) % i; } cout << r << endl; return 0; }