黑马程序员技术交流社区

标题: 【上海校区】算法题（三十）：约瑟夫环问题 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:19
标题: 【上海校区】算法题（三十）：约瑟夫环问题
问题描述
约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。

给定两个int n和m，代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。

测试样例

输入：5 3
返回：4

分析
有两种方法可解这道题，一种是直接模拟该过程，找到最后一个数；另一种是利用数学归纳法来求解。

数学归纳法过程：

把n个人的编号改为0~n-1，然后对删除的过程进行分析。

第一个删除的数字是(m-1)%n，记为k，则剩余的编号为(0,1,...,k-1,k+1,...,n-1)，下次开始删除时，顺序为(k+1,...,n-1,0,1,...k-1)。

用表示从0~n-1开始删除后的最终结果。

用表示从(k+1,...,n-1,0,1,...k-1)开始删除的最终结果。

则。

把从(k+1,...,n-1,0,1,...k-1)转换为(0~n-2)的形式

k+1  0

k+2  1

...

k-1  n-2

转换函数为



假设我们知道(n-1)个人报数的问题的解x，那么根据上式把x变回去刚好就是n个人情况的解。用逆函数来变回去



如何知道(n-1)个人报数的解呢？需要知道(n-2)时的情况，这样一直倒推到1。

所以







令f表示i个人玩报m退出最后的胜利者的编号，最后的结果自然是f[n]。

f[1]=0

f=(f[i-1]+m)%i

最终输出 f[n]+1（编号从1开始）

上述过程的抽象理解方式为给定数n,m后，最终结果是固定的，只是在每次删除时，编号不一样，而我们要找到其在初始时的编号。那么就需要用逆函数来计算。先从最终结果逆运算到上一结果，同志逆运算到上上一个，一直逆运算到最后，即可得到在结果在初始时的编号。

public class YSFRound {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int n = 9;
                int m = 5;
                fun(n, m);
        }
        //数学归纳
        public static void fun(int n, int m){
                if(n<0 || m<0){
                        System.out.println(-1);
                        return;
                }
                int s=0;
                for(int i=2; i<=n; i++){
                        s = (s+m)%i;
                }
                System.out.println(s+1);
        }
    //模拟方法
        public static void fun2(int n, int m){
                LinkedList<Integer> list = new LinkedList<>();
                for(int i=1; i<=n; i++){
                        list.add(i);
                }
                int idx=0;
                while(list.size()>1){
                        int del = (idx+m-1)%list.size();
                        list.remove(del);
                        idx = del%list.size();
                }
                System.out.println(list.get(0));
        }
       

}
输出：8
---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/84072792
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:47
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2