数据结构与算法--我们来玩丢手绢（约瑟夫环问题）

谁借莪１个温暖的怀抱￠ 2022-10-13 15:52 144阅读 0赞

#### 我们来玩丢手绢 ####

*  昨天我们打扑克，今天我们丢手绢
 *  丢手绢我们都知道这个游戏，他的由来由约瑟夫 （Josephus）提出来的

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，
    39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人
    该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，
    越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，
    直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。
    Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

*  问题来了，我们就不杀呀杀了，还是丢手绢吧，让n个人围成一个环，编号从1 ~n，从1 开始数当数到第m个人时候，他从圈中离开，接着从m+1 个人数，继续m个，在出局，依次复制这个过程，求最后一个出局的人是几号？

#### 方案一，环形链表 ####

*  题目明显提到了数字的圆圈，自然我们可以构造一个这样类似的数据结构去模拟这种过程。在常用数据结构中，n个阶段的环形链表很好的重现了这种模式  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]
 *  我们先构建n个节点的链表，每次删除第m个元素，当环形链表中元素只剩下一个时候得到解
 *  算法分析：
    
     *  链表头开始，指定位置position，链表尾指定位置before
     *  循环m次，分别将position与before都前移m-1次，得到指定位置
     *  删除psition位置节点，让position指向position.next，统计个数count = n-1
     *  继续以上步骤
 *  以上步骤中循环次数 （n-1）\*m次因此时间复杂度应该是O(nm)，当m特别大40000 ，时间复杂度会异常的大，非常慢
 *  优化：可以通过取余操作，直接计算出m次循环在 链表中实际的步骤，将 m % count -1得到实际步骤，当m是大数时候，优化效果明显
 *  如上分析有如下代码：

/** * 约瑟夫环问题： 将0,1,2,3,4.....n 这n个数字排列成一个圈圈，从数字0 开始数m个数，删掉他， * 接着从m+1 个开始数在来m个继续删除，一次类推，求出剩下的最后一个数据 * @author liaojiamin * @Date:Created in 14:30 2021/7/7 */
    public class JosephusForList { 
        public static void main(String[] args) { 
            System.out.println(delNodeForJosephus(40000,997));
        }
    
    
        /** * 环形链表方法 * */
        public static Integer delNodeForJosephus(Integer n, Integer m){ 
            if(n <= 0|| m<=0){ 
                return null;
            }
            //构造环形队列
            ListNode head = new ListNode(0);
            ListNode last = null;
            ListNode position = head;
            for (Integer i = 1; i < n; i++) { 
                last = new ListNode(i);
                position.setNext(last);
                position = position.getNext();
            }
            last.setNext(head);
            ListNode before = position;
            position = position.getNext();
    
            //当需要移动的位置小于当前数据个数，直接移动指针
            Integer count = n;
            while (m <= count){ 
                for (Integer i = 0; i < m-1; i++) { 
                    before = position;
                    position = position.getNext();
                }
                before.setNext(position.getNext());
                position = position.getNext();
                count--;
            }
            //当m 大于当前需要移动位置个数，取余计算最小移动值
            while (m > count && count > 1){ 
                int move = Math.abs(m%count - 1);
                for (Integer i = 0; i< move;i++){ 
                    before = position;
                    position = position.getNext();
                }
                before.setNext(position.getNext());
                position = position.getNext();
                count--;
            }
            position.setNext(null);
            return position.getValue();
        }
    
    }

*  以上算法时间复杂度O(nm)， 空间复杂度O(n)

#### 约瑟夫环问题 ####

*  约瑟夫环问题最终还是一个数学问题（数学能救命），我们大概来推导一下
 *  首先定义一个关于n 和 m的方法记为f(n, m)，表示每次在n个数字0~n-1中每次删除第m个数字，最后剩下的数字
 *  第一个删除的数字用n，m表示：（m-1）% n , 当且仅当 m>0 n>1的时候，我们记为k =（m-1）% n 如下图  
    ![在这里插入图片描述][20210707173909447.png]
 *  接着下一次遍历是从k+1 开始的现有数字总共 n-2个，k+1排第一，也就有如下图所示的顺序

