數字圍一個圈，依次去掉下一個，最後剩下什麼？

12-07

數字1到1000按照逆時針順序排一個圈，從最小的數字開始，仍存在的數字依次把右邊的數字去掉。例如1去掉2，3去掉4，...999去掉1000。下一輪1去掉3，5去掉7。注意1可能被去掉，例如要是999還存在就去掉1。以此類推，最終剩下的數字是？

正如前一個答案所說，此題其實是約瑟夫斯問題的一個最小特例，維基百科裡就有詳細解釋和證明了（英文版更詳細）。不過我猜一看公式就頭暈的人應該不少，那麼這裡就給出一個通俗還帶圖的講解。

首先我們拿個不算很大的數字出來，就用11吧，圍成一圈隔一個去掉一個，最後剩下的是7。

懷疑的話可以自己算算看。懶得算？我做了個小演示工具，進去試試。（瀏覽器要支持HTML5）

把左上角的總數改成11，點「開始」。

嗯，總之我們的結果是7，這個毋庸置疑。
接下來就能直接推算出12個數字時剩下的是哪個，不用再從頭算一遍了。

原理十分簡單：

先把12個數字排成一圈，從1開始，去掉右邊的2：

現在剩下的就是11個數字了吧。

那麼它和原本只有11個數字的時候相比，有什麼區別呢？

唯一區別就是，下一步要跳過3，去掉右邊的4；而原本只有11個數字時，去掉的是1右邊的2。

對比一下：

換句話說，12個數字只要經過了第一步之後，剩下的11個和原本就是11個數字的情況相比，只是順時針旋轉了兩個數字而已，除了編號之外就沒有什麼區別了。

11個數字時最後剩下的是7，那麼順時針旋轉兩個就是9。
也就是說，12個數字中最後剩下的是9。
同理可算出13個數字剩下的是11；14個數字是13；15個數字是15。

且慢，現在都剩到15了，再增加的話會怎樣呢？

當然是轉過一圈繼續了：16個數字時，在上一步的15基礎上再順時針轉兩位，最後剩的是1。

一直以此類推下去，就能算出所有數字的結果了。

從1開始，每個數字對應的最終生還者如下表：

1 ：1
2-3 ：1 3
4-7 ：1 3 5 7
8-15 ：1 3 5 7 9 11 13 15
16-31 ：1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
32-....：1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39...

可以看出，每行的個數翻倍，然後回到1重新開始。

根據上述結論歸納出計算方法。
設總數為 $n$ ，最終剩下的數字為 $f(n)$ ，則函數公式為：
$f(n)=2(n-2^{floor(log_{2}n)})+1$
其中floor指的是向下取整函數，而 $2^{floor(log_{2}n)}$ 則是比n小的、最大的2的冪值。

用這個公式可以算出，當一共有1000個數字時，最終剩下的是977。

有時間的話不妨在演示工具上測一下，不測也沒關係，結果長這樣：

勤奮好學的你可能會想，如果間隔的不是一個，而是兩個三個乃至多個，是不是也有這麼方便的計算公式呢？
遺憾的是，約瑟夫斯問題在間隔超過1時不存在通用的簡單公式，只能逐個遞推。
原理仍然和我們最早由11推出12時所用的方法一致：如果每隔k個數字去掉一個，那麼我們知道n的結果後，就能推出n+1時的結果。在n的基礎上順時針旋轉k+1個位置，轉過一圈的話就從頭開始。
也就是 $f(n+1)=(f(n)+k+1) modn$ （其中mod n指的是對n取餘數）

你可以驗證一下，把演示工具的總數和間隔數隨便改改，勾選「連續運行」，讓它自己跑去吧。下面會記錄下一大串結果，看看是不是符合這個公式。

約瑟夫環當步長為1的時候。請看這裡約瑟夫斯問題

這是非常著名的約瑟夫環問題，在《具體數學》這本書第一章中有詳細的推導過程…

這道題是碼農常見的面試題之一…