约瑟夫问题

刺骨的言语ヽ痛彻心扉 2022-09-19 13:29 179阅读 0赞

**约瑟夫问题**

**作者：Ackarlix**

这是一个非常经典的问题：n个骑士编号1，2，...，n，围坐在圆桌旁，编号为k的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1开始报数，找出最后留在圆桌旁的骑士编号。

这个问题可以用没有头结点的循环链表解决，数据域存放骑士的编号，出列的骑士，删除其对应的结点，最后剩下的那个结点就是问题所求的骑士编号。程序如下：

\#define OK 1  
\#define ERROR 0  
\#include <iostream.h>  
\#include <malloc.h>

int N; //骑士总数

typedef int Status;

// 定义循环链表  
typedef struct LNode\{  
int data;  
LNode \*next;  
\}LNode,\*LinkList;

// 构造空循环链表  
Status InitList(LinkList &L)\{  
L=(LinkList)malloc(sizeof(LNode));  
L->next=L;  
return OK;  
\}

// 第i个位置之前插入元素e  
Status ListInsert(LinkList &L,int i,int e)\{  
if(i<1) return ERROR; //插入位置不合理  
int j=0;  
LinkList p=L,s;  
while(j<i-1)\{ //寻找第i-1个结点  
p=p->next;  
j++;  
\}  
s=(LinkList)malloc(sizeof(LNode)); //生成新结点,插入L中  
s->data=e;  
s->next=p->next;  
p->next=s;  
return OK;  
\}

// 删除结点s  
Status ListDelete(LinkList &L,LinkList &s)\{  
LinkList p=L;  
while((p->next)!=s)\{ //寻找结点s  
p=p->next;  
\}  
p->next=s->next; //删除结点s  
if(s==L) L=s->next;  
free(s);  
return OK;  
\}

// 初始化循环链表  
Status PutList(LinkList &L)\{  
int i;  
L->data=1;  
for (i=2;i<=N ; i++)\{  
ListInsert(L,i-1,i);  
\}  
return OK;  
\}

// 取第i个结点的地址,赋给结点s  
Status GetElem(LinkList L,int i,LinkList &s)\{  
if(i<1) return ERROR; //位置不合理  
int j=1;  
LinkList p;  
p=L;  
while(j<i)\{ //寻找第i个结点  
p=p->next;  
j++;  
\}  
s=p;  
return OK;  
\}

// 数i个结点，删除最后数的结点,返回后面结点的地址  
Status ElemCount(LinkList &L,int i,LinkList &s)\{  
LinkList p=s;  
while(i!=1)\{ //数i个结点  
p=p->next;  
i--;  
\}  
s=p->next; //结点s返回后面结点的地址  
cout<<p->data<<' ';  
ListDelete(L,p); //删除最后数的结点  
return OK;  
\}

//Josephus 问题  
void Josephus(int k,int m)\{  
int total=N;  
LinkList L,s;  
InitList(L);  
PutList(L);  
GetElem(L,k,s);  
while(total!=1)\{ //直到只剩一人，循环结束  
ElemCount(L,m,s);  
total--;  
\}  
cout<<endl<<"留下的骑士是"<<L->data<<endl;  
\}

// 主函数  
void main()\{  
int k,m;  
char flag='y';  
while(flag=='y')\{  
cout<<"输入骑士个数,开始数的位置,每次数的人数:";  
cin>>N>>k>>m;  
cout<<"骑士离开的顺序为:";  
Josephus(k,m);  
cout<<"你想再试一次吗(按y继续): ";  
cin>>flag;  
cout<<endl;  
\}  
cout<<"程序结束."<<endl;  
\}

输出结果为（红色为键盘输入的数据）：

输入骑士个数,开始数的位置,每次数的人数:13 1 3  
骑士离开的顺序为:3 6 9 12 2 7 11 4 10 5 1 8  
留下的骑士是13  
你想再试一次吗(按y继续): y

输入骑士个数,开始数的位置,每次数的人数:10 2 2  
骑士离开的顺序为:3 5 7 9 1 4 8 2 10  
留下的骑士是6  
你想再试一次吗(按y继续): n

程序结束.