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

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

吧。。。

 

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

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

}

关于前面的代码, 我测试了下发现并不是所有的情况都对的，比如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吗

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

　　　　　　　　　 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-

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


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

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

#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;
}

纯数组

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