鱼C论坛

 找回密码
 立即注册
查看: 3529|回复: 0

[技术交流] 复杂约瑟夫环算法

[复制链接]
发表于 2015-1-29 22:14:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
如果不知道简单约瑟夫环问题,请点击下面的链接:http://bbs.fishc.com/thread-58023-1-1.html
复杂约瑟夫环:
在历史上,约瑟夫环被广泛研究。一个推广的约瑟夫环问题如下:
n个人环坐一圈,按照顺时针方向依次编号是123n,有一个黑盒子放置在许多纸条,其上随机写有数字。每个人随机取一个纸条,纸条上的数字为出列数字,游戏开始时,任选一个数字m。从第一个人开始,按编号顺序自1开始顺序报数,报到m的人出列,同时将其手中的数字作为新的出列数字。然后,从下个人开始重新从1报数,如此循环下去,问最后剩下那个人?
代码实现:
  1. import java.util.Random;
  2. import java.util.Scanner;
  3. public class P7_12 {
  4.         private static Scanner input;
  5.         public static void main(String[] args) {
  6.                 int data;
  7.                 int num;
  8.                 input = new Scanner(System.in);
  9.                 System.out.println("请输入约瑟夫环的人数:");
  10.                 int a=input.nextInt();
  11.                 LinkList1 p=null,q,htemp;
  12.                 Random r=new Random();
  13.                 for(int i=1;i<=a;i++){
  14.                         data=r.nextInt(a)+1;
  15.                         p=AddNode(p,data);
  16.                         if(p==null){
  17.                                 break;
  18.                         }
  19.                 }
  20.                 htemp=p;
  21.                 int j=0;
  22.                 while(htemp.next!=null){
  23.                         htemp=htemp.next;
  24.                 }
  25.                 htemp.next=p;
  26.                 AllNode(p);
  27.                 htemp=p;
  28.                 num=r.nextInt(a)+1;
  29.                 System.out.println("第一次随机数是:"+num);
  30.                 while(htemp.next!=htemp){
  31.                         for(int i=1;i<num-1;i++){
  32.                                 htemp=htemp.next;
  33.                         }
  34.                         if(num==1){
  35.                                 q=htemp;
  36.                                 while(htemp.next!=q){
  37.                                         htemp=htemp.next;
  38.                                 }
  39.                                 htemp.next=q.next;
  40.                         }else{
  41.                                 q=htemp.next;
  42.                                 htemp.next=q.next;
  43.                         }
  44.                         num=q.data;
  45.                         htemp=htemp.next;
  46.                         j++;
  47.                         System.out.printf("第%d人死亡,",j);
  48.                         shuchu(q);
  49.                         if(j%5==0){                                                //计数功能
  50.                                 System.out.printf("\n");
  51.                         }
  52.                 }
  53.                 System.out.printf("第%d人死亡,自杀人手中拿的编号是:%d",j+1,htemp.data);
  54.         }
  55.         static void shuchu(LinkList1 q){
  56.                 System.out.printf("自杀人手中拿的编号是:%d---->",q.data);
  57.         }

  58.         static LinkList1 AddNode(LinkList1 p, int n) {
  59.                 LinkList1 q, htemp;
  60.                 q = new LinkList1();
  61.                 q.data = n;
  62.                 q.next = null;
  63.                 if (p == null) {
  64.                         p = q;
  65.                         return p;
  66.                 } else {
  67.                         htemp = p;
  68.                         while (htemp.next != null) {
  69.                                 htemp = htemp.next;
  70.                         }
  71.                         htemp.next = q;
  72.                         return p;
  73.                 }

  74.         }
  75.         static void AllNode(LinkList1 p){
  76.                 LinkList1 htemp;
  77.                 htemp=p;
  78.                 do{
  79.                         System.out.printf("数据是:%d   ",htemp.data);
  80.                         htemp=htemp.next;
  81.                 }while(htemp!=p);
  82.         }
  83. }
  84. class LinkList1{
  85.         int data;
  86.         LinkList1 next;
  87. }
复制代码



想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 18:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表