问题描述：

已知n个人（以编号0，2，3…n-1分别表示）围坐在一起。从编号为0的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，最后一个出列的人为胜利者。求胜利者编号.

---

历史背景：

Wikipedia: 这个问题是以弗拉维奥·约瑟夫斯命名的，它是1世纪的一名犹太历史学家。

他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。

他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。

约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个.

问题分析：解决该问题有两种思路，第一种：通过建立循环链表来模拟这个过程

第二种：通过递归方式（数学归纳将问题转化为数学问题）

由于递归方式，代码更简洁，下面首先以递归方式来解决问题

——————递归实现：

例如 对 m= 10,k=3

0　　1　　2　　3　　4　　5　　6　　7　　8　　9　　(*)

0　　1　　3　　4　　5　　6　　7　　8　　9 　  (* 循环下去)

转化为：　　　　　　　3　　4　　5　　6　　7　　8　　9　　0　　1　　(* 循环下去）

　　　　　　　　　　　 0　　1　　2　　3　　4　　5　　6　　7　　8

m=10,k=3 去掉一个元素之后，变成了一个m=9,k=3的约瑟夫环问题

并且有如下关系

3 = (0+3)%10   4 = （1+3）%10 　　… 0 = (3+7)%10

即 3 = (0+k)% m    4 =  (1+k) % m       … 0  = (3+k) % m

m =10,k =3 设约瑟夫环最后一个出列的人为 Joseph(10,3),那么存在如下关系

Joseph(10,3) = (Joseph(9,3)+k) %m;

…

Joseph(n,k) = (Joseph(n-1,k)+k) % n （n>1）;

C++实现如下：

递归方法一：

1 int Joseph(int m,int k)
2 {
3 if(m<=0||k<=0)
4 {
5 cout<<"error!"<<endl;
6 return -1;
7 }else
8 {
9 if(m==1)
10 {
11 return 0;
12 }else
13 {
14 return ((Joseph(m-1,k)+k)%m);
15 }
16 }
17 }

递归方法二：如果输出整个出队的顺序

int Joseph(int m,int k,int i)
{
if(m<=0||k<=0||m<i)
{
cout<<"error"<<endl;
return -1;

}else  
{  
    if(i==1)  
    {  
        return (m+k-1)%m;  
    }else  
    {  
        return ((Joseph(m-1,k,i-1)+k)%m);  
    }  
}  

}

程序运行结果如下：

int main()
{
cout<<"递归方法一"<<endl;
cout << Joseph(6,3) << endl;
cout<<"递归方法二"<<endl;
for(int i=1;i<=6;i++)
{
cout<<Joseph(6,3,i)<<endl;
}
getchar();
return 0;
}

结果：

——————循环链表实现：

建立节点数据结构：循环链表

struct Node
{
int data;
Node * next;
};

struct LinkedList
{
Node *pHead;
Node *pTail;
int len;
};

建立循环链表

//建立个节点
Node * GetNode(int i)
{
Node * p = (Node *)malloc(sizeof(Node));
if(p!=NULL&&i>=0)
{
p->data = i;
p->next = NULL;
return p;

}else  
{

    cout<<"error"<<endl;  
    exit(-1);  
    return NULL;  
}  

}

//建立链表
LinkedList* CreateLinkedList(int i)
{
Node* node = GetNode(0);
LinkedList *head = (LinkedList*)malloc(sizeof(LinkedList));
if(head == NULL)
{
cout<<"CreateLinkedList:memory error"<<endl;
exit(-1);
return NULL;
}
if(i<=0)
{
cout<<"CreateLinkedList: error"<<endl;
exit(-1);
return NULL;
}

head->pHead = node;  
head->pTail = node;  
head->len = 1;  
if(i==1)  
{  
    node->next = node;  
}else  
{  
    Node \*p = head->pHead;  
    for(int j=1;j<=i-1;j++)  
    {  
        Node\* node = GetNode(j);  
        node->data = j;  
        p->next = node;  
        p=p->next;  
        head->len++;  
    }  
    head->pTail = p;  
    p->next = head->pHead;  
}  
return head;

}

删除节点：

//删除节点
void RemoveNode(LinkedList*head,Node *deleNode)
{
Node* p = head->pHead;
cout<data<len>1){
do
{
if(p->data==deleNode->data)
{
if(p==head->pHead)
{
head->pHead = p->next;
}
if(p==head->pTail)
{
head->pTail = p->next;
}
p->data = p->next->data;
p->next = p->next->next;
head->len--;
return;

            }else{  
                p=p->next;  
            }  
        }while(p!=head->pHead);  
    }else  
    {  
        cout<<"error";  
        exit(-1);  
        return;  
    }  
}else  
{  
    return;  
}  

}

约瑟夫模拟：

int Joseph(int m,int k)
{
if(m<=0||k<=0) { cout<<"error:input"<pHead;

for(int i=1;i<=k;i++)  
{  
    if(list->len ==1)  
    {  
        return p->data;  
    }  
    if(i==k)  
    {  
        RemoveNode(list,p);  
        i = 1;  
    }  
    p=p->next;  
}  
return 0;

}

程序运行结果如下：

int _tmain(int argc, _TCHAR* argv[])
{

cout<<"循环列表"<<endl;  
cout<<Joseph(6,3)<<endl;  
getchar();  
return 0;  

}