问题描述：
题目要求，这里就不再给出了。大致描述如下：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。（2746:约瑟夫问题）
思路分析：
想做这题，其实是不要想着怎么去循环来报数。要知道，你要是用循环来解，这个循环嵌套是一件很麻烦的事。我不是说循环嵌套麻烦，只是这一题不适合用循环嵌套，关键是谁嵌套谁，还有就是循环结束的地方在哪里？都是问题。所以，这个时候，我们得换一个思路还想问题。我们现在在做的事情只是一循环报数。那要给猴子一个循环吗？是用for循环吗？看到题中的“圈”字就知道这一题肯定是要用到循环，可是关键是循环怎么用的问题。我们可以想到的是，循环还有一个表示方法，那就是周期！其实周期性才是我们解决这一题的关键所在。
我们需要用到两个周期，一个是猴子的，这个比较明显。还有一个是报数的数组，它也得是一个周期。如果不是周期的，那我们的猴子就只会在退出第一个的时候就停止了，然后就是一个无尽地等待过程（死循环）。
代码分析：
两个周期的表示如下：
indexOfM = (indexOfM + 1 + m) % m; index = (index + 1 + n) % n;
还有一点就是这一题用for 循环是不合适的，原因是for循环的第二个参数不太好定。不如用while来得痛快。
得到下标的关键代码如下：
private static int getIndexOfKing(int n, int m) {
int index = 0;
boolean[] isExit = initBoolean(n);
int indexOfM = 0;
while (!gotKing(isExit)) {
// 如果第i只猴没有退出
if(!isExit[index]) {
indexOfM = (indexOfM + 1 + m) % m;
// 如果第i只猴数到m
if(indexOfM == 0) {
isExit[index] = true;
}
}
index = (index + 1 + n) % n;
}
index = getindexOfKing(isExit);
return (index + 1);
}
+1的原因是因为我们代码中的下标是从0开始的，而现实中报数的下标是从1开始的。
完整代码展示：
---------------------------------------完 整 程 序 代 码---------------------------------------------
import java.util.Scanner;
public class Main {
/**
* 得到猴王的下标
* @param isExit
* @return
*/
private static int getindexOfKing(boolean[] isExit) {
int index = -1;
for (int i = 0; i < isExit.length; i++) {
if(isExit[i] == false) {
index = i;
break;
}
}
return index;
}
/**
* 是否选出了猴王
* @param isExit
* @return
*/
private static boolean gotKing(boolean[] isExit) {
int count = isExit.length;
for (int i = 0; i < isExit.length; i++) {
if(isExit[i] == true) {
count--;
}
}
if(count == 1) {
return true;
}else {
return false;
}
}
/**
* 初始化数组
* @param n
* @return
*/
private static boolean[] initBoolean(int n) {
boolean[] exit = new boolean[n];
for (int i = 0; i < n; i++) {
exit[i] = false;
}
return exit;
}
/**
* 获得猴王的下标
* @param n
* @param m
* @return
*/
private static int getIndexOfKing(int n, int m) {
int index = 0;
boolean[] isExit = initBoolean(n);
int indexOfM = 0;
while (!gotKing(isExit)) {
// 如果第i只猴没有退出
if(!isExit[index]) {
indexOfM = (indexOfM + 1 + m) % m;
// 如果第i只猴数到m
if(indexOfM == 0) {
isExit[index] = true;
}
}
index = (index + 1 + n) % n;
}
index = getindexOfKing(isExit);
return (index + 1);
}
public static void main(String[] args) {
int n;
int m;
Scanner input = new Scanner(System.in);
while (true) {
n = input.nextInt();
m = input.nextInt();
if((n == 0) && (m == 0)) {
break;
}
System.out.println("" + getIndexOfKing(n, m));
}
}
}