用java实现的丢手帕问题，即有n个人围成圈，从第k个人开始从1报数，
报到第m个人时出局，从出局人的下一个开始从新报数，
报到第m个人时出局......如此循环直至最后一人出局

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

复制代码

这是当场就要回答出来吗？还是有考虑时间？

这是数据结构里的问题

这是一个经典题目，用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至剩下一个，求最后一个人编号。
约瑟夫环问题，我给出的解法有两种：
1. 建立一个有N个元素的循环链表，然后从链表头开始遍历并记数，如果计数i==m(i初始为1)踢出元素，继续循环，当当前元素与下一元素相同时退出循环，记录这个元素的初始编号就可以了，你自己实现吧，思路是这样的。
2.思想：归纳为数学性问题
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
  k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f=(f[i-1]+m)%i;  (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：

1. 
   
2. /*
   
3. **  n表示人数，m表示每隔几个就出局
   
4. */
   
5. int getWinner_num(int n,int m)
   
6. {
   
7.     int s = 0;
   
8.     for (int i = 2; i <= n; i++)
   
9.     {
   
10.         s = (s + m) % i;
    
11.     }
    
12.     return  s+1;
    
13. }

复制代码

这是我自己写的。题目类似，希望对你有用

//思路：定义一个int数组，容量为500，代表500个小朋友，数组中的所有元素的值都设为1，开始报数，报数到3的将该元素的值设为0，计算500元素的值和，当为1时，打印出编号。
class aaa
{
        public static void main(String[] args)
        {
                int i=1;
                int count=1;
                int[] array = new int[500];
                //赋值为1
                for(i=1;i<=500;i++)
                        array[i-1]=1;
                //当数组元素的和为1，则停止运行
                while(1!=sum(array))
                {
                        for(i=1;i<=500;i++)
                        {
                                //没有报过3的小朋友继续报数
                                if (array[i-1]==1)
                                {
                                        //让count在1-3循环
                                        if(count==4)
                                                count = 1;
                                        if(count==3)
                                                //报到3的退出
                                                array[i-1]=0;
                                        count++;
                                }
                        }
                }

                for(i=1;i<=500;i++)
                        if(array[i-1]==1)
                        System.out.print("最后一个小朋友是："+i);
        }
        public static int sum(int[] array)
        {
                int len = array.length;
                int sum=0;
                for(int i=0;i<len;i++)
                        sum = sum + array[i];
                return sum;
        }
}

学习了。

daoqin 发表于 2014-9-9 22:34
这是一个经典题目，用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至剩下一个，求最后一个 ...

大神，经典~~~

感觉会需要一些考虑时间

我有一个简单的模型，用boolean [] 数组来来表示小孩围成的圈，然后开始全部true,然后数，数到指定数人变为false,再重新开始数，重复下去，碰到到最后一个，下标回到开始，最后找出剩下的最后一个true:

1. public class countQuit {
   
2.         public static void main(String[] args) {
   
3.        
   
4.                 boolean[] circle = new boolean[500];
   
5.                 for(int i = 0;i < 500;i++) {
   
6.                         circle[i] = true;
   
7.                 }
   
8.                
   
9.                 int countNum = 0;
   
10.                 int index = 0;
    
11.                 int leftcount = circle.length;
    
12.                
    
13.                 while (leftcount > 1) {
    
14.                         if(circle[index] == true) {
    
15.                                 countNum++;       
    
16.                         }
    
17.                         if(countNum == 3) {
    
18.                                 circle[index] = false;
    
19.                                 countNum = 0;
    
20.                                 leftcount--;                       
    
21.                                 }
    
22.                         index++;
    
23.                         if(index == circle.length) {
    
24.                                 index = 0;
    
25.                                 }
    
26.                 }
    
27.                 for(int i = 0;i < circle.length;i++) {
    
28.                         if(circle[i] == true) {
    
29.                                 System.out.println(i);
    
30.                         }
    
31.                 }
    
32.         }
    
33. }

复制代码

我是来学习的