约瑟夫问题

雪是梅之香

背景：
据说著名犹太历史学家 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
好久没研究算法了，复习！

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