http://gdxzleecs.blog.sohu.com/124424792.html
首先看一看最原始的約瑟夫問題：
1 約瑟夫環（Josephus）問題是由古羅馬的史學家約瑟夫（Josephus）提出的，他參加并記錄了公元66—70年猶太人反抗羅馬的起義。約瑟夫作為一個將軍，設法守住了裘達伯特城達47天之久，在城市淪陷之后，他和40名死硬的將士在附近的一個洞穴中避難。在那里，這些叛亂者表決說“要投降毋寧死”。于是，約瑟夫建議每個人輪流殺死他旁邊的人，而這個順序是由抽簽決定的。約瑟夫有預謀地抓到了最后一簽，并且，作為洞穴中的兩個幸存者之一，他說服了他原先的犧牲品一起投降了羅馬。
2 17世紀的法國數學家加斯帕在《數目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒.
3 有ｎ只猴子，按順時針方向圍成一圈選大王（編號從１到ｎ），從第１號
開始報數，一直數到ｍ，數到ｍ的猴子退出圈外，剩下的猴子再接著從1 開始報數。就這樣，
直到圈內只剩下一只猴子時，這個猴子就是猴王，編程求輸入ｎ，ｍ后，輸出最后猴王的編
號。
4 編號為1,2,3,…,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選一個正整數作為報數的上限值m，從第一個人開始按順時針方向自1開始順序報數,報到m時停止。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一人開始重新從1報數，如此下去，直到所有人全部出列為止。編程打印出列順序。
以上是典型的約瑟夫問題。約瑟夫問題的傳統解法是利用循環鏈表加以解決，這就需要從1號元素開始模擬所有元素出列的情況，附上原始的解決方法：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int code;
node * next;
};
int n,m,i,j;
int main(void)
{
node * head,* tail,* no,* p2;
no=new node;
no->code=1;
no->next=NULL;
head=tail=no;
scanf("%d%d",&n,&m);
for (i=2;i<=n;i++)
{
no=new node;
no->code=i;
no->next=NULL;
tail->next=no;
tail=no;
}
tail->next=head;
for (i=1;i<=n-1;i++)
{
j=1;
while (j<=m-1)
{
no=no->next;
j++;
}
printf("%d ",no->next->code);
p2=no->next;
no->next=no->next->next;
delete p2;
}
printf("%d\n",no->code);
system("pause");
return 0;
}
對于4 ：
#include<stdio.h>
#include<stdlib.h>
/*********
作者： 北京交通大學
循環鏈表的應用
********/
typedef struct LNode
{
int num,code;
struct LNode *next;
}LNode,*Linklist;
/*********
函數名：Josef
參數：整形n，代表人數 m代表初始的密碼
返回值：無
**********/
void Josef(int n,int m)
{
Linklist head,p,L,q;
head = (Linklist)malloc(sizeof(LNode));
p = head;
int i,j,k,temp;
int mima = m;//初始密碼
for(i=1;i<n;i++)//建立單循環鏈表 ,有頭結點
{
L = (Linklist)malloc(sizeof(LNode));
p->next = L;
p = L;
}
L->next = head;//L指向隊尾;
//L = head;
//p = head->n;
p = head;
for(i = 1;i<=n;i++)//為每一個節點輸入密碼和號數
{
printf("請為節點%d輸入密碼：",i);
scanf("%d",&j);
p->num = i;
p->code= j;
p = p->next;
}
int count = 0; //count來尋找刪除的節點的前一個節點
p = L; //從尾指針 開始查找，來防止初始密碼為1時可能帶來的指針溢出問題
while(p->next!=p)
{
while(count<mima-1)
{
p = p->next;
count++;
}
mima = p->next->code;
printf("%d ",p->next->num);
p->next = p->next->next;
count = 0;
}
printf("%d",p->num);
}
main()
{
int n,m;
printf("請輸入人數：");
scanf("%d",&n);
printf("請輸入初始密碼：");
scanf("%d",&m);
Josef(n,m);
getchar();
}
以上時間復雜度高達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等于一百萬，一千萬的情況不是問題了?？梢?，適當地運用數學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執行效率。
在此基礎上再看看POJ 2244這個問題：
問題描述：http://acm.pku.edu.cn/JudgeOnline/problem?id=2244
這個問題對約瑟夫問題有點變形： 已知最后的元素 為 2 ，n 從輸入中給出，求出最小的m
其實這個用一種比較笨的辦法就是 m 從1開始一個一個試，找到第一個（n ，m），使得最后出列的元素序號為2 的 m 即為解。
求最后出列元素的方法由上面給出，這里所作的優化就是求約瑟夫的優化，至于遍歷求m的優化可以考慮打表。
這個題目還有一點要注意的就是 ： 它第一個打印的元素始終是1，從2開始為約瑟夫問題，這樣可以把2看做是1，n看為n-1的約瑟夫問題。
一下是源代碼：
#include<stdio.h>
#include<stdlib.h>
int josef(int n,int m)
{
int s = 0;
for(int i = 2;i<=n-1;i++)
s = (s+m)%i;
return s+1+1;
}
int main()
{
int n;
int m;
scanf("%d",&n);
while(n)
{
for(m=1;;)
{
if(josef(n,m)==2)
break;
m++;
}
printf("%d\n",m);
scanf("%d",&n);
}
return 0;
}