2010年10月28日星期四1数据结构:第一次实验讲解数据结构:第一次实验讲解Data Structure主讲教师：骆嘉伟主讲教师：骆嘉伟Office number: 计通院606计通院606E-mail: luojiawei@约瑟夫问题（Josephus Problem）约瑟夫问题（Josephus Problem）?据说著名犹太历史学家 Josephus有过以下的故事：据说著名犹太历史学家 Josephus有过以下的故事：?在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋 友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到， 于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个 重新报数，直到所有人都自杀身亡为止 然而Josephus 和 他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他 将朋友与自己安排在第16个与第31个位置，于是逃过了这场 死亡游戏原题： 用户输入M,N值，N个人围成一个环， 从0号人开始数,数到M,那个人就退出游戏，直到最后一个人 求最后一个剩下的人是几号？在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋 友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到， 于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个 重新报数，直到所有人都自杀身亡为止。
然而Josephus 和 他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他 将朋友与自己安排在第16个与第31个位置，于是逃过了这场 死亡游戏原题： 用户输入M,N值，N个人围成一个环， 从0号人开始数,数到M,那个人就退出游戏，直到最后一个人 求最后一个剩下的人是几号？背景背景2010年10月28日星期四3实验1 约瑟夫环问题实验1 约瑟夫环问题【【问题描述】问题描述】 设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先 第1个人从1开始顺时针报数．报m的人(m 为正数)．令其出 列然后再从他的下一个人开始，重新从1顺时针报数，报m 的人，再令其出列如此下去，直到圈中所有人出列为止 求出列编号序列设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先 第1个人从1开始顺时针报数．报m的人(m 为正数)．令其出 列然后再从他的下一个人开始，重新从1顺时针报数，报m 的人，再令其出列如此下去，直到圈中所有人出列为止 求出列编号序列 【基本要求】【基本要求】 基于线性表的基本操作来实现约瑟夫问题，产生依次退出 该圈子人的编号基于线性表的基本操作来实现约瑟夫问题，产生依次退出 该圈子人的编号。
2010年10月28日星期四4实验1 约瑟夫环问题实验1 约瑟夫环问题#include #include class Josephuscircle; class Josephusnode { int number; Josephusnode * next; public: friend class Josephuscircle; }; class Josephuscircle { private: Josephusnode *head, *current; int total,count,start; //定义三个参数分别作为总人数、报数长度、起始位置定义三个参数分别作为总人数、报数长度、起始位置 public: Josephuscircle (); //构造函数构造函数 ~Josephuscircle (){delete [] head;} //析构函数析构函数 void counting(); //报数函数报数函数 };2010年10月28日星期四5实验1 约瑟夫环问题实验1 约瑟夫环问题Josephuscircle::Josephuscircle() { int n,k,m; cout>输入圈中的人数输入圈中的人数,报数长度报数长度,起始位置：起始位置：“; loop: cin>>n>>k>>m; coutn) { cout>>初始化参数不合法！初始化参数不合法！“>>请重新输入参数！请重新输入参数！\n“number=0; //创建表头创建表头2010年10月28日星期四6实验1 约瑟夫环问题实验1 约瑟夫环问题head->next=NULL; int i=1; while(inext=new Josephusnode; //创建并初始化链表创建并初始化链表 if(current==NULL) { cerrnumber=i; i++; } current->next=head->next; //首尾连接形成循环链表首尾连接形成循环链表 current=head; //当前指针指向表头当前指针指向表头 } void Josephuscircle::counting() { for(int i=1;inext; //将当前指针指向报数的起始位置将当前指针指向报数的起始位置 head->next=current; } Josephusnode *temp; //中转节点中转节点 int k=total; while(k>1) { for(int j=1;jnext; //报数报数 temp=current->next; //跳过将要被删除的节点跳过将要被删除的节点 current->next=temp->next; cout>第第“number>剩下的人是第剩下的人是第“next->numbernext; } 实验1 约瑟夫环问题实验1 约瑟夫环问题2010年10月28日星期四8int main() { char c; loop1: Josephuscircle Josephus; //定义一个对象并初始化定义一个对象并初始化 Josephus.counting(); //从链表中删除相关节点从链表中删除相关节点 cout>>是否重新开始是否重新开始?(Y/N)“>c; if(c=='y'||c=='Y') goto loop1; else if(c=='N'||c=='n') return 0; else {cout>>输入字符不正确输入字符不正确!“>>请重新选择操作请重新选择操作!“0，从 编号为1的人开始，按顺时针方向1开始顺序报数，报到m时 停止。
报m的人出圈，同时留下他的密码作为新的m值，从他 在顺时针方向上的下一个人开始，重新从1开始报数，如此 下去，直至所有的人全部出列为止编号为1,2,...,n的n个人按顺时针方向围坐一圈，每 人持有一个密码（正整数）现在给定一个随机数m>0，从 编号为1的人开始，按顺时针方向1开始顺序报数，报到m时 停止报m的人出圈，同时留下他的密码作为新的m值，从他 在顺时针方向上的下一个人开始，重新从1开始报数，如此 下去，直至所有的人全部出列为止约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：例：4596157318213224m：密码k：计数 m：密码k：计数start?出队序列：出队序列：k=15约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：4596157318213224m：密码k：计数start?出队序列：出队序列：k=25约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：4596157318213224m：密码k：计数start?出队序列：出队序列：k=3 5约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：4596157318213224m：密码k：计数start?出队序列：出队序列：k=4 5约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：m：密码k：计数?出队序列：出队序列：start4596157318213224k=5 5存入密码约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：96157318213224m：密码k：计数start?出队序列：出队序列：k=145约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：96157318213224m：密码k：计数start?出队序列：出队序列：5k=44约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：961573113224m：密码k：计数start?出队序列：出队序列：5k=1 82约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：961573113224m：密码k：计数start?出队序列：出队序列：52k=88约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：1573113224m：密码k：计数start?出队序列：出队序列：52k=196约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：1573113224m：密码k：计数start?出队序列：出队序列：52k=996约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：3113224m：密码k：计数start?出队序列：出队序列：52k=11567约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：3113224m：密码k：计数start?出队序列：出队序列：5267k=15 15约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：3113m：密码k：计数start?出队序列：出队序列：52674k=122约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：3113m：密码k：计数start?出队序列：出队序列：52674k=22 22约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：31m：密码k：计数start?出队序列：出队序列：526743k=11约瑟夫环(Joseph Circle)约瑟夫环(Joseph Circle)?例：m：密码k：计数start?出队序列：出队序列：526743k=131Joseph's PuzzleJoseph's P pratices 10045Problem descriptionProblem description?Persons, whose number order is from 1 to N, hold a password (the straight integer less than 10000) each person and sit around clockwise.?At first we choose a positive integer factor as the count off number M and start to number clockwise from number one .As we number to M the person who numbers M leaves the rank and whose password will be the new number M. And then start to number again from the person who is sit clockw。