约瑟夫环问题——一般解+数学模型递归解

Description

约瑟夫问题是个有名的问题：N个人围成一圈，每个人都有自己对应的号数（号数从1到N），从1号开始报数（报数从数字1开始,轮到下一个人数字递增），当有人报数的数字为M将会被杀掉，下一个人接着从数字1开始报数，循环多次直到最后只剩下一个人，其余人都将被杀掉。返回剩下的那一个人的号数。

Input

输入两个正整数N，M

Output

一个整数表示剩下那个人的编号

Sample Input 1 

6 5

Sample Output 1

1

Hint

0<=N&&M<=500

解题：思路一二为一般解属于正向思维，思路三递归数学模型解，可作为模板解望重点理解！

思路一：本来想用环形链表解决，解题相对也简单   

        循环链表的向下枚举不需要考虑头尾问题，直接node=node.next向下
        循环聊表的删除也不需要考虑头尾问题，直接node.next=node.next.next删除
        当然也有一些需要注意的地方！

        形成环形链表很简单，只需要将普通链表的最后一个节点的next指向第一个节点即可

        循环链表中只有一个节点的时候停止返回，即node.next=node的时候

        删除，需要找到待删除的前面节点，所以我们删除计数的时候要少即一位，利用前面的那个节点直接删除后面节点即可

        但是如果M特别大的话消耗的时间会更多，比如现在环中只剩3个人，要杀第300个人，就要循环next 300次，浪费太多时间了，很难AC

思路二：ArrayList集合，压缩无效喊数

        一百个人，杀喊103的兄弟，最左边的人开始喊从1喊道100无效定位了一轮，有用的其实就是又从头开始从101到103的情况；

        通过这样的逻辑重新定位会快很多

        屡一下逻辑：

        用left记录喊1的人，index记录要杀的人（index = left + M ）

        先判断index是否超过集合长度，

                如果超过：M先减掉left到最后一个人的人数，这时候left来到集合下标为0的人

                剩下的步数对集合长度求余，压缩出现从头到尾喊但是没杀人的情况；

                余数-1是最后一轮要杀的人的下标；

        然后remove掉下标元素就可以

        重复上步骤，直到list长度为1，结束；

上一手梵达芬奇高！需要灵魂感受的画。

 如图所示，M为步长，先减掉6个人（arrayList.size()-left），在对8求余数，就等于2，表示杀集合中第2个，转换成下标2-1赋值给变量index，remove（index）。

没看懂看代码自己品一下，不难滴，就是下标修正

完整代码：

import java.util.ArrayList;

public class T_01 {
    static int n = 6;
    static int m = 12;
    static int index = 12;
    public static void main(String[] args) {
        //初始化集合
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int j = 1; j <= 6; j++) {
            arrayList.add(j);
        }
        System.out.println(arrayList);
        //第一轮从第一个人开始喊，下标是0
        remove(arrayList,0);
        System.out.println("最后:"+arrayList);
    }
    static void remove(ArrayList<Integer> arrayList,int left){
        //设置结束条件
        if (arrayList.size() == 1){
            return;
        }
//        如果逻辑index大于N，表示从开始喊的人（不一定是集合的第一个人）到集合最后一个人是找不出杀谁的
//        需要从集合第一个开始继续数（这个阶段可以通过求余压缩）
        if (index > n){
//            因为第一轮可能出现不是从集合第一个人开始数的情况
//            统一把特殊情况处理
//            先减掉从开始喊的人到集合最后一个人
            index = (m-(arrayList.size()-left));
//            求余表示杀从头开始数第几个人
            int q = index%n;
            if (q == 0){
//                如果求余等于0就等于杀最后一个人，等于数组长度减一最后一个人的下标
                index = n-1;
            }else {
//                不等于0，余数-1等于下标
                index = (q-1);
            }
//            如果下标小于集合长度，代表一轮就能找到要杀的人
        } else if (index <= n) {
            index = index-1;
        }
//        移除集合中下标为index的元素
        arrayList.remove(index);
//        下一场游戏开始喊1的人
        left = index;
        n = arrayList.size();
//        如果你杀的是集合最后一个人，下一场游戏喊1的人在集合第一个，尾的下一个是头。
        if (left > n-1){
            left = 0;
        }
//        逻辑上要杀的位置
        index = left+m;
//        进入下一场，并告诉下一场开始喊1的人是谁
        remove(arrayList,left);
    }
}

思路三：数学模型加递归

        首先理解题意得知一定会得到一个存活的人，那考虑是否有一个方法，可以从已知的这个人得到他上一轮的编号，递归得到最开始的编号

        思维方式和之前的相反，之前是把该杀的人都杀掉得到或者的最后一个人

        现在是从结果得知最后一个人活着的人，往前推得到最开始的时候这个人的编号输出

        先从怎么将数转化成号

        数指的是要杀报到这个数，号指的是开始报数的人为1号，到最后一个人为n号

 剃刀式函数

y=x%i（基本式）

通过上加下减，左加右减

y=(x-1)%i+1（题意变式）

号 = （数-1）% 人数 + 1

s = (m-1)%n+1

解释：现在人数有3个人（编号为1,2,3），杀数到5的人，那么死的这个人的编号是2

开始搞前后关系

怎么由后推前

同样是剃头函数模型

前 = (后-1+s)%n+1

前 = (后-1+((m-1)%n+1))%n+1

getLive(n,m) = (getLive(n-1,m) -1 +(m-1)%n +1)%n +1

getLive(n,m) = (getLive(n-1,m) +(m-1)%n)%n +1

getLive(n,m) = (getLive(n-1,m) +m -1)%n +1

后的极限为最后活着的人号数为1

上代码

public class T_01_RE {
    public static void main(String[] args) {

        System.out.println(getLive(6,12));
    }

    /**
     * 剃刀函数
     * 首先确定怎么将数转换成号
     * 上加下减，左加右减
     * n=3  1 2 3
     * m=4
     * s = (m-1)%n+1
     * 怎么由后推前
     * 同样是剃头函数模型
     * 前 = (后-1+s)%n+1
     * 前 = (后-1+((m-1)%n+1))%n+1
     * getLive(n,m) = (getLive(n-1,m) -1 +(m-1)%n +1)%n +1
     * getLive(n,m) = (getLive(n-1,m) +(m-1)%n)%n +1
     * getLive(n,m) = (getLive(n-1,m) +m -1)%n +1
     * 后的极限为最后活着的人号数为1
     * @param n
     * @param m
     * @return
     */
    static int getLive(int n,int m){
        if (n == 1){
            return 1;
        }
        return (getLive(n-1,m) + m - 1)% n + 1;
    }
}

看不懂看大牛视频讲解：

【适合有经验】约瑟夫环问题_哔哩哔哩_bilibili

总结：

约瑟夫环问题还是常见的，视频收获很大，希望有兴趣的一定要好好看，如果第三解不好理解也建议直接背下来，可以解大部分约瑟夫环问题，实在想不通，可以试试第二解，比较符合正常思考逻辑但是笨一点哈哈。