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

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

  
搓搓的弄了一个链表。。。 代码确实多啊
  

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

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

纯数组     46 楼    Simon.C    2011-04-22              哈哈，又见数据结构了
关于题目，有点不明：报到M,意思是说M出列后又从1开始报？    47 楼    sunlightcs    2011-04-22              Simon.C 写道哈哈，又见数据结构了
关于题目，有点不明：报到M,意思是说M出列后又从1开始报？
是这个意思了。    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--;
   }
}    49 楼    jkxydp    2011-09-27              代码行数太多，逻辑太啰嗦，递归就简单多了。