在线等急

Question

有编号从1到N的N个人坐成一圈报数，报到M的人出局，下一位再从1开始，如此持续，直止剩下一位为止，报告此人的编号X。输入N,M，求出X。

Answer 1

import java.util.*;/*
 * Created on Mar 21, 2006
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 *//**
 * @author YongDongLiang
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Recursion1 {
private List men=null;
private int n;
private int m;
Recursion1(int n,int m){
this.n = n;
this.m = m;
men = new ArrayList();
for(int i=0;i<n;i++){
men.add(new Integer(i));
}
}
void getLastMan(){
System.out.println("size:"+men);
if(men.size()==1)return;
System.out.println("remove No."+m%men.size());
men.remove((m-1)%men.size()); //因为从第0开始
getLastMan();
}

void prt(){
getLastMan();
System.out.println("The last man is:"+men.get(0));
}

public static void main(String[] args){
new Recursion1(6,5).prt(); }
}

Answer 2

先前有点错
import java.util.*;/*
 * Created on Mar 21, 2006
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 *//**
 * @author YongDongLiang
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Recursion1 {
private List men=null;
private int n;
private int m;
Recursion1(int n,int m){
this.n = n;
this.m = m;
men = new ArrayList();
for(int i=1;i<=n;i++){
men.add(new Integer(i)); //从1开始
}
}
void getLastMan(){
System.out.println("size:"+men+" *="+men.size());
if(men.size()==1) return;

int i = 0;
if(m%men.size()==0) i = men.size()-1;
else i = m%men.size()-1;

System.out.println("remove No."+i);
men.remove(i); //因为从第0开始
getLastMan();
}

void prt(){
getLastMan();
System.out.println("The last man is:"+men.get(0));
}

public static void main(String[] args){
new Recursion1(6,5).prt(); }
}

Answer 3

String person[]=new String[N]; //定义N个人
int M,X;  //定义M,X
Vector v=new Vector();
for(int i=0;i<person.length;i++){
v.add(persion[i]);
}
while(v.size()>1){ int k=M%v.size(); //第几个人报到M
if(k==0) k=v.size(); 
k--; //数组下标比实际数小1
v.remove(k);

}String p=(String)v.get(0); //经过循环后集合v只有一个人；for(int i=0;i<person.length;i++){ //这个人再比对数组中的人，是哪一个，x
if(p.equal(persion[i])){
X=i+1;
}
}

Answer 4

用LinkedList效率比较高吧。我写的：public class Circle {
public static final int N = 100;
public static final int M = 50;
private static LinkedList nums = new LinkedList();
static {
for(int i = 0; i < N; i++)
nums.add(new Integer(i+1));
}
public static void main(String[] args) {
System.out.println("N = " + N + ", M = " + M + ", " + (Integer)(remove(nums).get(0)) + " is left.");
}
public static LinkedList remove(LinkedList nums) {
int len = nums.size();
if(len == 1) return nums;
else {
nums.remove((M - 1) % len);
nums.add(nums.remove(0));
return (remove(nums));
}
}
}输出：
N = 100, M = 50, 31 is left.关键思路：
1. 用M-1和链表的长度求模来决定要移除的无素的位置
2. 移除元素后，移除第一个元素并添加到最后一个元素的后面欢迎大家评批指正！