[Java] UVa 151 Power Crisis

題目連結

題意:
能源危機，各個地區要輪流限電
給定 N ，代表有 1~N 個地區
每次都從 1 開始
求最小正整數 m
使得重複每 m 個地區斷電後
最後一個斷電的是地區 13

超過 N 後再從 1 開始
已經斷電的則跳過

例如:
N = 13，m = 1
斷電順序 : 1, 2, ..., 13

若 N = 14, m = 2
斷電順序 : 1, 3, 5, 7, 9, 11, 13, ...
斷到 13 後下一個預計是 2
也就是 13 並不是最後斷電
2 就不是答案

解法:
暴力模擬即可
如果 N 限定過大可能就行不通

題目要求最小的 m
就從 1 開始代入
每次從 1 開始，每 m 個一數
數到 13 就看是不是最後一個

m 可能超過 N，例如 N = 14, m = 18
目前不確定該取多少
不過 N 只介於 13 ~ 100
保險一點倒是可以先測測看
(N 代 13~100 最大的 m 為多少)

此外
這題其實是一個特殊題型
叫做 約瑟夫問題
了解的人可以直接套用公式求解
詳情可以參考: 約瑟夫問題（Josephus Problem）

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N, m, count;
	int k[] = new int[100];
	while (sc.hasNext()) {
	N = sc.nextInt();
	if (N == 0)
	break;
	for (m = 1; m < 500; m++) {
	boolean OK = true;
	for (int q = 1; q < 100; q++)
	k[q] = 0;
	int j = 1;
	count = 0;
	k[1] = 1;
	while (true) {
	j++;
	if (j > N) //over N
	j -= N;
	if (k[j] == 0) {
	count++;
	if (count == m) {
	k[j] = 1;
	count = 0;
	}
	}
	if (k[13] == 1)
	break;
	}
	for (int i = 1; i <= N; i++) {
	if (k[i] == 0) {
	OK = false;
	break;
	}
	}
	if (OK) {
	System.out.printf("%d\n", m);
	break;
	}
	}
	}
	}
	}

view raw UVa151.java hosted with ❤ by GitHub