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

《约瑟夫环问题实验报告材料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、时，该小孩出列，然后从下一个小孩开始报数，仍是报到第S个时出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。算法分析：用一个标准的输入输出的头文件iostream.h，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型： #includestructNode{intdata;structNode*next;};intmain(){intm,n;cout<<"请输入m的值";cin>>m;cout<<"请输入n的值";cin>>n;标准

3、文档实用文案Node*first,*last;first=last=newNode;//生成第一个结点first->data=1;for(inti=2;idata=i;last->next=p;last=p;//链接结点}last->next=first;intnumber=n;Node*pre=last;while(number>1){for(intj=1;jnext;Node*p=pre->next;pre->next=p->next;c

4、out<data<<"";deletep;number--;}标准文档实用文案cout<data<<"";deletepre;}输出结果如下图所示：二、Joseph(约瑟夫)问题是非常著名的。最原始的问题是：n个人，记为1，2，...，n，站成一圈。从第一个人开始数，数到的第m个人将要被处死，如此反复进行，直到只剩下一个人，而这个人会获救。比如：当n=6，m=5，那么这些人将以5，4，6，2，3的次序被处死，而1就获救了。假设有k个好人和k个坏人围成一圈，其中1到k是好人，（k+1）到2k是坏人。你必须选择m

5、使得所有的坏人都先被处死，然后才是第一个好人；并且要求m最小。#includestructNode{标准文档实用文案intdata;Node*pNext;};voidmain(){intn,k,m,i;Node*p,*q,*head;cout<<"输入n的值:";cin>>n;cout<<"输入起始报数人号码k的值:";cin>>k;cout<<"输入数到m出列的m的值:";cin>>m;head=(Node*)newNode;//确定头结点p=head;for(i=1;i<=n-1;i++)//赋初值{

6、p->data=i;p->pNext=(Node*)newNode;//为下一个新建内存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++){cout<data<

7、<'t';p=p->pNext;}cout<<'';return;}elsefor(i=1;ipNext;}//找到报m-1的结点q=p->pNext;//q为报m的结点cout<data<<"t";//输出报m的结点的值k=(q->pNext)->data;//k为下一个报数的起点p->pNext=q->pNext;//删除报m的结点}cout<data<<'';//输出最后一个结点的值}输出结果如下图所示：标准文档