已经经历过两次考试中都遇到了约瑟夫环问题，就问题本身而言并不难，主要是在理解问题上经常由于题干较短，没有理解清楚意思从而导致无法解题。
问题描述：
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。
历史背景：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。（百度百科）
思路
1.建立链表解决问题
2.通过递归解决问题
建立链表的方法：
1.链表结构
struct Node
{
int data;
Node * next;
};
struct LinkedList
{
Node *pHead;
Node *pTail;
int len;
};
2.建立节点
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;
}3.建立链表
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;//按顺序编码，初始化的节点为0，所以从1开始编码
p->next = node;上一个节点指向新建的节点
p=p->next;//指向当前结点的前进改为指向下一个节点，否则就是在一个节点上重复操作
head->len++;//增加长度
}
head->pTail = p;//修改尾节点
p->next = head->pHead;
}
return head;
}
}4.删除节点
void RemoveNode(LinkedList*head,Node *deleNode)
{
Node* p = head->pHead;
cout<<deleNode->data<<endl;
if(p!=NULL){
if(head->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;
}
}//挺好理解的，如果不懂可以去翻一下严蔚敏的数据结构,以上实现了链表的基本操作5.实现约瑟夫环
int Joseph(int m,int k)//m代表有多少人，n代表每喊到多少时退出
{
if(m<=0||k<=0)//无意义
{
cout<<"error:input"<<endl;
return -1;
}
LinkedList* list = CreateLinkedList(m);//初始化链表
Node * p = list->pHead;
for(int i=1;i<=k;i++)
{
if(list->len ==2)
{
cout<<p->data<<endl;
cout<<"answer is :"<<endl;
return p->next->data;
}
if(i==k)
{
RemoveNode(list,p);
i = 1;
}
p=p->next;
}
return 0;
}6.主函数
int main()
{
cout<<"Print output queue"<<endl;
cout<<Joseph(20,3)<<endl;
//getchar();
return 0;
}7.测试
总代码：
#include<iostream>
#include<malloc.h>
using namespace std;
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;//按顺序编码，初始化的节点为0，所以从1开始编码
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<<deleNode->data<<endl;
if(p!=NULL){
if(head->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)//m代表有多少人，k代表每喊到多少时退出
{
if(m<=0||k<=0)//无意义
{
cout<<"error:input"<<endl;
return -1;
}
LinkedList* list = CreateLinkedList(m);//初始化链表
Node * p = list->pHead;
for(int i=1;i<=k;i++)
{
if(list->len ==2)
{
cout<<p->data<<endl;
cout<<"answer is :"<<endl;
return p->next->data;
}
if(i==k)
{
RemoveNode(list,p);
i = 1;
}
p=p->next;
}
return 0;
}
int main()
{
cout<<"Print output queue "<<endl;
cout<<Joseph(20,3)<<endl;
//getchar();
return 0;
}
通过递归解决问题
呃呃呃…
推导的递推公式可以理解，但是具体怎么推导出来的还不清楚，的确有时候“怎么想到的“是一个比较玄学也看数学功底的事情，也欢迎知道的将方法说出来，分享知识。下面粘出公式：
Joseph(n,k) = (Joseph(n-1,k)+k) % n （n>1）;
#include<iostream>
#include<malloc.h>
using namespace std;
int Joseph(int m,int k)
{
if(m<=0||k<=0)
{
cout<<"error!"<<endl;
return -1;
}else
{
if(m==1)
{
return 0;
}
else
{
return ((Joseph(m-1,k)+k)%m);
}
}
}
int main()
{
cout<<"Print "<<endl;
cout<<Joseph(20,3)<<endl;
system("pause");
return 0;
}
粘出参考的一篇博文，十分感谢博主的总结，我对博主的文章加了部分注释和自己的理解。但是值得指出的是原博主的代码在链表法中存在着问题，例如Joseph（20，3），用迭代法可以得出正确答案为19，但是链表法得出的答案是12，这主要是因为在处理只剩下两个数字的情况时出了错误，显而易见，只剩两个数字时，若喊得是偶数退出，则必定是第二个退出留下第一个，若喊得是奇数退出，则必定是第一个退出留下第二个，我对此处代码进行了改进，总结进了总代码中。
截图
