约瑟夫环算法设计

约瑟夫环算法设计 实验一 基于约瑟夫环问题的算法设计 --计科一班钟祯穆20100810127 一、问题描述 设编号为1-n的n(n>0)个人按顺时针方向围成一圈(首先第1个人从1开始顺时针报数(报m的人(m 为正整数)(令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。 二、需求分析 1、需要基于线性表的基本操作来实现约瑟夫问题 、需要利用顺序表来实现线性表 2 3、测试用例 输入:10，3 6 9 2 7 1 8 5 10 4 输出:3 三、概要设计 抽象数据类型 为实现上述程序的功能，应以整型(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<<"请输入总人数及出列编号"<>n>>m; int *listarray=new int[n]; //将这n个人存入数组 int *outarray=new int[n]; //存放依此出列的人的编号 for(int i=0;i