复杂约瑟夫环算法
如果不知道简单约瑟夫环问题，请点击下面的链接：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;
}
页:
[1]