約瑟夫斯問題（有時也稱為約瑟夫斯置換），是一個出現在計算機科學和數學中的問題。
有n個囚犯站成一個圓圈，準備處決。首先從一個人開始，越過k − 2個人，並殺掉第k個人。接著，再越過k − 1個人，並殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。
問題是，給定了n和k，一開始要站在什麼地方才能避免被處決？
歷史起源
這個問題是以弗拉維奧·約瑟夫斯命名的，它是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。
解法
我們將明確解出k = 2時的問題。對於的情況，我們在下面給出一個一般的解法。
設f(n)為一開始有n個人時，生還者的位置。走了一圈以後，所有偶數號碼的人被殺。再走第二圈，則新的第二、第四、……個人被殺，等等；就像沒有第一圈一樣。如果一開始有偶數個人，則第二圈時位置為x的人一開始在第2x − 1個位置。因此位置為f(2n)的人開始時的位置為2f(n) − 1。這便給出了以下的遞推公式：
f(2n)=2f(n)-1
如果一開始有奇數個人，則走了一圈以後，最終是號碼為1的人被殺。於是同樣地，再走第二圈時，新的第二、第四、……個人被殺，等等。在這種情況下，位置為x的人原先位置為2x + 1。這便給出了以下的遞推公式：
f(2n+1)=2f(n)+1
如果我們把n和f(n)的值列成表，我們可以看出一個規律：
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
從中可以看出，f(n)是一個遞增的奇數數列，每當n是2的冪時，便重新從f(n) = 1開始。因此，如果我們選擇m和l，使得n = 2m + l且，那么。顯然，表格中的值滿足這個方程。我們用數學歸納法給出一個證明。
定理：如果n = 2m + l且，則f(n) = 2l + 1。
證明：對n套用強歸納法。n = 1的情況顯然成立。我們分別考慮n是偶數和n是奇數的情況。
如果n是偶數，則我們選擇l1和m1，使得，且。注意l1 = l / 2。我們有f(n) = 2f(n / 2) − 1 = 2((2l1) + 1) − 1 = 2l + 1，其中第二個等式從歸納假設推出。
如果n是奇數，則我們選擇l1和m1，使得，且。注意l1 = (l − 1) / 2。我們有f(n) = 2f((n − 1) / 2) + 1 = 2((2l1) + 1) + 1 = 2l + 1，其中第二個等式從歸納假設推出。證畢。
答案的最漂亮的形式，與n的二進制表示有關：把n的第一位移動到最後，便得到f(n)。如果n的二進制表示為，則。這可以通過把n表示為2m + 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個人視為一個步驟，然後把號碼改變。
注釋
The War of the Jews 3.387-391
參考文獻
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.
外部連結
cut-the-knot上的約瑟夫斯遊戲（Java Applet）
Eric W. Weisstein, 約瑟夫斯問題, MathWorld.
