黑马程序员技术交流社区

标题: 看到有面试题，是关于算法的问题，想了老久都想不出怎么做。求大神 [打印本页]

---

作者: liaorubei    时间: 2014-9-7 21:36
标题: 看到有面试题，是关于算法的问题，想了老久都想不出怎么做。求大神
500个小孩围成一圈，从第一个开始报数：1，2，3，1,2,3,1,2,3,……每次报3的小孩退出
问最后剩下的那个小孩，在以前500人里是第几个？？？

脑子知道是怎么回事，就是在一圈的人中，一直的数，第次报3的人出列，直到最后的一个，然后最后的那个人，是一开始的500人中的第几个人，可是就是用代码显示不出来，而且在纸上慢慢数的话，和代码中给出的结果也不对，那个人帮我看看啊，最好的代码有注释。

---

作者: hejinzhong    时间: 2014-9-7 22:01

1. 
   
2. 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围,从1开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到最后一个人。
   
3. 
   
4. import java.util.Scanner;
   
5. 
   
6. public class Ex14 {
   
7. 
   
8.         public static void main(String[] args) {
   
9.                Scanner s = new Scanner(System.in);
   
10.                 int n = s.nextInt();
    
11.                 boolean[] arr = new boolean[n];
    
12.                 for (int i = 0; i < arr.length; i++) {
    
13.                        arr[i] = true;// 下标为TRUE时说明还在圈里
    
14.                 }
    
15.                 int leftCount = n;
    
16.                 int countNum = 0;
    
17.                 int index = 0;
    
18.                 while (leftCount > 1) {
    
19.                         if (arr[index] == true) {// 当在圈里时
    
20.                                 countNum++; // 报数递加
    
21.                                 if (countNum == 3) {// 报道3时
    
22.                                         countNum = 0;// 从零开始继续报数
    
23.                                         arr[index] = false;// 此人退出圈子
    
24.                                         leftCount--;// 剩余人数减一
    
25.                                 }
    
26.                         }
    
27.                         index++;// 每报一次数，下标加一
    
28.                         if (index == n) {// 是循环数数，当下标大于n时，说明已经数了一圈，
    
29.                                 index = 0;// 将下标设为零重新开始。
    
30.                         }
    
31.                 }
    
32.                 for (int i = 0; i < n; i++) {
    
33.                         if (arr[i] == true) {
    
34.                                 System.out.println(i + 1);
    
35.                         }
    
36.                 }
    
37.         }
    
38. //方法有很多，主要是思想问题
    
39. }
    
40. 
    

复制代码

---

作者: daoqin    时间: 2014-9-7 22:20


这是一个经典题目，用户输入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. }

复制代码

---

作者: liaorubei    时间: 2014-9-7 23:21

hejinzhong 发表于 2014-9-7 22:01

哦，你这个好像有点想得懂了，就是说原来标的编号不变，然后每次点到3的人就做一个另外的标记，是吧。当最后一个没有标记的人，原来的编号就是要求的结果。

---

作者: 不服™け你咬我    时间: 2014-9-7 23:41
学习学习

---

作者: hejinzhong    时间: 2014-9-8 00:10

liaorubei 发表于 2014-9-7 23:21
哦，你这个好像有点想得懂了，就是说原来标的编号不变，然后每次点到3的人就做一个另外的标记，是吧。当 ...

嗯，就看你怎么区分淘汰和未淘汰的人，还有报数如何循环的问题

---

作者: 谢建平    时间: 2014-9-8 00:59
第一个方法好 理解  第二个方法考到智商了 0.0

---

作者: 明天过后1    时间: 2014-9-8 01:17
我觉得对于难以理解的东西,用面向对象的思想很好找到解决方案,虽然效率不是很高
这是我的解决方案:
/**
* @author frank
*        对题目元素进行了抽象
*/
public class Child {
        //用来记录孩子在这个圈子中的序号
        public int index;
        //用来标志孩子是否出列
        public boolean isOut=false;
        //用来记录孩子当前报的号码,这个属性只能在孩子没被淘汰前生效
        public int num;
}

/**
* @author frank
* 演示
*/
public class Test {
        public static void main(String[] args) {
                //建立一个容器,就是围成一圈
                Child[] children=new Child[500];
                //往容器中填充元素
                Child temp=null;
                for (int i = 0; i < children.length; i++) {
                        temp=new Child();
                        children[i]=temp;
                }
                //给孩子们分配一个序号
                for (int i=1;i<=500;i++) {
                        children[i-1].index=i;
                }
                //用来表示当前孩子所报的号码
                int num=0;
                //用来记录当前剩下孩子的数量
                int count=500;
               
                while(count>1){//添加游戏约束条件:当前只剩下一个孩子
                        for (int i = 0; i < children.length; i++) {
                               
                                if(children[i].isOut==false){//没有处理的可以进行统计
                                        //当前孩子抱的号码
                                        num++;
                                        children[i].num=num;
                                       
                                        if(num==3){//出列
                                                children[i].isOut=true;//出列标志处理
                                                //完成三次报数就把它恢复为原始值
                                                num=0;
                                                //每出局一个孩子记录一下
                                                count--;
                                        }
                                       
                                       
                                }
                               
                        }
                }
               
                //最后找出没被淘汰的孩子
                for (Child c : children) {
                        if(c.isOut==false){
                                System.out.println("num:"+c.index);
                        }
                }
        }

}

---

作者: hailong    时间: 2014-9-8 16:49
学习 学习

---

作者: yl82846094    时间: 2014-9-8 17:19
看看，学习学习

---

作者: relive    时间: 2014-9-8 17:27
一个children类，包含属性int类型的index，放入一个ArrayList中，一直index模3然后remove，直至最后一个，获取index就可以了

---

作者: WakeUp    时间: 2014-9-9 04:25
mark一下

---

作者: 许愿じ☆VE杰    时间: 2014-9-9 07:01
学习学习

---

作者: 彭卫红    时间: 2014-9-9 07:24
都不错，思路打开了就好

---

作者: xbz1986    时间: 2014-9-9 08:25
学习，学习！

---

作者: MR.Sun    时间: 2014-9-9 08:46
学习学习！

---

作者: Sakuratossi    时间: 2014-9-9 11:55

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

第二种算法不是一般人想得到的啊，学习了

---

作者: ulopllo    时间: 2014-9-9 14:11

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

太给力了。。。真心赞
自己还得再好好揣摩下~智商不太够了

---

作者: king13131313    时间: 2014-9-9 18:24
最后应该剩下的是2个小孩吧？

---

作者: ╃→梅飛揚之城    时间: 2014-9-9 23:21
学习学习

---

作者: noway    时间: 2014-9-9 23:44
  看看  学学  提高智商

---

作者: 笑轻轻    时间: 2014-9-9 23:55
这题用个数学公式来表示一两句代码的问题，你写这么多看的人头晕。。

---

作者: liqi    时间: 2014-9-10 15:17
第二种方法厉害

---

作者: 爽朗的菜籽    时间: 2014-10-7 20:07
第二个方法真心有点厉害，，没看懂。。继续看

---

作者: 在学野马    时间: 2014-10-8 07:37
面试的有这么难吗。。

---

作者: 杜工    时间: 2014-10-8 08:03
一时半会琢磨不出来。。。

---

作者: 田峻菘    时间: 2014-10-8 13:37
学习了。

---

作者: jamesli    时间: 2015-3-1 00:15
有点看不懂，先收藏一下

---

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

黑马程序员IT技术论坛 X3.2