题目
据说著名犹太历史学家 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开始记录。
- 有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。这时候我们就可以使用取余运算符,完美的进行使得时间复杂度达到O(n)的水平
方法二:递归
这里贴上一个链接
来自大神@啊啦啦工业
心中疑问的解答:
首先为什么不从1开始计数,而偏偏从0开始计数:为了顺从i一直降低的原则,也少了一个变量统计总人数i,若从1开始计数,则每次映射到新的地址为(i+1)%人数;变量变化复杂且麻烦。