有n个人，按顺序围成一圈，从第1个开始报数，第m个出列，直至所有人都出列

问题：有n个人，按顺序围成一圈，从第1个开始报数，第m个出列，直至所有人都出列。

 

1、设计思路

1）

使用集合存放n个值；

循环n次 {

  每次获取第m个，并删除第m个

}

 

1.1）循环n次

通过for循环n次，或者通过while语句遍历集合至空为止

 

1.2）每次获取第m个，并删除第m个

循环查找，每次循环计数1，当计数值count==m时，获取值并删除相应元素；

进入下一轮查找直到结束。

 

由于m可能大于n，一次循环不一定满足要求，所以需要用到递归算法。

 

2、代码实现

import java.util.ArrayList;
import java.util.List;

public class DeleteCyclicData1 {
	
	/** 原始数据 */
	private List<Integer> list;
	
	/**
	 * 开始执行
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void exec(int n, int m) {
		initData(n);
		deleteElements(n, m);
	}
	
	/**
	 * 初始化数据
	 *
	 * @param n
	 * @return void
	 */
	public void initData(int n) {
		list = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
	}

	/**
	 * 逐个删除并输出元素
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void deleteElements(int n, int m) {
		System.out.print(String.format("\nn=%s, m=%s, results：", n, m));
		for (int i = 1; i <= n; i++) {
			System.out.print(deleteElement(m, 0) + " ");
		}
	}
	
	/**
	 * 开始执行
	 *
	 * @param n
	 * @param m
	 * @return int 返回本次删除的元素
	 */
	public int deleteElement(int m, int count) {
		for (int i = 0; i < list.size(); i++) {
			if (++count == m) {
				return list.remove(i);
			}
		}
		return deleteElement(m, count);
	}
	
	public static void main(String[] args) {
		DeleteCyclicData1 obj = new DeleteCyclicData1();
		obj.exec(5, 2);
		obj.exec(5, 3);
		obj.exec(5, 6);
		obj.exec(5, 12);
	}

}

 

import java.util.ArrayList;
import java.util.List;

public class DeleteCyclicData2 {
	
	/** 原始数据 */
	private List<Integer> list;
	
	/**
	 * 开始执行
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void exec(int n, int m) {
		initData(n);
		deleteElements(n, m);
	}
	
	/**
	 * 初始化数据
	 *
	 * @param n
	 * @return void
	 */
	public void initData(int n) {
		list = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
	}

	/**
	 * 逐个删除并输出元素
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void deleteElements(int n, int m) {
		System.out.print(String.format("\nn=%s, m=%s, results：", n, m));
		while (list.size() > 0) {
			System.out.print(deleteElement(m, 0) + " ");
		}
	}
	
	/**
	 * 开始执行
	 *
	 * @param n
	 * @param m
	 * @return int 返回本次删除的元素
	 */
	public int deleteElement(int m, int count) {
		for (int i = 0; i < list.size(); i++) {
			if (++count == m) {
				return list.remove(i);
			}
		}
		return deleteElement(m, count);
	}
	
	public static void main(String[] args) {
		DeleteCyclicData2 obj = new DeleteCyclicData2();
		obj.exec(5, 2);
		obj.exec(5, 3);
		obj.exec(5, 6);
		obj.exec(5, 12);
	}

}

 

以上是看到这个问题的第一个思路，但总感觉这样递归似乎比较麻烦。

假设m<=n，那么其实只需要直接从集合中获取第m个值即可；

如果m>n，那么m对n取余的余数可以重复使用以上规则；

但是，有一种特殊情况，当m>n，且m能够被n整除的时候，此时余数为0，这种情况不能直接使用余数获取相应值，而应该获取集合的最后一个元素。

于是，代码如下：

import java.util.ArrayList;
import java.util.List;

public class DeleteCyclicData3 {
	
	/** 原始数据 */
	private List<Integer> list;
	
	/**
	 * 开始执行
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void exec(int n, int m) {
		initData(n);
		deleteElements(n, m);
	}
	
	/**
	 * 初始化数据
	 *
	 * @param n
	 * @return void
	 */
	public void initData(int n) {
		list = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
	}

	/**
	 * 逐个删除并输出元素
	 *
	 * @param n
	 * @param m
	 * @return void
	 */
	public void deleteElements(int n, int m) {
		System.out.print(String.format("\nn=%s, m=%s, results：", n, m));
		while (list.size() > 0) {
			int remainder = m % list.size();
			System.out.print(list.remove(remainder == 0 ? list.size() - 1 : remainder - 1) + " ");
		}
	}
	
	public static void main(String[] args) {
		DeleteCyclicData3 obj = new DeleteCyclicData3();
		obj.exec(5, 2);
		obj.exec(5, 3);
		obj.exec(5, 6);
		obj.exec(5, 12);
	}

}

 

运行结果：

 

n=5, m=2, results：2 3 4 5 1 
n=5, m=3, results：3 4 5 1 2 
n=5, m=6, results：1 3 5 4 2 
n=5, m=12, results：2 5 4 3 1 

 

 

事实上，第1种思路比较简单，易于理解。第2种思路虽然代码简洁一点，但反而容易出错。

 

（转载请注明来源：http://zhanjia.iteye.com/admin/blogs/2028617）