POJ-2746:ジョセフ問題(Java版)

問題の説明:
テーマの要求は、ここではもう出しません.n匹のサルがいて、時計回りに囲んで大王(番号1からn)を選び、1番から数え、mまで数え、mまで数えたサルは圏外に出て、残りのサルは1から数え始める.こうして、圏内にサルが1匹しか残っていないまで、このサルはサル王であり、n,mをプログラミングして入力した後、最後のサル王の番号を出力する.(2746:ジョセフ問題)
構想分析:
この問題をやりたいのは、実はどのように循環して数えるか考えないでください.ループで解くと、このループがネストされるのは面倒なことです.私は循環ネストが面倒だとは言っていませんが、この問題は循環ネストに適していません.肝心なのは誰がネストしているのか、そして循環が終わった場所はどこですか.すべて問題です.だから、この時、私たちは考えを変えて問題を考えなければなりません.私たちが今やっていることはただの循環報数です.サルにサイクルを与えますか?forサイクルですか?問題の中の「輪」の字を見ると、この問題は必ず循環に使うことがわかりますが、肝心なのは循環がどのように使うかの問題です.サイクルにはもう一つの表現方法が考えられます.それはサイクルです.実は周期性こそ私たちがこの問題を解決する鍵です.
私たちは2つの周期を使う必要があります.1つはサルで、これは明らかです.もう一つは新聞数の配列で、周期でなければなりません.周期的でなければ、私たちのサルは最初のサルを脱退する時に止まるだけで、それから無限に過程(死の循環)を待っています.
コード解析:
2サイクルの表示は次のとおりです.

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

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

もう一つは,この問題がforループでは不適切であることであり,forループの2番目のパラメータがあまり定まらないためである.ホワイトを使ったほうがいいです.
下付きのキーコードは次のとおりです.

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));
		}
        
    }

}