约瑟夫问题

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

方法1:数组法

思路:定义一个比人数多1的数组(方便进行计数)模拟题目中的情况,发现每次都是活着的人进行1~3的重复报数,报3的人都自杀那么可以使用取余进行简单的判断就能达成条件

public class yuesefu {
    public static void main (String[] args) {
        int i  = 1;
        int j = 41;
        boolean renshu[] = new boolean[42];
        while(i < 42){
            renshu[i] = true;
            i++;
        }///初始时候每个人都是活着的
        int g = 0;
        while (j > 2){
            for (i = 1;i < 42;i++){//可以将这里改为%则能少一个循环
                if (renshu[i] == true ){
                    g++;//对活着的人进行计数
                    if ( g % 3 == 0){
                        renshu[i] = false;
                        j--;//人死了剪掉
                    }
                }
            }
        }
        for (int o = 1;o < 42;o++){
            if (renshu[o] == true)System.out.println(o);
        }
    }
}

注意点:

  1. 记得计数的时候要从1开始记录。
  2. 有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。这时候我们就可以使用取余运算符,完美的进行使得时间复杂度达到O(n)的水平

方法二:递归

这里贴上一个链接
来自大神@啊啦啦工业

约瑟夫问题递归问题详解

心中疑问的解答:
首先为什么不从1开始计数,而偏偏从0开始计数:为了顺从i一直降低的原则,也少了一个变量统计总人数i,若从1开始计数,则每次映射到新的地址为(i+1)%人数;变量变化复杂且麻烦。

上一篇:循环链表实现约瑟夫环问题


下一篇:DotNet.CAP,或是.NET唯一靠谱的开源分布式框架