约瑟夫环算法设计.doc_第1页
约瑟夫环算法设计.doc_第2页
约瑟夫环算法设计.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

实验一 基于约瑟夫环问题的算法设计 -计科一班钟祯穆20100810127一、问题描述设编号为1-n的n(n0)个人按顺时针方向围成一圈首先第1个人从1开始顺时针报数报m的人(m 为正整数)令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。二、需求分析1、需要基于线性表的基本操作来实现约瑟夫问题2、需要利用顺序表来实现线性表3、测试用例输入：10，3输出：3 6 9 2 7 1 8 5 10 4三、概要设计抽象数据类型为实现上述程序的功能，应以整型（int）数据存储用户的输入，以及输出的结果。算法的基本思想利用数组来模拟一个环，然后模拟报号出圈的过程让数组元素循环报数，当报数编号和用户所输入的出列编号相同时，则输出此数，重复此过程，直到所有人都出列。程序由三个模块组成：（1） 输入模块：完成两个整数的输入，存入变量n和m中。（2） 计算模块：循环计算出这n个数的输出序列（3） 输出模块：按序列输出这n个数。四、详细设计物理数据类型 队列元素以及出列序列皆以整型数组方式存储算法的具体步骤（1） 给输入输出序列元素编号（2） 开始循环访问数组元素（3） 从第一个元素开始报数，当报数编号与出列编号相同时即让该数输出。（4） 将下一个元素置1，即又重新从1开始报数，重复此循环过程，直至所有数输出。算法的时间复杂度程序中循环语句为单程循环，无嵌套，时间复杂度为O（n）输入和输出的格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列 输出格式2：将这n个数的输出序列写入到文件中五、运行结果六、源代码(此程序在DevC+上运行) /*求解约瑟夫环问题*/ #include using namespace std;int main()int m,n,k,i,j; /n表示总人数，m是出列编号 cout请输入总人数及出列编号nm; int *listarray=new intn; /将这n个人存入数组int *outarray=new intn; /存放依此出列的人的编号for(int i=0;in;i+) listarrayi=i+1; /对这n个人进行编号/*开始循环报数，并输出出列元素*/for(i=1,j=k=0;kn;j=+j%n) /i为报数编号，初始值为1，循环访问数组元素，即数组元素循环报数，k为出列元素序号if(listarrayj!=0)if(i=m) /若报数编号和出列编号相同outarrayk=listarrayj;/则将该元素放置到出列数组，并输出coutoutarrayk ;k+;listarrayj=0;/将出列元素置0 i=1; /将i置1，用以
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论