有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;
   
2. 
   
3. 
   
4. public class demo09 {
   
5. 
   
6.         static final int Num=100;                                                 //总人数
   
7.         static final int KillMan=14;                                                 //数到多少退出
   
8. 
   
9.         static void Josephus(int alive)                                        //约瑟夫环算法
   
10.         {
    
11.             int[] man=new int[Num];
    
12.             int count=1;
    
13.             int i=0,pos=-1;
    
14. 
    
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);
    
59. 
    
60.         }
    
61. 
    
62. }
    

复制代码

这个算法有什么用的？

:handshake:handshake

研究研究......

  好强大~~~~~~~~~~~~~~~~~

能给点注释就好了，看的有点混乱

几行搞定;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.     }

复制代码