《算法》第四版 1.3.37 Josephus问题

1.3.37 Josephus问题

题目:

Josephus问题。在这个古老的问题中, N个身陷绝境的人一致同意通过以下的方式减少生存人数。他们围坐成一圈(位置记为0到N-1)并从第一个人开始报数, 报到M的人会被杀死, 直到最后一个人留下来。传说中Josephus找到了不会被杀死的位置。编写一个Queue的用例Josephus, 从命令行接受N和M并打印出人们被杀死的顺序(这也将显示Josephus在圈中的位置)。

输入:

$ java Josephus 7 2

输出:

1 3 5 0 4 2 6

思路:

交换不断交换两个队列, 直到所有元素出栈为止

import java.util.Scanner;
public class Josephus {
  public static void main(String[] args) {
    Scanner read = new Scanner(System.in);
    int N = read.nextInt();
    int M = read.nextInt();
    Queue<Integer> q1 = new Queue<Integer>();
    Queue<Integer> q2 = new Queue<Integer>();
    // Queue<Integer> q_ans = new Queue<Integer>();  // 直接打印储存
    for (int i = 0; i < N; i++) { q1.enqueue(i);}
    int num = 1, cnt = 0;
    while (cnt != N) {
      if (!q1.isEmpty()) {
        if (num != M) { q2.enqueue(q1.dequeue()); num++; }   // q1队首出队, 进q2队
        else {
          System.out.print(q1.dequeue() + " ");
          num = 1; cnt++;
        }
      } else {
        if (num != M) { q1.enqueue(q2.dequeue()); num++; }   // q1队首出队, 进q2队
        else {
          System.out.print(q2.dequeue() + " ");
          num = 1; cnt++;
        }
      }
    }
    System.out.println();
  }
}

改进:

但看了书中给出的解答之后, 大为吃惊, 他竟然在头部出列,同时, 在尾部入列

public class Josephus {
  public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
	int M = Integer.parseInt(args[1]);
	Queue<int> queue = new Queue<int> ();
	for (int i = 0; i < N; i++) { queue.enqueue(i); }
	while (!queue.isEmpty()) {
	  for (int i = 0; i < m-1; i++) {
	    queue.enqueue(queue.dequeue());   // 出列 同时 进列
	  }
	  System.out.print(queue.dequeue() + " ");
	}
	System.out.println();
  }
}

Output:

$ java Josephus 7 2
1 3 5 0 4 2 6

队列头进尾出的策略, 你理解了多少？