约瑟夫环问题〔Josephus〕.ppt

问题描述 已知n（2^15）个人（以编号1,2，…，n分别表示）围坐在一圆桌上，从编号为k（1≤ k≤ n）的人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依此重复，直到圆桌周围的人全部出列，依次输出最后三个出列的序号。 输入格式： 第一行为一个整数T（2^15）表示测试次数，接着第二到T+1行分别为n，m和k的值。 例：2 10 2 3 输出格式： T行最后min（n，3）个出列的编号。 结果：6 1 5 问题背景 这个问题是以弗拉维奥?约瑟夫斯命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。 解题方法 思路：将n个人分别用1,2…，n表示，并存放于一个数组中，将出列的人的号码从数组中删除，并输出最后三个出列的号码。 关键：（1）从第k个人开始报数，而非第一个人开始。 （2）当报到第n个人时，编号为1的人继续往下报数。 （3）显示出最后三个出列的人的编号。 public void SortArray(int[]a,int n,int m,int k,int g){ int[] b=new int[n]; int c=0; int i=k-2; while(true){ for(int j=0;jm;){ i=(i+1)%n; if(a[i]!=0){ j++; } } b[c]=a[i]; a[i]=0; c++; if(c==n) break; } System.out.print(“最后出列的3人: ); this.show(b,g); } } 数据测试 1.数据选择： 要求：n2^15; 1=k=n; 2.数据和结果显示： 数据测试 * n=12； k=4; m=3 出列 n=12; k=4; m=3 出列 Josephus jp=new Josephus(); int a[]=new int[n]; for(int i=0;in;i++){ a[i]=i+1; } jp.SortArray(a,n,m,k,g); } public void show(int[]b,int g){ for(int i=b.length-g;ib.length;i++){ System.out.print(b[i]+ ); } } 算法设计 2 1 4 最后出列的3人 2 循环数m 2 起始号码k 5 总人数n 6 1 5 最后出列的3人 3 循环数m 2 起始号码k 10 总人数n 3 14 6 最后出列的3人 8 循环数m 6 起始号码k 20 总人数n 18 23 26 最后出列的3人 7 循环数m 4 起始号码k 30 总人数n 47 21 46 最后出列的3人 15 循环数m 6 起始号码k 48 总人数n 38 54 4 最后出列的3人 25 循环数m 34 起始号码k 68 总人数n 87 32 21 最后出列的3人 4 循环数m 73 起始号码k 105 总人数n 32 53 97 最后出列的3人 23 循环数m 16 起始号码k 120 总人数n 70 296 198 最后出列的3人 12 循环数m 80 起始号码k 300 总人数n 166 358 266 最后出列的3人 30 循环数m 12 起始号码k 500 总人数n *