约瑟夫环

介绍

约瑟夫环（Josephus Problem）是一个理论计算机科学中的经典问题，也是一个著名的数学游戏问题。故事背景多种多样，但基本情节大致如下：有一群人围成一个圈，从某个人开始报数，每次数到特定数值（比如说是m）的人会被排除出圈，然后从下一个人继续开始报数，直到只剩下最后一个人为止，这个人就是游戏的胜利者。

解决约瑟夫环问题可以用递归、迭代或者数学公式等多种方法。

题目：

孩子们的游戏

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    private int function(int n, int m) {
        if (n == 1) 
            return 0;
        //递归
        int x = function(n - 1, m);
        //返回最后删除的那个元素
        return (m + x) % n; 
    }
    public int LastRemaining_Solution(int n, int m) {
        //没有小朋友的情况
        if(n == 0 || m == 0)
            return -1;
        return function(n, m);
    }
}

优点：简洁

缺点：会出现栈溢出

递归法解析：

LCR 187. 破冰游戏 - 力扣（LeetCode）

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        //没有小朋友的情况
        if(n == 0 || m == 0)
            return -1;
        int x = 0;
        //从小到大，更新x
        for(int i = 2; i <= n; i++)
            x = (m + x) % i;
        return x;
    }
}

优点：效率高

缺点：有难度

迭代法解析：

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