黑马程序员技术交流社区

标题: 约瑟夫环算法 [打印本页]
作者: adalvik    时间: 2015-4-18 20:10
标题: 约瑟夫环算法
本帖最后由 adalvik 于 2015-4-18 20:12 编辑

有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？

这个问题是一哥们认为很难的问题,可能这哥们很少接触数据结构吧..其实这就是一个约瑟夫环算法的问题

先引入一个典故

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏...

是不是感觉这个问题 和 这哥们提的问题一样~

那么看代码吧


  1. import java.util.Scanner;


  4. public class demo09 {

  6.         static final int Num=100;                                                 //总人数
  7.         static final int KillMan=14;                                                 //数到多少退出

  9.         static void Josephus(int alive)                                        //约瑟夫环算法
  10.         {
  11.             int[] man=new int[Num];
  12.             int count=1;
  13.             int i=0,pos=-1;

  15.             while(count<=Num)
  16.             {
  17.                 do{
  18.                     pos=(pos+1) % Num;                  //环处理
  19.                     if(man[pos]==0)
  20.                         i++;
  21.                     if(i==KillMan)                                 //该人退出
  22.                     {
  23.                         i=0;
  24.                         break;
  25.                     }
  26.                 }while(true);
  27.                 man[pos]=count;
  28.                         System.out.printf("第%2d个人退出！约瑟夫环编号为%2d",pos+1,man[pos]);
  29.                         if(count%2==1)
  30.                         {
  31.                                 System.out.printf(" -> ");
  32.                         }
  33.                         else
  34.                         {
  35.                                 System.out.printf(" ->\n");                                //输出换行
  36.                         }
  37.                 count++;
  38.             }
  39.             System.out.printf("\n");
  40.             System.out.printf("这%d需要存活的人初始位置应排在以下序号:\n",alive);
  41.             alive=Num-alive;
  42.             for(i=0;i<Num;i++)
  43.                 {
  44.                 if(man[i]>alive)
  45.                         {
  46.                     System.out.printf("初始编号:%d,约瑟夫环编号:%d\n",i+1,man[i]);
  47.                         }
  48.                 }
  49.             System.out.printf("\n");
  50.         }
  51.         public static void main(String[] args)
  52.         {
  53.                 int alive;
  54.                 Scanner input=new Scanner(System.in);
  55.             System.out.printf("约瑟夫环问题求解!\n");
  56.                 System.out.printf("输入需要留存的人的数量:");               
  57.             alive=input.nextInt();                        //输入留存的人的数量
  58.                 Josephus(alive);

  60.         }

  62. }
复制代码





作者: nate996    时间: 2015-4-18 21:24
这个算法有什么用的？
作者: msyx9871453    时间: 2015-4-18 21:33
:handshake:handshake
作者: 18561271203    时间: 2015-4-18 21:43
研究研究......
作者: 刘镓旗    时间: 2015-4-18 21:50
  好强大~~~~~~~~~~~~~~~~~
作者: rick1991chen    时间: 2015-4-18 22:04
本帖最后由 rick1991chen 于 2015-4-18 22:07 编辑

能给点注释就好了，看的有点混乱
作者: fantacyleo    时间: 2015-4-18 22:14
几行搞定;P
  1.     public int josephusRing(int n, int m) {
  2.         int k = 1;
  3.         for (int i = 2; i <= n; i++) {
  4.             k = (k + m % i) > i ? (k + m % i) % i : k + m % i;
  5.         }
  6.        return k;
  7.     }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2