1. 
   
2. //数据结构 约瑟夫问题
   
3. /*用java实现的丢手帕问题，即有n个人围成圈，从第k个人开始从1报数，
   
4. 报到第m个人时出局，从出局人的下一个开始从新报数，
   
5. 报到第m个人时出局......如此循环直至最后一人出局*/
   
6. class Child {
   
7. int no; //编号
   
8. Child nextChileChild = null; //指向下一个人
   
9. 
   
10. public Child(int no) {
    
11. 
    
12. this.no = no;
    
13. }
    
14. 
    
15. }
    
16. 
    
17. //链表类
    
18. 
    
19. //环形链表
    
20. class CycLink {
    
21. 
    
22. //先定义一个指向链表第一个小孩的那个引用
    
23. //指向第一个小孩的引用，不能动
    
24. Child firstChild = null;
    
25. Child temp = null;
    
26. int len = 0;// 表示共有几个小孩
    
27. int k;
    
28. int m;
    
29. 
    
30. //设置链表大小
    
31. public void setLen(int len) {
    
32. this.len = len;
    
33. }
    
34. 
    
35. public void setK(int k) {
    
36. //设置第几个人开始数数
    
37. this.k = k;
    
38. }
    
39. 
    
40. public void setM(int m) {
    
41. //设置m
    
42. this.m = m;
    
43. }
    
44. 
    
45. public void play() {
    
46. //1找到开始数数的人
    
47. Child temp = this.firstChild;
    
48. for (int i = 1; i < k; i++) {
    
49. temp = temp.nextChileChild;
    
50. 
    
51. }
    
52. //数M下
    
53. while (this.len != 1) {
    
54. for (int j = 1; j < m; j++) {
    
55. temp = temp.nextChileChild;
    
56. }
    
57. Child temp2 = temp;// 找到要出圈的前一个小孩
    
58. //讲数到M的小孩 退出圈
    
59. temp2=temp2.nextChileChild;
    
60. temp.nextChileChild=temp2.nextChileChild;
    
61. System.out.println("现在出圈的是" + temp2.no);
    
62. this.len--;
    
63. }
    
64. //打印最优一个小孩
    
65. System.out.print("最后出圈的是：" + temp.no);
    
66. }
    
67. 
    
68. //初始化链表
    
69. public void creatLink() {
    
70. for (int i = 1; i <= len; i++) {
    
71. 
    
72. if (i == 1) {
    
73. //创建第一小孩
    
74. Child child = new Child(i);
    
75. this.firstChild = child;
    
76. this.temp = child;
    
77. } else {
    
78. if (i == len) {
    
79. Child child = new Child(i);
    
80. temp.nextChileChild = child;
    
81. temp = child;
    
82. temp.nextChileChild = this.firstChild;
    
83. 
    
84. } else {
    
85. //继续创建小孩
    
86. Child child = new Child(i);
    
87. temp.nextChileChild = child;
    
88. temp = child;
    
89. }
    
90. }
    
91. 
    
92. }
    
93. 
    
94. }
    
95. 
    
96. public void show() {
    
97. 
    
98. Child temChild = this.firstChild;
    
99. do {
    
100. System.out.println(temChild.no + "###");
     
101. temChild = temChild.nextChileChild;
     
102. } while (temChild != this.firstChild);
     
103. }
     
104. }
     
105. 
     
106. //主方法类
     
107. 
     
108. public class Demo4 {
     
109. 
     
110. public static void main(String[] args) {
     
111. //TODO Auto-generated method stub
     
112. CycLink cyclink =new CycLink();
     
113. cyclink.setLen(17);
     
114. cyclink.creatLink();
     
115. cyclink.setK(17);//17代表尾号//从1号开始念
     
116. cyclink.setM(3);//输出念到3的人出圈
     
117. cyclink.show();
     
118. cyclink.play();
     
119. }
     
120. }
     
121. 
     

复制代码

