经典面试题-约瑟夫环

男娘i 2022-04-11 05:59 53阅读 0赞

# 题目描述： #

0, 1, …, n - 1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

# 输入： #

每组数据一行,包含2个整数n和m，分别表示0 到 n - 1 的序列和指定删除的第m个数字。

# 输出： #

输出能保留到最后的那个数字。

# 样例输入： #

5 3

# 样例输出： #

# 思路分析： #

*  除了暴力破解其实还有一种方法就是找到n个数字和n-1个数字的之间的关系，利用动态规划的思想来解决
 *  1）对于n个数组成的序列，第一次被删除的数为：(m - 1) % n。  
    （2）假设第二轮删除时，初始数字为m % n。令k = m % n，则对于剩下的n - 1个数构成的约瑟夫环为：k, k + 1, k + 2, k +3, …..,k - 3, k - 2。做一个映射如下：

k ——> 0  
k+1 ——> 1  
k+2 ——> 2  
…  
…  
k-2 ——> n-2

也就是说，n - 1个数中的一个数k，对应n个数时的下标为0。因此，设n - 1个序列最终留到最后的数为x，利用映射关系逆推，可得出n个数时，留到最后的数为：(x + k) % n。则有：

(x + k) % n  
= (x + (m % n)) % n  
= (x % n + (m % n) % n) % n  
= (x % n + m % n) % n  
= (x + m) % n

（3）类似的，现在考虑第二个被删除的数：(m - 1) % (n - 1)。  
（4）假设第三轮的开始数字为p，那么这n - 2个数构成的约瑟夫环为p, p + 1, p + 2,…, p - 3, p - 2。同样得到如下映射：

p ——> 0  
p+1 ——> 1  
p+2 ——> 2  
…  
…  
p-2 ——> n-3

也就是说，n - 2个数中的一个数p，对应n - 1个数时的下标为0。设n - 2个序列最终留到最后的数为y，利用映射关系逆推，可得出n - 1个数时，留到最后的数为：(y + p) % (n - 1)，其中p等于m % (n - 1)。代入可得：(y + m) % (n - 1)。

由以上内容得知，要求得n个数的序列最后留下的值，可通过n - 1个数的解来求得。递推下去，当只有一个人时，最后一个数字是0。

# 综上所述，得到以下递推式： #

## f\[1\] = 0; f\[i\] = (f\[i -1\] + m) % i; ##

# 代码： #

//n是代表n个数字，m是第每个出队
        public static int getJosePhus(int n,int m){
            int all = 0;
            if(n < 1||m < 1){
                return -1;
            }
            for(int i = 2;i <= n;i++){
                all = (all + m) % n;
            }
            return all;
        }

## 参考：   [http://blog.csdn.net/wuzhekai1985/article/details/6628491][http_blog.csdn.net_wuzhekai1985_article_details_6628491] ##

[http_blog.csdn.net_wuzhekai1985_article_details_6628491]: http://blog.csdn.net/wuzhekai1985/article/details/6628491