求解josephus问题实验报告(c语言向量法实现)

《求解josephus问题实验报告(c语言向量法实现)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求解Josephus问题实验报告一、用向量法实现Josephus问题的求解1程序功能描述：连续输入n个数(报数的总人数)，从第s个位置开始报数，每隔m个数输出，直到n个数全部输出位置为止，观察出列次序。当n<0或s<1或m<=0时，输出”ERROR”。2主要数据结构描述用一维数组A[i]实现。3程序结构描述构造一个josephus函数，函数内部实现求解josephus问题的算法，然后再在主函数中调用josephus函数，使算法得以实现。4算法描述用数组A[i]记录第s（报数的初始位置）个位置的信息，用k表示每次执行后数组中剩余数字个数，通过i=(i+m-1)%k记录出列者位置

2、，并将其放入数组最后，第i个位置以后数字分别前移一位。最后将数组翻转，输出翻转后的数组。5程序测试方案与测试结果描述（1）输入n值为6，s值为3，m值为2，输入A[i]的值为123456输出结果为：462531截图如下：（2）1、输入n值为-1,s值为3，m值为2，显示：ERROR。截图如下：2、输入n值为6,s值为0，m值为3，显示：ERROR。截图如下：3、输入n值为6,s值为3，m值为0，显示：ERROR。截图如下：二、用循环单链表法实现josephus问题的求解1程序功能描述：连续输入n个数(报数的总人数)，从第s个位置开始报数，每隔m个数输出，直到n个数全部输出位置

3、为止，观察出列次序。当n<0或s<1或m<=0时，输出”ERROR”。2主要数据结构描述：用循环单链表实现。3程序结构描述：构造一个josephus函数，函数内部实现求解josephus问题的算法，然后再在主函数中调用josephus函数，使算法得以实现。4算法描述：（1）用三个指针变量p,q,tmp，另p指向head头指针,通过s次循环将p指向报数的起始位置s，用q记录p的位置，再经过m次循环另p指向出列者的位置，将其数值保存在一维数组中，并将其从链表中删除，p指向下一次起始位置，结束时返回数组A[j]。5程序测试方案与测试结果描述：（1）输入n值为6，s值为3，m值为2，

4、输入A[i]的值为123456输出结果为：462531截图如下：（2）1、输入n值为-1,s值为3，m值为2，显示：ERROR。截图如下：2、输入n值为6,s值为0，m值为2，显示：ERROR。截图如下：3、输入n值为6,s值为3，m值为0，显示：ERROR。截图如下：