约瑟夫环问题实验报告

约瑟夫环问题实验报告约瑟夫环问题实验报告 实验课题 用循环链表解决约瑟夫环的问题 参与者 XX 班 级 教育技术 121 班 日 期 2013 年 10 月 11 日 上机环境 宿舍个人电脑 硬件设施如下图所示 实验要求实验要求 实验目的实验目的 熟悉 C 语言的基本编程方法 掌握线性表的操作实现方法 培养使用线性表解决实际问题的能力 实验内容实验内容 利用循环链表实现约瑟夫问题的求解 存储结构 循环链表 约瑟夫问题如下 一一 小孩报数问题 有 N 个小孩围城一圈 给他们从 1 开始依次编号 现指定从第 W 个开始报数 报到第 S 个时 该小孩出列 然后从下一个小 孩开始报数 仍是报到第 S 个时出列 如此重复下去 直到所 有的小孩都出列 总人数不足 S 个时将循环报数 求小孩出列 的顺序 算法分析算法分析 用一个标准的输入输出的头文件 iostream h 为了 统一对表中任意节点的操作 循环链表不带头结点 循环链表 的结点定义为如下结构类型 include include structstruct NodeNode intint data data structstruct NodeNode next next intint main main intint m n m n cout cout m cin m cout cout n cin n NodeNode first last first last first last newfirst last new Node Node 生成第一个结点生成第一个结点 first data 1 first data 1 for intfor int i 2 i n 1 i i 2 idata i p data i last next p last p last next p last p 链接结点链接结点 last next first last next first intint number n number n NodeNode pre last pre last while number 1 while number 1 for intfor int j 1 j m j j 1 jnext pre pre next NodeNode p pre next p pre next pre next p next pre next p next cout data cout data deletedelete p p number number cout data cout data deletedelete pre pre 输出结果如下图所示 输出结果如下图所示 二二 Joseph 约瑟夫 问题是非常著名的 最原始的问题是 n 个人 记为 1 2 n 站成一圈 从第一个人开始数 数 到的第 m 个人将要被处死 如此反复进行 直到只剩下一个人 而这个人会获救 比如 当 n 6 m 5 那么这些人将以 5 4 6 2 3 的次序被处死 而 1 就获救了 假设有 k 个好人和 k 个坏人围成一圈 其中 1 到 k 是好人 k 1 到 2k 是坏人 你必须选择 m 使得所有的坏人都先被处 死 然后才是第一个好人 并且要求 m 最小 include structstruct NodeNode intint data data NodeNode pNext pNext voidvoid main main intint n k m i n k m i NodeNode p q head p q head cout cout n cin n cout cout k cin k cout cout m cin m head Node newhead Node new Node Node 确定头结点确定头结点 p head p head for i 1 i n 1 i for i 1 idata i p data i p pNext Node newp pNext Node new Node Node 为下一个新建内存为下一个新建内存 p p pNext p p pNext p data n p data n 最后一个单独处最后一个单独处 理理 p pNext head p pNext head 指向头 形成循环指向头 形成循环 链表链表 p head p head while p data p pNext data while p data p pNext data p data p p data p pNext data pNext data 表示只剩下一个结点的表示只剩下一个结点的 while p datawhile p data k k 寻找编号为寻找编号为 k k 的结点的结点 p p pNext p p pNext if m 1 if m 1 for i 1 i n i for i 1 i n i cout data t cout data pNextp p pNext cout n cout n return return elseelse for i 1 i m 1 i for i 1 ipNext p p pNext 找到报找到报 m 1m 1 的结点的结点 q p pNext q p pNext q q 为报为报 m m 的结点的结点 cout data t cout data pNext data k q pNext data k k 为下一个报数的起点为下一