摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

我們將明確解出k = 2時的問題。對於的情況，我們在下面給出一個一般的解法。

設f(n)為一開始有n個人時，生還者的位置。走了一圈以後，所有偶數號碼的人被殺。再走第二圈，則新的第二、第四、……個人被殺，等等；就像沒有第一圈一樣。如果一開始有偶數個人，則第二圈時位置為x的人一開始在第2x − 1個位置。因此位置為f(2n)的人開始時的位置為2f(n) − 1。這便給出了以下的遞推公式：

如果一開始有奇數個人，則走了一圈以後，最終是號碼為1的人被殺。於是同樣地，再走第二圈時，新的第二、第四、……個人被殺，等等。在這種情況下，位置為x的人原先位置為2x + 1。這便給出了以下的遞推公式：

如果我們把n和f(n)的值列成表，我們可以看出一個規律：

從中可以看出，f(n)是一個遞增的奇數數列，每當n是2的冪時，便重新從f(n) = 1開始。因此，如果我們選擇m和l，使得n = 2^m + l且，那麼。顯然，表格中的值滿足這個方程。我們用數學歸納法給出一個證明。

定理：如果n = 2^m + l且，則f(n) = 2l + 1。

證明：對n應用強歸納法。n = 1的情況顯然成立。我們分別考慮n是偶數和n是奇數的情況。

如果n是偶數，則我們選擇l₁和m₁，使得，且。注意l₁ = l / 2。我們有f(n) = 2f(n / 2) − 1 = 2((2l₁) + 1) − 1 = 2l + 1，其中第二個等式從歸納假設推出。

如果n是奇數，則我們選擇l₁和m₁，使得，且。注意l₁ = (l − 1) / 2。我們有f(n) = 2f((n − 1) / 2) + 1 = 2((2l₁) + 1) + 1 = 2l + 1，其中第二個等式從歸納假設推出。證畢。

答案的最漂亮的形式，與n的二進位表示有關：把n的第一位移動到最後，便得到f(n)。如果n的二進位表示為，則。這可以通過把n表示為2^m + l來證明。

在一般情況下，這個問題的最簡單的解決方法是使用動態規劃。利用這種方法，我們可以得到以下的遞推公式：

f(n,k) = (f(n − 1,k) + k)mod n，f(1,k) = 0

如果考慮生還者的號碼從n - 1到n是怎樣變化的，則這個公式是明顯的。這種方法的運行時間是O(n)，但對於較小的k和較大的n，有另外一種方法，這種方法也用到了動態規劃，但運行時間為O(klogn)。它是基於把殺掉第k、2k、……、2個人視為一個步驟，然後把號碼改變。