内容发布更新时间 : 2024/12/22 12:00:10星期一 下面是文章的全部内容请认真阅读。
约瑟夫斯问题实验报告
学号 150820127 姓名 王碧辉
一、问题描述 1、实验题目
约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2、基本要求
利用单向循环链表存储结构模拟此过程，按照出列的顺序
印出各人的编号。 3、测试数据
m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。
4、简述每一部分的对象、目的和要求： (1)主函数部分： 对象：链表； 目的：创建新链表； 要求：将该链表初始化 。 （2）被调函数部分： 对象：结构体；
目的：创建循环链表并且模拟约瑟夫斯问题；
要求：让链表首尾相接，并且释放原来单链表的头结点空间。
通过该函数的调用，依次输出各结点的编号，并且符合规则。 二、需求分析
1.程序所能达到的基本可能：
该程序用循环链表来模拟n个人顺时针围坐一圈，用链表中的每一个结点代表一个人，结点结构体中设置两个变量，分别存放其编号以及密码。在输入初始密码后，对该链表进行遍历，直到遍历到第m个结点，释放其空间，使其出列。然后用被释放空间结点的密码值作为新的密码值，重复上述过程，直至所有结点被释放空间出列，链表成为空链表。 2.输入输出形式及输入值范围：
程序运行后显示提示信息：\input a data:\，提示用户输入密码信息，在输入达预定次数后自动跳出该循环，同时循环链表创建成功，在主函数中有相应的输出给予检验。然后程序显示提示信息：\，提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。用户输入完毕后，程序自动输出运行结果。输入值须为正整数。 3.测试数据要求：无。 三、程序设计 1、结构体定义 Struct node { };
基本操作：node *CreateNode(void)//创建单向循环链表 void CoutNum(node *p)//每次输出符合要求的节点编号 2、程序保护模块
int data;//节点密码 int num;//节点编号
node *next;//指向下一结点的指针
主函数模块： 结构体循环链表模块： 调用关系： 主函数 3、算法流程图
图1.创建循环链表