【上海校区】算法题(三十):约瑟夫环问题

python 未结 0 191
就会给房东
就会给房东 2021-07-22 15:06
悬赏:47
问题描述
约瑟夫问题是一个非常著名的趣题,即由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
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复