复杂约瑟夫环算法

雪是梅之香

如果不知道简单约瑟夫环问题，请点击下面的链接：http://bbs.fishc.com/thread-58023-1-1.html
复杂约瑟夫环：

在历史上，约瑟夫环被广泛研究。一个推广的约瑟夫环问题如下：

有n个人环坐一圈，按照顺时针方向依次编号是1、2、3、…、n，有一个黑盒子放置在许多纸条，其上随机写有数字。每个人随机取一个纸条，纸条上的数字为出列数字，游戏开始时，任选一个数字m。从第一个人开始，按编号顺序自1开始顺序报数，报到m的人出列，同时将其手中的数字作为新的出列数字。然后，从下个人开始重新从1报数，如此循环下去，问最后剩下那个人？

代码实现：

import java.util.Random;
import java.util.Scanner;
public class P7_12 {
        private static Scanner input;
        public static void main(String[] args) {
                int data;
                int num;
                input = new Scanner(System.in);
                System.out.println("请输入约瑟夫环的人数：");
                int a=input.nextInt();
                LinkList1 p=null,q,htemp;
                Random r=new Random();
                for(int i=1;i<=a;i++){
                        data=r.nextInt(a)+1;
                        p=AddNode(p,data);
                        if(p==null){
                                break;
                        }
                }
                htemp=p;
                int j=0;
                while(htemp.next!=null){
                        htemp=htemp.next;
                }
                htemp.next=p;
                AllNode(p);
                htemp=p;
                num=r.nextInt(a)+1;
                System.out.println("第一次随机数是："+num);
                while(htemp.next!=htemp){
                        for(int i=1;i<num-1;i++){
                                htemp=htemp.next;
                        }
                        if(num==1){
                                q=htemp;
                                while(htemp.next!=q){
                                        htemp=htemp.next;
                                }
                                htemp.next=q.next;
                        }else{
                                q=htemp.next;
                                htemp.next=q.next;
                        }
                        num=q.data;
                        htemp=htemp.next;
                        j++;
                        System.out.printf("第%d人死亡,",j);
                        shuchu(q);
                        if(j%5==0){                                                //计数功能
                                System.out.printf("\n");
                        }
                }
                System.out.printf("第%d人死亡,自杀人手中拿的编号是：%d",j+1,htemp.data);
        }
        static void shuchu(LinkList1 q){
                System.out.printf("自杀人手中拿的编号是：%d---->",q.data);
        }

        static LinkList1 AddNode(LinkList1 p, int n) {
                LinkList1 q, htemp;
                q = new LinkList1();
                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(LinkList1 p){
                LinkList1 htemp;
                htemp=p;
                do{
                        System.out.printf("数据是:%d   ",htemp.data);
                        htemp=htemp.next;
                }while(htemp!=p);
        }
}
class LinkList1{
        int data;
        LinkList1 next;
}