淘宝面试题 n个人围成一圈，报到m的人出列

有N个人围成一圈，第一个人从1开始报数，报到M的人出列，求最后一个出列的人。
这是一个约瑟夫环问题，下面给出了java实现的例子：

package com.juziku;

import java.util.Arrays;


/**
* n个人围成一圈，报到m的人出列
* @author sunlightcs
* 2011-3-8
* http://hi.juziku.com/sunlightcs/
*/
public class Queue {

	public static void main(String[] args) {
		queue(10, 3);
	}
	
	/**
	 * 最后出队的人
	 * @param total  总的人数
	 * @param num    第几号出队
	 */
	public static void queue(int total, int num){
		//定义一个数组，true表示没有出队列的，false表示已经出队列的
		boolean []arr = new boolean[total];
		Arrays.fill(arr, true);
		
		//移动变量，如：1  2  3  1  2  3  1  2
		int next = 1;
		
		//数组下标
		int index = 0;
		
		//剩下的人数
		int count = total;
		
		//如果剩下的人数为1人时，停止报数
		while(count>1){
			if(arr[index] == true){
				if(next == 3){
					arr[index] = false;
					
					//剩下的人数减1
					--count;
					
					//移动变量复位，从1开始报数
					next = 1;
					
					System.out.println("依次出列的人为："+(index+1));
				}else{
					++next;
				}
			}
			
			++index;
			if(index == total){
				//数组下标复位，从0开始新重遍历
				index = 0;
			}
		}		
		for(int i=0; i<total; i++){
			if(arr[i] == true){
				System.out.println("最后出列的人为："+(i+1));
			}
		}
	}
	
}

全文请访问：人人编程

评论

50 楼 necsoftscp 2014-08-28  

args

49 楼 jkxydp 2011-09-27  

代码行数太多，逻辑太啰嗦，递归就简单多了。

48 楼 dypy3 2011-04-23  

这个之前自己写的，虽然不完全一样，但都差不多
public class MyCount3Quit{
public static void main(String[] agrs){
    KidCircle kid =new KidCircle(500);
    int n=kid.count(0,2);
    kid.delNext(n);
    while(kid.getLen()>1){
       n=kid.count(n,3);
       kid.delNext(n);
    }
    System.out.println(n);
}
}

class KidCircle{
   // private int[] kid;
    private int[] next;
    private int len;
    KidCircle(int i){
      len=i;
     // kid=new int[i];
      next=new int[i];
      for(int j=0;j<i-1;j++){
         //kid[j]=j;
         next[j]=j+1;
      }
      next[i-1]=0;
   }
  
   public int getLen(){return len;}
  
   public int length(){
       return len;
   }
  
   public int count(int n, int i){     //返回第I个人的位置
      for(int j=1;j<i;j++){
         n=next[n];
      }
      return n;
   }
  
   public void delNext(int i){
      next[i]=next[next[i]];
      len--;
   }
}

47 楼 sunlightcs 2011-04-22  

Simon.C 写道

哈哈，又见数据结构了
关于题目，有点不明：报到M,意思是说M出列后又从1开始报？

是这个意思了。

46 楼 Simon.C 2011-04-22  

哈哈，又见数据结构了
关于题目，有点不明：报到M,意思是说M出列后又从1开始报？

45 楼 sunlightcs 2011-04-22  

qrg 写道

有一个小小的疑问：为什么不直接用 if(arr[index])，而非要用if(arr[index] == true)呢？

习惯问题，

44 楼 accphc 2011-04-21  

<p>
</p>
<pre name="code" class="java">public static int find(int n, int m)
{
if(n==1)
return 0;
int r = 0;
for (int i = (m-1)%n; i &lt;= n; i++) {
r = ((r + m)%n )% i;
}
return r + 1;
}</pre>
 

43 楼 a06062125 2011-04-21  

<p>明白了~</p>
<p> </p>

42 楼 qrg 2011-04-21  

有一个小小的疑问：为什么不直接用 if(arr[index])，而非要用if(arr[index] == true)呢？

41 楼 bookcaicai 2011-04-21  

albertshaw 写道

public int find(int n, int m)
	{
		int r = 0;
		for (int i = 2; i <= n; i++) {
			r = (r + m) % i;
		}
		return r + 1;
	}

以前在论坛里看到过一个实现,说实话我没看懂,但是试了几个都是正确的,希望数学好的朋友来解释下.

见：http://baike.baidu.com/view/717633.htm#sub717633

40 楼 fivestarwy 2011-04-21  

dsjt 写道

fivestarwy 写道

albertshaw 写道

public int find(int n, int m)
	{
		int r = 0;
		for (int i = 2; i <= n; i++) {
			r = (r + m) % i;
		}
		return r + 1;
	}

以前在论坛里看到过一个实现,说实话我没看懂,但是试了几个都是正确的,希望数学好的朋友来解释下.

f(1,m)=0
f(n,m)=(f(n-1,m)+m)%n

还是不明白这个递推公式 是怎么求出来的？

n个人最后剩下来的人序号为f(n,m)，死了一个人后其实序号是不变的，以此建立递推关系
死了一人后算f(n-1,m)得到的序号其实是从第m个开始计数的，所以要加m