![在这里插入图片描述][20210707174219696.png]

*  我们记录第一个删除后的值是 d(n-1, m)，与之前的 f(n, m)是同一个规则删除，那么他们最终的结果肯定是一样的，那么就有 d(n-1, m) = f(n, m)
 *  也就是我们将k+1当成是当前的第0 位置，k-1是当前最后的位置，也就是 n-2，那么我们依次推导出各个的位置，k+2是第一个位置
    
     *  n-2之后有n-1，在加上k个数 (n-2)-(k+2)+1=n-k-3
     *  n-2 之后有k1个数，(n-2)-(k+1)+1 = n-k+2
     *  同理 0 则是 n-k+1
     *  1 是 n-k
     *  k-1则是n-2
     *  用下图对应关系展示  
        ![在这里插入图片描述][20210707175110698.png]
 *  如上图，上部分是数据值，下部分是对应的位置，我们可以定义两个集合：
    
     *  A集合是上部分数据值
     *  B集合是下部分位置值
     *  A,B为非空集, 若存在对应法则f(), 使得对每个 x∈y 都有唯一确 y∈B与之对应, 则称对应法则f()为A到B的映射
 *  如果我们找到了数据值与 位置值的映射关系函数，是不是可以直接通过计算得到下一步中需要删除的数据
 *  此处，我们定义映射为p，推导出p(x) = (x-k-1)%n,映射的逆映射就是p(x) = (x+k+1)%n
 *  根据以上映射规则，映射之前的写中最后剩下的数字 d(n-1, m) = p\[f(n-1)+m\] = \[f(n-1,m) +k +1\]%n，将k=（m-1）%n 得到f(n,m) = d(n-1,m)= \[f(n-1,m) +k +1\]%n
 *  那么我们得到一个递推公式
    
     *  n =1 f(n, m) = 0
     *  n>1 f(n, m) = \[f(n-1, m)+m \]%n
 *  有了如上公式我们很自然直接递归就能得到第n次的结果
 *  如上分析有如下代码：

*  以上递归实现当n， m值非常大时候几乎不可用，情况通[之前文章斐波那契数量][Link 1]原因一样

#### 优化方案三 ####

*  动态规划解法：在以上推导基础上用一个循环解决

package com.ljm.resource.math.myList;
    
    /** * 约瑟夫环问题： 将0,1,2,3,4.....n 这n个数字排列成一个圈圈，从数字0 开始数m个数，删掉他， * 接着从m+1 个开始数在来m个继续删除，一次类推，求出剩下的最后一个数据 * @author liaojiamin * @Date:Created in 14:30 2021/7/7 */
    public class JosephusForList { 
        public static void main(String[] args) { 
            System.out.println(fixJosephusForMath2(40000,997));
        }
    
        /** * 动态规划实现 * 数学方案：通过计算得出发f(n,m) * n=0 f(n,m) = 1 * n>1 f(n,m) = [f(n-1,m)+m]%n * * */
        public static Integer fixJosephusForMath2(Integer n, Integer m){ 
            if(n <= 0|| m<=0){ 
                return null;
            }
            int last = 0;
            for(int i=2;i<=n;i++){ 
                last = (last+m)%i;
            }
            return last;
        }
    
    }

*  可以看出，以上实现思路分析非常复杂，但是代码简单时间复杂度O(n)，空间复杂度O(1)，远优于第一，第二解法

[上一篇：数据结构与算法–判断扑克牌是否顺子][Link 2]  
[下一篇：数据结构与算法–这个需求很简单怎么实现我不管（发散思维）][Link 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221005/18dd1674eb0c45cfa5992eb8bee03f66.png
[20210707173909447.png]: /images/20221005/c2f201c278294484b7f44305dc2b3964.png
[20210707174219696.png]: /images/20221005/3c1124ce23a34e6e9a8d5901f2250c4e.png
[20210707175110698.png]: /images/20221005/2e45dae2372c4f13ab67d81e164835ca.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114886125
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118522294
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/118578427