约瑟夫

约瑟夫出圈问题 两种方法实现，数据和链表 n个人围成一个圈，一个个首尾相连的圈报数，从第一个开始报数
 报到m的人出圈，剩下的人继续从1开始报数，直到所有人都出圈为止。

1. import java.util.LinkedList;   
2. import java.util.Scanner;   
3.   
4. /**  
5.  * 约瑟夫出圈问题 两种方法实现，数据和链表 n个人围成一个圈，一个个首尾相连的圈报数，从第一个开始报数  
6.  * 报到m的人出圈，剩下的人继续从1开始报数，直到所有人都出圈为止。  
7.  *   
8.  * @author sesame.yangj  
9.  */  
10. public class Joseph {   
11.   
12.     /**  
13.      * @param args  
14.      */  
15.     public static void main(String[] args) {   
16.         Joseph j = new Joseph();   
17.         System.out.println("约瑟夫出圈");   
18.         System.out.println("输入人数:");   
19.         Scanner s = new Scanner(System.in);   
20.         int n = s.nextInt();   
21.         System.out.println("输入出圈的位置:");   
22.         int m = s.nextInt();   
23.         System.out.println("数组实现");   
24.         j.arrayJoseph(n, m);   
25.         System.out.println("链表实现");   
26.         j.listJoseph(n, m);   
27.     }   
28.   
29.     /**  
30.      * 用数组实现  
31.      *   
32.      * @param n 总的人数  
33.      * @param m 当前报的数  
34.      */  
35.     public void arrayJoseph(int n, int m) {   
36.         //数组存储编号   
37.         int array[] = new int[n];   
38.         int len = n;   
39.         for (int i = 0; i < array.length; i++) {   
40.             array[i] = i + 1;   
41.         }   
42.   
43.         int i = 0;   
44.         //当前报的数   
45.         int j = 1;   
46.   
47.         while (len > 0) {   
48.             if (array[i % n] > 0) {   
49.                 //位置有人   
50.                 if (j % m == 0) {   
51.                     //报到出圈的人   
52.                     System.out.println(array[i % n]);   
53.                     //为之置空   
54.                     array[i % n] = -1;   
55.                     //从1开始报数   
56.                     j = 1;   
57.                     i++;   
58.                     len--;   
59.                 } else {   
60.                     i++;   
61.                     j++;   
62.                 }   
63.             } else {   
64.                 //遇到空位   
65.                 i++;   
66.             }   
67.         }   
68.     }   
69.   
70.     /**  
71.      * 用双向链表实现  
72.      *   
73.      * @param n  
74.      * @param m  
75.      */  
76.     public void listJoseph(int n, int m) {   
77.         LinkedList<Integer> list = new LinkedList<Integer>();   
78.         for (int i = 0; i < n; i++) {   
79.             //添加数据,与编号对应   
80.             list.add(i + 1);   
81.         }   
82.         int moved = 0;   
83.         while (list.size() > 0) {   
84.             moved = (moved + m - 1) % list.size();   
85.             System.out.println(list.get(moved));   
86.             list.remove(moved);   
87.         }   
88.     }   
89. }  

 

1. public class Joseph {   
2.   
3.     /**  
4.      * 问题描述  
5.      * 约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号  
6.      * 开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，  
7.      * 直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。  
8.      * 输入数据  
9.      * 每行是用空格分开的两个整数,第一个是 n ,第二个是 m ( 0 < m, n < 300),最后一行是：0 0   
10.      * 输出要求  
11.      * 对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号  
12.      * 输入样例：  
13.      * 6 2  
14.      * 12 4  
15.      * 8 3  
16.      * 0 0  
17.      * 输出样例：  
18.      * 5  
19.      * 1  
20.      * 7  
21.      */  
22.     public static void main(String[] args) {   
23.   
24.         Scanner in =new Scanner(System.in);    
25.         System.out.print("有几只猴子选大王?");    
26.         int amount = in.nextInt();   
27.         System.out.print("喊几的退出圈子?");    
28.         int num = in.nextInt();   
29.   
30.         // 定义"猴子圈"   
31.         Set<Integer> monkeys = new TreeSet<Integer>();   
32.         // 初始化"猴子圈",确定每只猴子的编号。   
33.         for (int i = 1; i <= amount; i++) {   
34.             monkeys.add(i);   
35.         }   
36.            
37.         // 初始化报的数为1   
38.         int i = 1;   
39.         // 开始报数! 每一轮报数,都接着上次报的数i进行,"猴子圈"只剩1只猴子了就停止报数   
40.         while (monkeys.size() > 1) {   
41.             // 定义猴子编号数组,用于迭代"猴子圈"   
42.             Integer[] monkeyNums = monkeys.toArray(new Integer[0]);   
43.             // 迭代"猴子圈",作为一轮报数   
44.             for (int monkeyNum : monkeyNums) {   
45.                 if (i < num) {   
46.                     // 下只猴子要报的数   
47.                     i++;   
48.                 } else {   
49.                     // 如果这只猴子报的数是num,就把它移出"猴子圈"   
50.                     monkeys.remove(monkeyNum);   
51.                     // 下只猴子报数从1开始   
52.                     i = 1;   
53.                 }   
54.             }   
55.         }   
56.            
57.         // "猴子圈"的最后一只猴子做大王。   
58.         int king = 0;   
59.         for (int monkeyNum : monkeys) {   
60.             king = monkeyNum;   
61.         }   
62.            
63.         System.out.println("大王是" + king + "号猴子");   
64.     }   
65.   
66. }