目录
  1. 1. 题目
  2. 2. 思路
  3. 3. 实现
算法-约瑟夫问题

该题之前文章有,此处重复

题目

据说着名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人 开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的人都死光了,所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

思路

在循环处理的时候,数组保持长度不变,增加三个变量:
i作为循环遍历参数,超出数组长度则重置为0;
num,作为有效数字长度,每减一个数字,num–;
flag,满三减一,将需要减去的数字置位0。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Main {
public static void main(String[] args) {
int list[] = new int[41];
for (int i = 0; i < 41; i++) {
list[i] = (i + 1);
}
int i = 0, num = 41, flag = 0;
while (num > 2) {
//有效数字
if (list[i]!=0) {
flag++;
if (flag == 3) {
list[i] = 0;num--;flag = 0;
}
}
i++;
if (i >= list.length) {i = 0;}
}
for (i = 0; i < list.length; i++) {
if (list[i]==0) continue;
System.out.print(list[i] + " ");
}
}
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-约瑟夫问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论