马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
如果不知道简单约瑟夫环问题,请点击下面的链接: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;
- }
复制代码
|