Problem Solving►UVa

UVa 440 - Eeny Meeny Moo

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Josephus problem
(注意 城市 1 都會先被斷)

Solution

參考：https://en.wikipedia.org/wiki/Josephus_problem#The_general_case

直接用遞迴的公式去解即可。

這裡試著解釋看看，非嚴謹證明！有錯還煩請告知。

(直接用殺人代替斷網)

總共 n 人，如果從第 0 個人開始往後點第 k 個人，並殺掉他，會造成兩件事：

  1. 總人數減少 1 人
  2. 下一個起點變成是被殺掉的下一位，也就是下一次的起始位置往前移 $k\ mod\ n$

$f(n,k)$ 表示該狀況時，最後 剩下的人是誰。
初始狀態：$f(1,k) = 0$

當我們要求出 $f(n,k)$ 時先做第一件事，減少一人，而我們已經知道 $n-1$ 人時最後剩下的是 $f(n-1, k)$。
但 $f(n-1,k)$ 的起始點和現在不同，所以我們把結果做位移，也就是：

$f(n,k) = (f(n-1,k) + k)\ mod\ n$

關於起始不同，舉例來說 n = 5 (0, 1, 2, 3, 4), k = 3，第一個被殺的是 2。
下一狀態是 0, 1, 3, 4，且從 3 開始計算，也就是起點往前移了 $k\ mod\ n = 3$ 個。(0 -> 3)
可以試著列列看，如果保持 k 不變，僅移動起始點，殺人的順序會怎麼改變。

以 n = 5 來說起點為 0，順序為：
2 -> 0 -> 4 -> 1 -> (3)。
將起點改為 2，順序則變成：
0 -> 3 -> 2 -> 4 -> (1)。

可以發現接下來每個被殺的位置也都被往前移了 $k\ mod\ n = 3$。

回到題目的部分，先建好表，要注意 k 可能超過 n。
另外則是由於每次 城市 1 都會先被斷，我們直接把它排除，並將 index 從 0 開始計算。
last[n - 1][k] == 0 時就是我們要找的 k 了。

Code

UVa 440
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#define N 150
#define M 600

int main()
{    
    int last[N][M] = {};
    for (int n = 2; n < N; ++n)
        for (int k = 1; k < M; ++k)
            last[n][k] = (last[n - 1][k] + k) % n;

    int n;
    while (scanf("%d", &n) && n)
    {
        for (int i = 1; i <M; ++i)
            if (!last[n - 1][i]) //直接將第一個排除，並把 Ulm 當第一個(idx = 0)
            {
                printf("%d\n", i);
                break;
            }
    }

    return 0;
}