论坛 › Java语言交流 › 约瑟夫问题

雪是梅之香 发表于 2015-1-29 19:59:20

约瑟夫问题

本帖最后由 雪是梅之香 于 2015-1-29 22:18 编辑

背景：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。关于约瑟夫问题可以观看小甲鱼的《数据结构与算法》系列视频中的第018讲，现附上Java代码。public class P7_1 {
      public static void main(String[] args) {
                // TODO Auto-generated method stub
                LinkList p=null;
                LinkList htemp,q;
                for(int i=1;i<=41;i++){
                        p=AddNode(p,i);
                }
                htemp=p;
                while(htemp.next!=null){
                        htemp=htemp.next;
                }
                htemp.next=p;
                int num=3;
                htemp=p;
                int j=0;
                while(htemp.next!=htemp){
                        for(int i=1;i<num-1;i++){
                              htemp=htemp.next;
                        }
                        q=htemp.next;
                        htemp.next=q.next;
                        htemp=htemp.next;
                        shuchu(q);
                        j++;
                        if(j%5==0){                                                //计数功能
                              System.out.printf("\n");
                        }
                }
                System.out.printf("轮到第%d个人自杀",htemp.data);
               
      }
      static void shuchu(LinkList q){
                System.out.printf("轮到第%d个人自杀--->",q.data);
      }
      static LinkList AddNode(LinkList p,int n){
                LinkList q,htemp;
                if((q=new LinkList())==null){
                        return null;
                }else{
                        q.data=n;
                        q.next=null;
                        if(p==null){
                              p=q;
                              return p;
                        }else{
                              htemp=p;
                              while(htemp.next!=null){
                                        htemp=htemp.next;
                              }
                              htemp.next=q;
                              return p;
                        }
                }
      }
      static void AllNode(LinkList p){
                LinkList htemp;
                htemp=p;
                do{
                        System.out.println("数据是："+htemp.data);
                        htemp=htemp.next;
                }while(htemp!=p);
      }
}
class LinkList{
      int data;
      LinkList next;
}复杂约瑟夫环：http://bbs.fishc.com/thread-58026-1-1.html

百日维新 发表于 2015-1-29 22:05:28

本帖最后由 百日维新 于 2015-1-29 22:06 编辑

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

雪是梅之香 发表于 2015-1-29 22:17:28

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

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

查看完整版本: 约瑟夫问题