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,如需转载请自行联系原作者



上一篇:索引性能好不好让二元高度来说话


下一篇:阿里云ace考试范围有哪些?考阿里云ace认证有什么用?