约瑟夫问题

雪是梅之香

背景：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。关于约瑟夫问题可以观看小甲鱼的《数据结构与算法》系列视频中的第018讲，现附上Java代码。

1. public class P7_1 {
   
2.         public static void main(String[] args) {
   
3.                 // TODO Auto-generated method stub
   
4.                 LinkList p=null;
   
5.                 LinkList htemp,q;
   
6.                 for(int i=1;i<=41;i++){
   
7.                         p=AddNode(p,i);
   
8.                 }
   
9.                 htemp=p;
   
10.                 while(htemp.next!=null){
    
11.                         htemp=htemp.next;
    
12.                 }
    
13.                 htemp.next=p;
    
14.                 int num=3;
    
15.                 htemp=p;
    
16.                 int j=0;
    
17.                 while(htemp.next!=htemp){
    
18.                         for(int i=1;i<num-1;i++){
    
19.                                 htemp=htemp.next;
    
20.                         }
    
21.                         q=htemp.next;
    
22.                         htemp.next=q.next;
    
23.                         htemp=htemp.next;
    
24.                         shuchu(q);
    
25.                         j++;
    
26.                         if(j%5==0){                                                //计数功能
    
27.                                 System.out.printf("\n");
    
28.                         }
    
29.                 }
    
30.                 System.out.printf("轮到第%d个人自杀",htemp.data);
    
31.                
    
32.         }
    
33.         static void shuchu(LinkList q){
    
34.                 System.out.printf("轮到第%d个人自杀--->",q.data);
    
35.         }
    
36.         static LinkList AddNode(LinkList p,int n){
    
37.                 LinkList q,htemp;
    
38.                 if((q=new LinkList())==null){
    
39.                         return null;
    
40.                 }else{
    
41.                         q.data=n;
    
42.                         q.next=null;
    
43.                         if(p==null){
    
44.                                 p=q;
    
45.                                 return p;
    
46.                         }else{
    
47.                                 htemp=p;
    
48.                                 while(htemp.next!=null){
    
49.                                         htemp=htemp.next;
    
50.                                 }
    
51.                                 htemp.next=q;
    
52.                                 return p;
    
53.                         }
    
54.                 }
    
55.         }
    
56.         static void AllNode(LinkList p){
    
57.                 LinkList htemp;
    
58.                 htemp=p;
    
59.                 do{
    
60.                         System.out.println("数据是："+htemp.data);
    
61.                         htemp=htemp.next;
    
62.                 }while(htemp!=p);
    
63.         }
    
64. }
    
65. class LinkList{
    
66.         int data;
    
67.         LinkList next;
    
68. }

复制代码

复杂约瑟夫环：http://bbs.fishc.com/thread-58026-1-1.html

百日维新

好久没研究算法了，复习！

雪是梅之香

百日维新 发表于 2015-1-29 22:05
好久没研究算法了，复习！

版主不要谦虚，这是我刚写的复杂约瑟夫环，帮忙看一下有无错误，我检查了半天，没找到
http://bbs.fishc.com/thread-58026-1-1.html