用结构解josephus.txt

个人笔记 适合初学者 josephus小孩围圈问题 二分搜索 活动安排问题

用环链解决
#include<iostream.h>
#include<iomanip.h>
struct jose    //小孩结点
{
int code;
jose * next;
}
void main()
{
//赋初值
int numofboys,interval;
cout<<"please input the number of boys,\n"   //小孩数
    <<"      interval of counting;\n";    //数小孩个数
cin>>numofboys>>interval;
//建立小孩结构数组
jose* pjose=new jope[numofboys];   //从堆内存分配空间
jose* pcuttent=pjose;    //当前结点指针
//初始化结构数组；构成环链，小孩编号，输出编号
int itemsinline=0;  //输出项目
for(int i=1;i<=numofboys;i++)
{
pcurrent->next=pjose+i%numofboys;   //链到下一个元素
pcurrent->code=i;    //小孩编号
pcurrent=pcurrent->next;   //改变当前位置
if(itemsinline++%10==0)
cout<<<endl;
cout<<setw(4)<<i;
}      //pcurrent此时等于pjose
itemsinline=0;
jose* pivot;    //链表哨兵
pcurrent=&pjose[numofboys-1];    //下一个就是数组第一个元素pjose[0]
while(pcurrent->next!=pcurrent)   //处理未获胜的所有小孩
{
for(int j=0;j<interval;j++)    //数interval个小孩
{
pivot=pcurrent;
pcurrent=pivot->next;
}
if(itemsinline++%10==0)    //输出小孩
cout<<<endl;
cout<<sewt(4)<<pcurrent->code;
pivot->next=pcurrent->next;   //小孩脱链
pcurrent=pivot;
}
cout<<"\n\nthe winner is"
    <<pcurrent->code<<endl;     //获胜者
delete[]pjose;    //返还堆空间
}