约瑟夫生死游戏.docVIP

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