ロジカルシンキング問題 -ヨセフスの問題

この問題はこのURLを翻訳したものです。

問題 - ヨセフスの問題

1番からN番までN人が丸を作りながら座っています。この時、正の整数M（≤N）が与えられます。これから順序によってM番目の人がサークルから抜けます。一人が抜けると、残りの人々でサークルを作ります。このプロセスは、N人の人がすべて抜けるまで継続します。サークルの人々が抜ける順序を（N、M） - ヨセフス順列といいます。たとえば（7、3） -ヨセフス順列は<3、6、2、7、5、1、4>になります。

NとMが与えられれば（N、M） - ヨセフス順列を求めるプログラムを作成してください。

例
入力：7 3
出力：<3, 6, 2, 7, 5, 1, 4>

この問題はDequeueを使って解くことができます

前回にStackとQueueを扱ってみました。Dequeueはその

Stackとキューを合わせたものです。

イメージをみればご理解いただけると思いますが

StackのようにFrontからデータを出すことも、

QueueのようにRear（Back）からデータを出すこともできます。

この構造はデータの位置の切り替えが多いだめ、

パフォーマンスに影響を与えることがあります。

このため、注意を持って使う必要がある構造です。

下は答案です。

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class algo {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> deque = new ArrayDeque<Integer>();
        StringBuilder sb = new StringBuilder("<");
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++) {
            deque.add(i);
        }
        while (!deque.isEmpty()) {
            for (int i = 0; i < m - 1; i++) {
                deque.addLast(deque.removeFirst());
            }
            sb.append(deque.removeFirst() + ", ");
        }
        System.out.println(sb.toString().substring(0, sb.length() - 2) + ">");
    }
}

JavaのDequeを使う場合、比較的簡単にコードを作ることができます。

前のことを除いて、後ろに移動させる構造です。

あるいは、この問題は割り算で解くこともできます。

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class algo {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<Integer>();

        StringBuilder sb = new StringBuilder("<");
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken()) - 1;

        for(int i=1;i<=n;i++) {
            list.add(i);
        }

        int index = 0;

        while(!list.isEmpty()) {
            index += m;

            if (index >= list.size()) {
                index %= list.size();
            }

            sb.append(list.remove(index) + ", ");
        }
        System.out.println(sb.toString().substring(0, sb.length()-2) + ">");
    }
}

この方式はListから使った数字は除いて、移動する位置は割り算を使い得る方式です。

例の７と２を入れて答案をだす過程を手書きで書いてみました。

四角形のところが取り出してセーブしたデータです。

思い通りの順番になることが確認できます。

Author Description