欢迎来到天天文库
浏览记录
ID:12511668
大小:162.71 KB
页数:4页
时间:2018-07-17
《求解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。截图如下:
此文档下载收益归作者所有