1. 
   
2. //数据结构 约瑟夫问题
   
3. /*用java实现的丢手帕问题，即有n个人围成圈，从第k个人开始从1报数，
   
4. 报到第m个人时出局，从出局人的下一个开始从新报数，
   
5. 报到第m个人时出局......如此循环直至最后一人出局*/
   
6. class Child {
   
7. int no; //编号
   
8. Child nextChileChild = null; //指向下一个人
   
9. 
   
10. public Child(int no) {
    
11. 
    
12. this.no = no;
    
13. }
    
14. 
    
15. }
    
16. 
    
17. //链表类
    
18. 
    
19. //环形链表
    
20. class CycLink {
    
21. 
    
22. //先定义一个指向链表第一个小孩的那个引用
    
23. //指向第一个小孩的引用，不能动
    
24. Child firstChild = null;
    
25. Child temp = null;
    
26. int len = 0;// 表示共有几个小孩
    
27. int k;
    
28. int m;
    
29. 
    
30. //设置链表大小
    
31. public void setLen(int len) {
    
32. this.len = len;
    
33. }
    
34. 
    
35. public void setK(int k) {
    
36. //设置第几个人开始数数
    
37. this.k = k;
    
38. }
    
39. 
    
40. public void setM(int m) {
    
41. //设置m
    
42. this.m = m;
    
43. }
    
44. 
    
45. public void play() {
    
46. //1找到开始数数的人
    
47. Child temp = this.firstChild;
    
48. for (int i = 1; i < k; i++) {
    
49. temp = temp.nextChileChild;
    
50. 
    
51. }
    
52. //数M下
    
53. while (this.len != 1) {
    
54. for (int j = 1; j < m; j++) {
    
55. temp = temp.nextChileChild;
    
56. }
    
57. Child temp2 = temp;// 找到要出圈的前一个小孩
    
58. //讲数到M的小孩 退出圈
    
59. temp2=temp2.nextChileChild;
    
60. temp.nextChileChild=temp2.nextChileChild;
    
61. System.out.println("现在出圈的是" + temp2.no);
    
62. this.len--;
    
63. }
    
64. //打印最优一个小孩
    
65. System.out.print("最后出圈的是：" + temp.no);
    
66. }
    
67. 
    
68. //初始化链表
    
69. public void creatLink() {
    
70. for (int i = 1; i <= len; i++) {
    
71. 
    
72. if (i == 1) {
    
73. //创建第一小孩
    
74. Child child = new Child(i);
    
75. this.firstChild = child;
    
76. this.temp = child;
    
77. } else {
    
78. if (i == len) {
    
79. Child child = new Child(i);
    
80. temp.nextChileChild = child;
    
81. temp = child;
    
82. temp.nextChileChild = this.firstChild;
    
83. 
    
84. } else {
    
85. //继续创建小孩
    
86. Child child = new Child(i);
    
87. temp.nextChileChild = child;
    
88. temp = child;
    
89. }
    
90. }
    
91. 
    
92. }
    
93. 
    
94. }
    
95. 
    
96. public void show() {
    
97. 
    
98. Child temChild = this.firstChild;
    
99. do {
    
100. System.out.println(temChild.no + "###");
     
101. temChild = temChild.nextChileChild;
     
102. } while (temChild != this.firstChild);
     
103. }
     
104. }
     
105. 
     
106. //主方法类
     
107. 
     
108. public class Demo4 {
     
109. 
     
110. public static void main(String[] args) {
     
111. //TODO Auto-generated method stub
     
112. CycLink cyclink =new CycLink();
     
113. cyclink.setLen(17);
     
114. cyclink.creatLink();
     
115. cyclink.setK(17);//17代表尾号//从1号开始念
     
116. cyclink.setM(3);//输出念到3的人出圈
     
117. cyclink.show();
     
118. cyclink.play();
     
119. }
     
120. }
     
121. 
     

复制代码