约瑟夫生死游戏.doc

约瑟夫生死游戏一、约瑟夫生死游戏30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置将是被扔下大海的位置。二、实验目的 n个人围成一个圈由第一个人数起，依次报数，数到第x个人，便把他剔除，然后再从他的下一个人数起，数到第x个人，再将他剔除,依次继续，直到剩下的人数小于等于n/2。三、功能分析1、构建约瑟夫链表：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点；2、确定n的值：进而使链具化体，从而可以构建一个具体的链表；3、更新链表：对剔除结点后的链表进行重新连接，构成一个新的链表，使得循环继续进行；4、输入：输入n的值进行链表具体化，输入间隔值m，使得间隔被确定，程序得以有效正确的进行；5、输出：输出要剔除的结点的数值。四、系统设计1、 利用类定义构造成员函数以及成员templateclass Listpublic:List()first=new LinkNode;first-link=first;List(T x)first=new LinkNode(x);first-link=first;List(List&L);List()void Insert(int i,T x);T getHead()return first-data; LinkNode* getfirst()return first;void xiuf(LinkNode* a)first=a;LinkNode*Locate(int i); protected:LinkNode*first;2、 定义成员函数templateList:List(List&L)T value;LinkNode*srcptr=L.getHead();LinkNode*destptr=first=new LinkNode;destptr-data=srcptr-data;while(srcptr-link!=first) value=srcptr-link-data;destptr-link=new LinkNode(value);destptr=destptr-link;srcptr=srcptr-link;last=srcptr;templateLinkNode* List:Locate(int i)if(i0)return NULL;LinkNode* current=first;int k=1;while(klink;k+;if(current=first)return NULL;return current;3、 创建含有n个结点的单循环链表队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。从上述分析可见，不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。templatevoid List:Insert(int i,T x)LinkNode* current=Locate(i);if(current=NULL)return;LinkNode*newNode=new LinkNode(x);if(newNode=NULL)cout存储分配错误!link=current-link;current-link=newNode;4、 Josephu操作Josphu链表链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列直到所有人都出出列为止。给出出列的顺序。templatevoid Josephus(List& Js,int n,int m)LinkNode *p=Js.Locate(1),*pre;int i,j;for(i=1;i=n/2;i+)if(m=1)cout出列的人是:datalink; Js.xiuf(p-link);delete p;p=pre;else for(j=1;jlink; cout出列的人是datalink=p-link; if(p=Js.getfirst()Js.xiuf(p-link); /if(p=Js.getlast()Js.movelast(pre); delete p; p=pre-link;5、 主函数void main() List clist(1); int i,n,m; cout输入游戏者的人数和报数间隔：nm; for(i=1;in;i+) clist.Insert(i,i+1); Josephus(clist,n,m); 五、程序流程开始进入程序，先确定n的值，然后，根据n得知建立链表，然后数数，确定输出的位置，输出数，更新链表，如果剩下的数小于等于n/2,则停止程序，否则继续计数进行循环直至结束程序。六、程序运行图输入人数30和间隔9运行结果也可以输入人数40间隔10六、完整程序代码#includeusing namespace std;templatestruct LinkNodeT data; LinkNode*link;LinkNode( T item) data=item;link=NULL;templateclass Listpublic:List()first=new LinkNode;first-link=first;List(T x)first=new LinkNode(x);first-link=first;List(List&L);List()void Insert(int i,T x);T getHead()return first-data; LinkNode* getfirst()return first;void xiuf(LinkNode* a)first=a;LinkNode*Locate(int i);protected:LinkNode*first;templateList:List(List&L)T value;LinkNode*srcptr=L.getHead();LinkNode*destptr=first=new LinkNode;destptr-data=srcptr-data;while(srcptr-link!=first)value=srcptr-link-data;destptr-link=new LinkNode(value);destptr=destptr-link;srcptr=srcptr-link;last=srcptr;templateLinkNode* List:Locate(int i)if(i0)return NULL;LinkNode* current=first;int k=1;while(klink;k+;if(current=first)return NULL;return current;templatevoid List:Insert(int i,T x)LinkNode* current=Locate(i);if(current=NULL)return;LinkNode*newNode=new LinkNode(x);if(newNode=NULL)cout存储分配错误!link=current-link;current-link=newNode;templatevoid Josephus(List& Js,int n,int m)LinkNode *p=Js.Locate(1),*pre;int i,j;for(i=1;i=n/2;i+) if(m=1)cout出列的人是:datalink; Js.xiuf(p-link);delete p;p=pre;else for(j=1;jlink; cout出列的人是datalink=p-link; if(p=Js.getfirst()Js.xiuf