問題描述：

? ? 題目要求，這里就不再給出了。大致描述如下：有ｎ只猴子，按順時針方向圍成一圈選大王（編號從１到ｎ），從第１號開始報數(shù)，一直數(shù)到ｍ，數(shù)到ｍ的猴子退出圈外，剩下的猴子再接著從1開始報數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時，這個猴子就是猴王，編程求輸入ｎ，ｍ后，輸出最后猴王的編號。（2746:約瑟夫問題）

思路分析：

? ? 想做這題，其實是不要想著怎么去循環(huán)來報數(shù)。要知道，你要是用循環(huán)來解，這個循環(huán)嵌套是一件很麻煩的事。我不是說循環(huán)嵌套麻煩，只是這一題不適合用循環(huán)嵌套，關(guān)鍵是誰嵌套誰，還有就是循環(huán)結(jié)束的地方在哪里？都是問題。所以，這個時候，我們得換一個思路還想問題。我們現(xiàn)在在做的事情只是一循環(huán)報數(shù)。那要給猴子一個循環(huán)嗎？是用for循環(huán)嗎？看到題中的“圈”字就知道這一題肯定是要用到循環(huán)，可是關(guān)鍵是循環(huán)怎么用的問題。我們可以想到的是，循環(huán)還有一個表示方法，那就是周期！其實周期性才是我們解決這一題的關(guān)鍵所在。

我們需要用到兩個周期，一個是猴子的，這個比較明顯。還有一個是報數(shù)的數(shù)組，它也得是一個周期。如果不是周期的，那我們的猴子就只會在退出第一個的時候就停止了，然后就是一個無盡地等待過程（死循環(huán)）。

代碼分析：

兩個周期的表示如下：

indexOfM = (indexOfM + 1 + m) % m;index = (index + 1 + n) % n;

還有一點就是這一題用for 循環(huán)是不合適的，原因是for循環(huán)的第二個參數(shù)不太好定。不如用while來得痛快。

得到下標(biāo)的關(guān)鍵代碼如下：

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只猴數(shù)到mif(indexOfM == 0) {isExit[index] = true;}}index = (index + 1 + n) % n;}index = getindexOfKing(isExit);return (index + 1);}

+1的原因是因為我們代碼中的下標(biāo)是從0開始的，而現(xiàn)實中報數(shù)的下標(biāo)是從1開始的。

完整代碼展示：

---------------------------------------完 整 程 序 代 碼---------------------------------------------

import java.util.Scanner;public class Main {/*** 得到猴王的下標(biāo)* @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;}}/*** 初始化數(shù)組* @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;}/*** 獲得猴王的下標(biāo)* @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只猴數(shù)到mif(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));}}}

總結(jié)

以上是生活随笔為你收集整理的POJ-2746:约瑟夫问题（Java版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。