约瑟夫环问题实验报告材料

1、实用文案约瑟夫环问题实验报告实验课题：用循环链表解决约瑟夫环的问题参与者： XX 班级：教育技术 121 班日期：2013年 10月 11日上机环境：宿舍个人电脑，硬件设施如下图所示：实验要求【实验目的】熟悉 C语言的基本编程方法， 掌握线性表的操作实现方法，培养使用线性表解决实际问题的能力。【实验内容】利用循环链表实现约瑟夫问题的求解。标准文档实用文案存储结构：循环链表约瑟夫问题如下：一、小孩报数问题有 N 个小孩围城一圈，给他们从1 开始依次编号，现指定从第W个开始报数，报到第S 个时，该小孩出列，然后从下一个小孩开始报数，仍是报到第S 个时出列，如此重复下去，直到所有的小孩都出列（总人数

2、不足S 个时将循环报数），求小孩出列的顺序。算法分析 ：用一个标准的输入输出的头文件iostream.h，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：#includestruct Nodeint data;struct Node *next;int main()int m,n;coutm;coutn;标准文档实用文案Node *first,*last;first=last=new Node;/生成第一个结点first-data=1;for(int i=2;idata=i;last-next=p;last=p;/链接结点last-next=first;in

3、t number=n;Node *pre=last;while(number1)for(int j=1;jnext;Node *p=pre-next;pre-next=p-next;coutdata ;delete p;number-;标准文档实用文案coutdata ;delete pre;输出结果如下图所示：二、 Joseph( 约瑟夫 ) 问题是非常著名的。最原始的问题是：n个人，记为1， 2，.，n，站成一圈。从第一个人开始数，数到的第 m个人将要被处死，如此反复进行，直到只剩下一个人，而这个人会获救。 比如：当 n=6，m=5，那么这些人将以5，4，6，2，3 的次序被处死，而1 就

4、获救了。假设有 k 个好人和k 个坏人围成一圈，其中1 到 k 是好人，（ k+1）到 2k 是坏人。你必须选择 m使得所有的坏人都先被处死，然后才是第一个好人； 并且要求 m最小。 #includestruct Node标准文档实用文案int data;Node *pNext;void main()int n,k,m,i;Node *p,*q,*head;coutn;coutk;coutm;head=(Node*)new Node;/确定头结点p=head;for(i=1;idata=i;p-pNext=(Node*)new Node;/为下一个新建内存p=p-pNext;标准文档实用文案p-data=n;/最后一个单独处理p-pNext=head;/指向头，形成循环链表p=head;while(p-data!=(p-pNext)-data)/p-data=(p-pNext)-data表示只剩下一个结点的while(p-data !=k)/寻找编号为 k 的结点p=p-pNext;if(m=1)for(i=1;i=n;i+)coutdatapNext ;coutn;return;else标准文档实用文案for(i=1;ipNext;/找到报 m-1 的结点q=p-pNext;/q为报 m的结点coutdatapNext)