之前就知道約瑟夫問題是模擬，今天我才發現一些約瑟夫問題可使用數學解法得出！真是強悍啊！約瑟夫問題真是博大精深！固然報數長度不定的應該只有模擬了吧，能用數學作的都是簡化過的約瑟夫問題。算法
下面整理以下：編程
1.問題描述：n我的（編號1~n)，從1開始報數，報到m的退出，剩下的人繼續從1開始報數。按順序輸出列者編號。數學解法複雜度：O(n)。數組
下面的代碼摘自雨中飛燕博客，這個公式推的太牛了，我還沒看懂。。。函數
#include <stdio.h>優化
#include <conio.h>遞歸
int main( void )遊戲
{get
int n, i = 0, m, p;博客
scanf("%d%d", &n, &m); //n總人數，m步長數學
while( ++i <= n )
{
p = i * m;
while (p > n)
p = p - n + (p - n - 1)/(m - 1);
printf("%d/n", p);
}
getch();return 0;
}
2.問題描述：n我的（編號1~n)，從1開始報數，報到m的退出，剩下的人繼續從1開始報數。求勝利者的編號。數學解法複雜度：O(n)。
多重轉載，做者不明，但寫得至關好。。。
不管是用鏈表實現仍是用數組實現都有一個共同點：要模擬整個遊戲過程，不只程序寫起來比 較煩，並且時間複雜度高達O(nm)，當n，m很是大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短期內出結果的。咱們注意到原問題僅僅是要求出最 後的勝利者的序號，而不是要讀者模擬整個過程。所以若是要追求效率，就要打破常規，實施一點數學策略。
爲了討論方便，先把問題稍微改變一下，並不影響原意：
問題描述：n我的（編號0~(n-1))，從0開始報數，報到(m-1)的退出，剩下的人繼續從0開始報數。求勝利者的編號。
咱們知道第一我的(編號必定是m%n-1) 出列以後，剩下的n-1我的組成了一個新的約瑟夫環（以編號爲k=m%n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
而且從k開始報0。
如今咱們把他們的編號作一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換後就完徹底全成爲了(n-1)我的報數的子問題，假如咱們知道這個子問題的解：例如x是最終的勝利者，那麼根據上面這個表把這個x變回去不恰好就是n我的狀況的解嗎？！！變回去的公式很簡單，相信你們均可以推出來：x'=(x+k)%n
如何知道(n-1)我的報數的問題的解？對，只要知道(n-2)我的的解就好了。(n-2)我的的解呢？固然是先求(n-3)的狀況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f[i]表示i我的玩遊戲報m退出最後勝利者的編號，最後的結果天然是f[n]
遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了這個公式，咱們要作的就是從1-n順序算出f[i]的數值，最後結果是f[n]。由於實際生活中編號老是從1開始，咱們輸出f[n]+1
因爲是逐級遞推，不須要保存每一個f[i]，程序也是異常簡單：
#include <stdio.h>
int main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d/n", s+1);
}
這個算法的時間複雜度爲O(n)，相對於模擬算法已經有了很大的提升。算n，m等於一百萬，一千萬的狀況不是問題了。
3.問題描述：n我的（編號1~n)，從1開始報數，報到m(m<<n)的退出，剩下的人繼續從1開始報數。求勝利者的編號。數學解法優化後複雜度：O(m)。
一樣摘自互聯網，貌似是一篇論文，做者不明。。。
上面的算法相比最初的模擬算法效率已經大大提高了，那麼，該算法還有改進的餘地麼？
事實上，若是咱們觀察上述算法中的變量s，他的初始值爲第一個出圈人的編號，但在循環的過程當中，咱們會發現它經常處在一種等差遞增的狀態，我來看這個式 子：s=(s+m)%i;，能夠看出，當i比較大而s+m-1比較小的時候，s就處於一種等差遞增的狀態，這個等差遞增的過程並非必須的，能夠跳過。
咱們設一中間變量x，列出以下等式：
s+m*x–1=i+x
解出x，令s=s+m*x，將i+x直接賦值給 i，這樣就跳過了中間共x重的循環，從而節省了等差遞增的時間開銷。但是其中求出來的x＋i可能會超過n，這樣的結果事實上已經告訴咱們此時能夠直接結束算法了。
整個算法的C語言描述以下：
long Josephus(long n,long m,long k) //分別爲：人數，出圈步長，起使報數位置,
{
if (m == 1)k = k == 1 ? n : (k + n - 1) % n;
else
{
for (long i = 1; i <= n; i++)
{
if ((k + m) < i)
{
x = (i - k + 1) / (m - 1) - 1;
if (i + x < n)
{
i = i + x;
k = (k + m * x);
}
else
{
k = k + m * (n - i) ;
i = n;
}
}
k = (k + m - 1) % i + 1;
}
}
return k; //返回最後一人的位置
}
該算法的算法複雜度在m<n時已經與一個圈中的人數n沒有關係了，即便在n=2000000000，m=3，s=1的狀況下，也只作了54次循環，事 實上，大多數的狀況都是m<n，且m相對來講很小，此時，這個算法的複雜度僅爲O(m)；但當m>=n時，用方程求出的值不能減小循環重數，算法複雜度仍爲O(n)。
4.問題描述：n我的（編號1~n)，從1開始報數，報到2的退出，剩下的人繼續從1開始報數。求勝利者的編號。數學解法優化後複雜度：O(log n)
詳見 Donald E. Knuth的《具體數學》 中相關部分的討論，至關精彩。（點擊這裏）
這時候有更簡單的遞歸公式：
J(1) = 1;
J(2n) = 2J(n) − 1,當 n ≥ 1;
J(2n + 1) = 2J(n) + 1,當 n ≥ 1;
進而能夠推出：
J(2^m+ l) = 2l + 1,當 m ≥ 0且0 ≤ l < 2 m.
(注意若是2^m≤ n < 2^m+1，那麼餘下的數l = n − 2^m知足不等式0 ≤ l <2^(m+1)− 2^m = 2^m。)
看公式蠻頭疼的，其實就是找到大於N的最小的2的X次方（記爲M），
而後 2N-M+1就是結果，這樣編程應該很簡單了吧？
下面來自另外一份轉載，原做者不詳
若是繼續推下去能夠獲得：
x = 2*n + 1 - (2*n+1-2*k)*2^log2((2*n)/(2*n+1-2*k))
其中，log2((2*n)/(2*n+1-2*k))爲計算(2*n)/(2*n+1-2*k)以2爲底的對數，
結果向下取整數。
聯繫2^log2((2*n)/(2*n+1-2*k))總體，能夠理解爲將(2*n)/(2*n+1-2*k)向下
舍取到2的冪。有些地方把這中運算稱爲地板函數，咱們定義爲flp2，下面是
C語言的實現：
unsigned flp2(unsigned x)
{
unsigned y;
do { y = x; x &= x-1; }while(x);
return y;
}
其中x &= x-1;語句是每次把x二進制最右邊的1修改成0，直到最左邊的1爲止.
這種方法也能夠用來計算x二進制中1的數目，當x二進制中1的數目比較小的
時候算法的效率很高。
m爲2的代碼實現:
unsigned josephus2k(unsigned n, unsigned k)
{
unsiged t = (n<<1) - (k<<1) + 1;
return (n<<1)+1 - t*flp2((n<<1)/t);
}