白駿11866ジョセフス解題0(JAVA)

12116 ワード
白駿 11866 Java ジャワ ジョセフス問題0 テキストリンク
質問リンク

質問する


ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

入力


第1行NとKは、スペースを隔てて順次与えられる.(1 ≤ K ≤ N ≤ 1,000)

しゅつりょく


例に示すように、ジョセフスシーケンスを出力します.

に答える


キューで解題すればいいのですが、特別にArrayListに入れてそのままpivotを回したいです.
CYCLEのような大きなピボットを回転させ、ピボットに対応する数を抽出します.

ソースコード

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
       
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> group = new ArrayList<Integer>();
        ArrayList<Integer> answer = new ArrayList<Integer>();
        int pivot = 0;
        int numberOfMember = Integer.parseInt(st.nextToken());
        
        final int CYCLE = Integer.parseInt(st.nextToken());
        
        for(int i=0;i<numberOfMember;i++) {
            group.add(i+1);
        }
        
        while(group.size()!=0) {
            for(int i=0;i<CYCLE-1;i++) {
                if(pivot==numberOfMember) {
                    pivot = 0;
                }
                pivot++;
                
            }
            if(pivot==numberOfMember) {
                    pivot = 0;
            }
            answer.add(group.remove(pivot));
            numberOfMember--;

        }
        bw.write("<");
        for(int i=0;i<answer.size()-1;i++) {
            bw.write(answer.get(i)+", ");
        }
        bw.write(answer.get(answer.size()-1)+">\n");
      
        bw.flush();
	br.close();
	bw.close();
        
        
    }
    
}
boot2docker のコマンドを確認する
百俊カップ麺(1781)