网站提交,网站开发工具总结,广告行业做网站哪个好,百度网盘电话人工服务1问题描述
设有编号为1,2,3，....n的n(n0)个人围成一个圈，每个人持有一个密码m,从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的人出圈，........如此下去，直到所有人全部出圈为止。当给定n和m后，设计算法求n个…1问题描述
设有编号为1,2,3，....n的n(n0)个人围成一个圈，每个人持有一个密码m,从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的人出圈，........如此下去，直到所有人全部出圈为止。当给定n和m后，设计算法求n个人出圈的次序：
这是一个比较综合的问题，其求解步骤如下：
（1）分析问题，对问题建立数据模型
（2）根据问题的特点和运算为数据模型设计适当的存储结构
（3）基于存储结构设计相应的算法
（4）调试 算法，上机实现
2分析问题
分析问题最好的方法就是运行一个实例。
首先考虑比较简单的情况：每个人持有密码相同，假设n=6,m=3时约瑟夫环问题的求解过程： 注意：出圈顺序和报数规律
通过上述问题求解过程，可把问题的输入（即n个人的编号）看成是一个线性序列，每个人的编号看成是一个数据元素。因此，问题抽象出的数据模型是线性表（逻辑结构）
引申：针对一个待求解问题，只有抽象出数据模型，才能为其设计合适的数据结构，从而实现数据从机外表示到机内表示的转化
引申：一种存储结构设计是否合理，取决于运算是否方便和时间性能是否高效。实际中，可设计几种方案，经过分析比较选择最合理的存储结构。
3设计存储结构
线性表有2种基本存储结构：顺序存储结构和链式存储结构
（1）顺序存储结构
用顺序表存储约瑟夫环问题的输入数据（即n个人的编号），需要考虑以下问题：ab
a如何表示某人已出圈使之不参与下一轮报数，可以有2种解决方法
方案一：将出圈的人从顺序表中删除。由于顺序表中执行删除运算需要移动元素，降低问题求解效率 b当报数到表尾时如何再回到表头使计数循环进行下去
可以使用求模运算实现循环计数。
采用方案一，则顺序表的长度是变化的，需要在每次出圈后重新设定表长；
采用方案二，则顺序表长度不变，但是在计数时要先判断是否为出圈标志
（2）链式存储结构
由于约瑟夫环问题本身具有循环性质，考虑采用循环链表；为了统一对表中任意节点的操作，循环链表不带头结点。 问题1：
