Josephus问题:n个小孩围成一圈,从某个小孩开始,顺时针方向从1开始数小孩,每数到第interval个小孩时,该小孩便离开圈子。再从1开始数小孩,这样小孩不断离开,圈子不断缩小,最后剩下的小孩是胜利者,求胜利者是哪个小孩?
#include <iostream>
using namespace std;
struct cjose
{
int data;
cjose* next, *front;
};
typedef cjose* list;
list tour(list l)//找到链表最后一位
{
list p=l->next;
while(p!=0)
{
p=p->next;
}
return p;
}
void creat(list *p, int n)//创建双向链表
{
(*p)=new cjose;
(*p)->next=NULL;
(*p)->front=NULL;
list s;
for(; n>0; n--)
{
s=new cjose;
s->data=n;
s->next=(*p)->next;
(*p)->next->front=s;
s->front=(*p);
(*p)->next=s;
}
s=tour(*p);
s->next=(*p)->next;//跳过头节点,让尾节点和初始节点相连
(*p)->next->front=s;
}
void destroy(list *l)
{
list p, q=(*l);
while(q!=0)
{
p=q->next;
delete q;
q=p;
}
*l=NULL;
}
void cut(list *p, int interval, int beginpos, int n)//本题主干
{
list b=(*p)+beginpos;
for(; n-1>0; n--)
{
for(int i=0; i<interval; i++)
{
b=b->next;
}
b->front->front->next=b;
cout<<b->front->data<<" ";
delete b->front;
}
}
int main()
{
int n, interval, beginpos;
list p;
cout<<"输入小孩个数,开始位置,数数间隔: "<<endl;
cin>>n>>beginpos>>interval;
creat(&p, n);
cout<<"The remove boys are: ";
cut(&p, interval, beginpos, n);
cout<<"The Winner is: "<<p->next->data;
destroy(&p);
system("pause");
}
josephus的链表实现.exe 中的 0x00db15dc 处有未经处理的异常: 0xC0000005: 写入位置 0x00000008 时发生访问冲突