//ReadCirLinkList_L.cpp
//To Read The Joseph Number
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include <malloc.h>
#define m 20
typedef struct CirLNode
{ int data;
struct CirLNode *next;
}CirLNode,*CirLinkList;
void CreateCirList_L(CirLinkList &L,int n) //CreateList_L() function
{ //To Creatre a LinkList L with HeadNode
int i;
CirLNode *p;
CirLNode *q;
L=(CirLinkList)malloc(sizeof(CirLNode));
L->next=NULL;
cout<<"Please input the data for LinkList Nodes: <eg. 3,1,7,2,4,8,4......>"<<endl;
for(i=n;i>0;--i)
{
p=(CirLinkList)malloc(sizeof(CirLNode));
q=(CirLinkList)malloc(sizeof(CirLNode));
cin>>p->data;
p->next=L->next;
q->next=p;
L->next=p;
}//end of for
if(n) cout<<"Success to Create a LinkList !"<<endl<<endl;
else cout<<"A NULL LinkList have been created !"<<endl;
}//end of CreateList() function
void ReadJosephList_L(CirLinkList &L,int n,int m)
{
CirLNode *p,*q;
int i,j,k=1;
int l[m];
p=L;
q=NULL;
j=1;
do
{
while(j<m+1)
{
++j;
q=p;
p = p->next;
}
l[k] = p->data;
p->next=q->next;
free(q);
p=q->next;
j=1;
k++;
}
while(p->next!=p);
l[k] = p->data;
cout<< "The Joseph Number is:"<<endl;
for(i=1;i<k+1;i++)
cout<<l[i]<<endl;
cout<<endl;
}
void main()
{
CirLinkList L;
CirLNode *p;
int m,j,n;
int CirLListNodeNum;
cout << "Read Joseph number.cpp"<<endl<<"======================"<<endl<<endl;
cout << "Please input the CirLinkListNodeNum:<eg.n>";
cin >> CirLListNodeNum;
cout <<endl<< "The CirLinklist to be< eg. 3,1,7,2,4,8,4......>"<<endl;
CreateCirList_L(L,CirLListNodeNum);
cin>>m;
if(m<=20)
{
ReadJosephList_L(L,n,m);
}
else
cout<<"It is error"<<endl;
}
约瑟夫问题的求解,红色部分为什么在编译的时侯有错误呢?
(约瑟夫问题:编序为1,2,...n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数),一开始人选一个整数作为报数上限m,从第一个人开始按顺时针方向从自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始从1报数,如此下去,知道所有人全部出列为止,设计一个程序求出出列顺序.
采用单循环链表模拟此程序,按照出列的顺序印出各人的编号
测试数据:m的初值为20;n=7,7个人的密码依次为3,1,7,2,4,8,4.首先m的值为6(正确的出列顺序为6,1,4,7,2,3,5))