黑马程序员技术交流社区

标题: 面试中遇到的丢手帕问题？ [打印本页]
作者: 林磊    时间: 2014-9-8 19:41
标题: 面试中遇到的丢手帕问题？
用java实现的丢手帕问题，即有n个人围成圈，从第k个人开始从1报数，
报到第m个人时出局，从出局人的下一个开始从新报数，
报到第m个人时出局......如此循环直至最后一人出局
作者: 旭辉lin    时间: 2014-9-8 19:41
  1. class Child {
  2. int no; //编号
  3. Child nextChileChild = null; //指向下一个人

  5. public Child(int no) {

  7. this.no = no;
  8. }

  10. }

  12. //链表类

  14. //环形链表
  15. class CycLink {

  17. //先定义一个指向链表第一个小孩的那个引用
  18. //指向第一个小孩的引用，不能动
  19. Child firstChild = null;
  20. Child temp = null;
  21. int len = 0;// 表示共有几个小孩
  22. int k;
  23. int m;

  25. //设置链表大小
  26. public void setLen(int len) {
  27. this.len = len;
  28. }

  30. public void setK(int k) {
  31. //设置第几个人开始数数
  32. this.k = k;
  33. }

  35. public void setM(int m) {
  36. //设置m
  37. this.m = m;
  38. }

  40. public void play() {
  41. //1找到开始数数的人
  42. Child temp = this.firstChild;
  43. for (int i = 1; i < k; i++) {
  44. temp = temp.nextChileChild;

  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. }

  63. //初始化链表
  64. public void creatLink() {
  65. for (int i = 1; i <= len; i++) {

  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;

  79. } else {
  80. //继续创建小孩
  81. Child child = new Child(i);
  82. temp.nextChileChild = child;
  83. temp = child;
  84. }
  85. }

  87. }

  89. }

  91. public void show() {

  93. Child temChild = this.firstChild;
  94. do {
  95. System.out.println(temChild.no + "###");
  96. temChild = temChild.nextChileChild;
  97. } while (temChild != this.firstChild);
  98. }
  99. }

  101. //主方法类

  103. public class Demo4 {

  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. }
复制代码
作者: 中华教书人    时间: 2014-9-9 14:50
这是当场就要回答出来吗？还是有考虑时间？
作者: 506291315    时间: 2014-9-9 16:57
这是数据结构里的问题
作者: daoqin    时间: 2014-9-9 22:34
这是一个经典题目，用户输入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，程序也是异常简单：

  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. }
复制代码







作者: pvting    时间: 2014-9-12 00:44
这是我自己写的。题目类似，希望对你有用

//思路：定义一个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;
        }
}
作者: yingsun    时间: 2014-9-12 15:41
学习了。
作者: 小叶子    时间: 2014-9-27 09:40
daoqin 发表于 2014-9-9 22:34
这是一个经典题目，用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至剩下一个，求最后一个 ...

大神，经典~~~
作者: v咔咔    时间: 2014-11-8 22:30
感觉会需要一些考虑时间
作者: nuddlesW    时间: 2014-11-15 15:49
我有一个简单的模型，用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. }
复制代码
作者: Tae丶Yeon    时间: 2014-11-24 15:32
我是来学习的



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