39 楼 549265480 2011-04-21  

#include "stdafx.h"
#include"iostream"
#define Size 100

typedef int type  ;
using namespace std;

void kill(int a[],int len,int n)
{
int b[Size];
int j=1;
for(int i=n;i<len;i++)
{
b[j]=a[i+1];
j++;
}
for(int i=1;i<n;i++)
{
b[j]=a[i];
j++;
}
for(int i=1;i<len;i++)
{
a[i]=b[i];
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int a[Size],b[Size],m,n,len;
cout<<"请输入多少人：";
cin>>len;
cout<<"请输入从几开始报数";
cin>>m;
cout<<"请输入数到几的人处死";
cin>>n;
int t=m;
int tn=1;

if(m>len)
{
cout<<"没有那么多人"<<endl;
exit(1);
}

for(int i=1;i<=len;i++)
{
a[i]=i;
}
cout<<"所有人站好了！"<<endl;
for(int i=1;i<=len;i++)
cout<<a[i]<<"  ";
cout<<endl;

cout<<"从"<<m<<"开始数，从新排队"<<endl;

int j=1;
for(int i=m;i<=len;i++)
{
b[j]=a[i];
j++;
}
for(int i=1;i<m;i++)
{
b[j]=a[i];
j++;
}

cout<<"所有人站好了！"<<endl;
for(int i=1;i<=len;i++)
cout<<b[i]<<"  ";
cout<<endl;

int temp=1;
int i=1;
while(len!=1)
{
cout<<b[i]<<"数到"<<temp<<endl;
if(temp==n)
{
cout<<b[i]<<"被杀"<<endl;

kill(b,len,i);
len--;
temp=1;
i=1;

cout<<"所有人站好了！"<<endl;
for(int ii=1;ii<=len;ii++)
cout<<b[ii]<<"  ";
cout<<endl;
}
else
{
if(i==len)
i=0;
i++;
temp++;
}
}
cout<<"最后留下"<<a[1]<<endl;
return 0;
}

纯数组

38 楼 dsjt 2011-04-21  

fivestarwy 写道

albertshaw 写道

public int find(int n, int m)
	{
		int r = 0;
		for (int i = 2; i <= n; i++) {
			r = (r + m) % i;
		}
		return r + 1;
	}

以前在论坛里看到过一个实现,说实话我没看懂,但是试了几个都是正确的,希望数学好的朋友来解释下.

f(1,m)=0
f(n,m)=(f(n-1,m)+m)%n

还是不明白这个递推公式 是怎么求出来的？

37 楼 idle_sun 2011-04-21  

int r = 0;  
for (int i = 2; i <= n; i++) {  
     r = (r + m) % i;  
}  
return r + 1; 


居然可以有这么强悍的实现。。。　没看懂　能讲一下不。。

36 楼 idle_sun 2011-04-21  

　　　　　　　　　 int current = -1;
List<Integer> nl = new ArrayList<Integer>();
for(int i = 1;i<=n;i++){
nl.add(i);
}

for(int i = 1; i<=n && nl.size()>1;i++){
current += m;
current = current >= nl.size() ? current = current%nl.size() : current; 
nl.remove(current);
current --;
}


集合比数组更方便一些(size()方法),我承认,我比前面那位数组实现的同学更懒　-0-

35 楼 wuliaolll 2011-04-21  

单向循环链表啊，数据结构最基础的问题了

34 楼 kasirin 2011-04-21  

wxynxyo 写道

关于前面的代码, 我测试了下发现并不是所有的情况都对的，比如n=2, m=2的情况

public int find(int n, int m)   
    {   
        int r = 0;   
        for (int i = 2; i <= n; i++) {   
            r = (r + m) % i;   
        }   
        return r + 1;   
    }  

不知道你这个是怎么测的，难道结果不是1吗

33 楼 wxynxyo 2011-04-21  

关于前面的代码, 我测试了下发现并不是所有的情况都对的，比如n=2, m=2的情况

public int find(int n, int m)   
    {   
        int r = 0;   
        for (int i = 2; i <= n; i++) {   
            r = (r + m) % i;   
        }   
        return r + 1;   
    }  

32 楼 s929498110 2011-04-21  

 

数组的方法， 闲着没事也试试

package net.sulin.sort;

public class ASFRoundArray {

	public static void main(String[] args) {
		final int number = 20;
		final int start = 6;
		final int out = 9;
		start(number, start, out);
	}
	
	public static void start(int number, int start, int out){
		//生产数组
		int[] arrays = new int[number];
		for (int i = 0; i < arrays.length; i++)
			arrays[i] = i+1;
		//开始弹出
		int now = 1;
		int num = start; //当前人
		while(true){
			if(arrays[num-1] != 0){ //如果当前没弹出
				if(now == out){ //弹出
					System.out.println("pop：" + arrays[num-1]);
					arrays[num-1] = 0;
					now = 1;
				}
				now ++ ;
			}
			num ++ ;
			if(num > number)
				num = 1;
		}
		
	}

}

31 楼 coolcooldool 2011-04-21  

if(next == num){ 
    arr[index] = false; 
                     
    //剩下的人数减1 
    --count;

吧。。。