约瑟夫环实验报告

约瑟夫环实验 姓名:杨维 班级:物联网工程0901班 学号:20090810229 实验一 约瑟夫环问题 一、 背景 约瑟夫问题，Josephus Problem，据说著名犹太历史学家 Josephus有过以下的故事: 在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人到,于是决定了一个自杀方式,41个人排成一个圆 圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报 数,直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从,Josephus 要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了 这场死亡游戏。 原题: 用户输入M,N值,N个人围成一个环,从0号人开始数, 数到M,那个人就退出游戏,直到最后一个人 求最后一个剩下的人是几号？ 二、 问题描述 设编号为1-n的n(n>0)个人按某顺序向围成一圈,首先第1个人从1开始顺时针报数,报 m的人(m 为正整数),令其出列。然后再从他的下一个人开始,重新从1顺时针报数, 报m的人,再令其出列。如此下去,直到圈中所有人出列为止。求出列编号序列。 三、 需求分析 1、 用户从界面输入两个整数n,m; 2、 n代表参加者的总数,m表示出列间隔数 3、 利用数组线性表实现 4、 测试数据例子 输入: 请输入n,m:10 3 输出: 出列的顺序:3 6 9 2 7 1 8 5 10 4 四、 概要设计 由于参加者是人,故先定义一个结构Person Struct Person{ Int id;//记录该人的编号 } 由于参加者排成了一个序列,故而使用线性表实现。 ADT List 操作对象:Person 基本操作 List();//构造空表 ~List();//撤销表 Void Add(Elem k);//向表尾处插入元素K Void Delete(int index);//删除下标为index的元素 Int GetTai();//返回剩余人数 Void show();//打印成员编号 算法基本思想: 从下标为0的开始计数为1,以后接着的每个人在前一个人计数加1,且每计数到3 的人退出然后后面的元素依次向前移动1,下一个人从新从1开始,如此直到下表最 大的人,如果此时人还没出完,从下标为0的接着计数,直到所有人退出为止。 流程图: 开始 Count= 1 i=0 isize=size; //为表大小赋值 tail=0; //表尾下标为0 Boy=new Person[size];//为表开辟空间 } 向表尾添加元素b void List::Add(Person b){ Boy[tail].id=b.id;//将b的id赋给表尾Boy tail++; //表尾下标加一 } 删除表中元素: void List::Delete(int index){ cout< struct Person{ int id; }; class List{ public: List(int size);//构造size大小的空线性表 ~List(){delete Boy;}//撤销线性表 void Add(Person b);//向表尾加入元素b void Delete(int index);//删除表中下标为index的元素 void show();//打印线性表的信息 int GetTail(){return tail;}//返回线性表位置 private: int tail;//表尾 int size;//表大小 Person *Boy;//表中元素 }; List::List(int size){ this->size=size; //为表大小赋值 tail=0; //表尾下标为0 Boy=new Person[size];//为表开辟空间 } void List::Add(Person b){ Boy[tail].id=b.id;//将b的id赋给表尾Boy tail++; //表尾下标加一 } void List::Delete(int index){ cout<>n>>m; List L(n); int i; cout<<"开始时的队列:"; for(i=0;i