java数据结构题之约瑟夫问题
约瑟夫问题：转载自 约瑟夫问题
据说着名犹太历史/数学家约瑟夫（Josephus）有过以下的故事：在罗马人占领乔塔帕特後，40个犹太士兵与约瑟夫躲到一个洞中，眼见脱逃无望，一群人决定集体自杀，约瑟夫建议自杀方式，41个人排成圆圈，由第1个人开始报数，每报数到5的人就必须自杀，然後由下一个重新报数，直到所有人都自杀身亡为止。如果你是约瑟夫，你应该在哪个位置才能活下来（最后只剩下你）?
我的答案：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package
p1;
import
java.util.LinkedList;
import
java.util.List;
public
class
KillSelf {
//构造链式列表，用来模拟人。
private
static
List<String> list =
new
LinkedList<String>();
//记忆自杀那个人前后的人集合有序子列表
private
static
List<String> listBefore,listAfter;
//自杀那个人的编号从1开始
private
static
String killedNum =
null
;
private
static
int
KILL_INDEX =
4
;
//记录自杀的总人数
private
static
int
sum =
0
;
public
static
void
main(String[] args) {
//记住每个从最开始的编号
for
(
int
i =
1
;i <=
41
;i++)
{
list.add(i+
""
);
}
//其实自杀的过程，是一个循环的过程，所以用循环来解决。
while
(
true
)
{
//获取自杀位置前后的子集
if
(list.size()>=
5
)
//当人数大于等于5个人时
{
listBefore =
new
LinkedList<String>(list.subList(
0
, KILL_INDEX));
//不能直接用subList的返回值，要包装一下
listAfter =
new
LinkedList<String>(list.subList(KILL_INDEX+
1
, list.size()));
}
else
if
(list.size() >
1
&& list.size() <
5
)
//当人数多于1个人但是少于5个人时
{
KILL_INDEX =
5
%list.size()-
1
;
//这个判断很巧妙
if
(KILL_INDEX >
0
&& KILL_INDEX <list.size()-
1
)
{
listBefore =
new
LinkedList<String>(list.subList(
0
, KILL_INDEX));
//不能直接用subList的返回值，要包装一下
listAfter =
new
LinkedList<String>(list.subList(KILL_INDEX+
1
, list.size()));
}
else
if
(KILL_INDEX ==
0
)
{
listBefore.clear();
listAfter =
new
LinkedList<String>(list.subList(KILL_INDEX+
1
, list.size()));
}
else
if
(KILL_INDEX == list.size()-
1
)
{
listBefore =
new
LinkedList<String>(list.subList(
0
, KILL_INDEX));
listAfter.clear();
}
}
else
break
;
//将子集的后与前连接起来，更新总的集合
killedNum = list.get(KILL_INDEX);
sum++;
System.out.println(
"编号"
+ killedNum +
"已自杀!-----自杀总人数达"
+ sum);
//更新list
list.clear();
list.addAll(listAfter);
list.addAll(listBefore);
System.out.println(
"剩余人员编号："
+list);
System.out.println(
""
);
}
System.out.println(
""
);
System.out.println(
"结论：处在"
+list.get(
0
)+
"号才不会自杀"
);
}
}
|
但是网上的帖子，几行代码就解决问题了，这就是算法的魅力！
本文转自屠夫章哥 51CTO博客，原文链接：http://blog.51cto.com/4259297/1658382，如需转载请自行联系原作者
