题目

有 N 个小朋友站成一个圆圈。他们沿顺时针编号依次是 1 ~ N。从编号是 1 的小朋友开始报数（1，2，3，…）报到 K 的小朋友出列。他顺时针方向的下一个小朋友继续从 1 开始报数。报到 K 的人再出列 …
这个游戏一直进行下去，直到队伍里只剩下一个小朋友。
求剩下的这个小朋友原来的编号是多少？
（参看下面的示意图）

当 N = 10，K = 3 时， 所求的编号为： 4。我们记为：
10,3 --> 4
类似还有：
20,5 --> 7
100,13 --> 70
3,5 --> 1
如果 N 比较小，怎么处理都无大碍。
当 N 很大时，就要考虑算法的效率问题了。
比如：
123456789,123 --> ???

分析

对于 N，K 较小的情况，可以直接采用模拟的办法。
弄一个动态数组，元素装的是小朋友的编号。
弄一个指针 p，指向准备从 1 开始报数的那个人。
已知 p，K，数组的长度，很容易求出下一个将要出列的人的位置。
将该位置的元素从数组中删除。
再重复游戏，直到数组中只有一个元素。
这个“笨办法”很可靠，不容易写错。一定要代码实现一下。

接下来就要考虑更高效的算法了。
假设我们已经把整个游戏过程录像。
现在把镜头推到最后。队列中只剩下一个人。
并用，如果游戏还要玩，那下一个要报数的人就是他自己。
把录像倒着回放一小段。
看到一个人，从队外插入的队列里了。
他的编号无所谓。
重要的是，你能算出他插入的位置和最后剩下的那个人的关系吗？
注意，逻辑上，队列是环形的，无所谓谁是头，谁是尾。
还有，能算出这两个人中，谁开始报 1 的吗？
好。再把镜头往回放，又一个人插进来。
…

代码

先来个笨算法的。

// problem002
import java.util.*;
public class A
{
	static int f(int n, int k){
		List<Integer> lst = new ArrayList();
		for(int i=1; i<=n; i++){
			lst.add(i);
		}
		
		int p = 0;
		while(lst.size()>1){
			p = (p+k-1) % lst.size();
			lst.remove(p);
		}
		
		return lst.get(0);
	}
	
	static void show(int n, int k){
		System.out.println(n + "," + k + " --> " + f(n,k));
	}
	
	public static void main(String[] args){
		show(10,3);
		show(20,5);
		show(100,13);
	}
}

再看看更神奇的方案
要不说：数学是科学之母呢。

//problem002
import java.util.*;
public class B
{
	static int f(int n, int k){
		int r = 0;
		for(int i=2; i<=n; i++){
			r = (r + k) % i;
		}
		
		return r + 1;
	}
	
	static void show(int n, int k){
		System.out.println(n + "," + k + " --> " + f(n,k));
	}
	
	public static void main(String[] args){
		show(10,3);
		show(20,5);
		show(100,13);
		show(123456789,123);
	}	
}

代码写出来简单得想跳楼，但需要仔细想想。
再想想…
实在不行就看我在千聊上的详解吧。
还是先想想好。思考是快乐的源泉。

详解

实在想不清楚，就在“千聊”中搜这个题目吧。
或用下面的邀请卡。