作业帮分别用数组和链表实现约瑟夫环.约瑟夫(Joseph)问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 23:01:50
分别用数组和链表实现约瑟夫环.约瑟夫(Joseph)问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人
分别用数组和链表实现约瑟夫环.
约瑟夫(Joseph)问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.试设计一个程序求出出列顺序.
测试数据
m的上限为20,初值为6；
(1) 对于n=7,7个人的密码依次为：3,1,7,2,4,8,4进行测试.
(2) 对于从键盘输入的n和n个人的密码进行测试.
实现提示
1、算法思路
(1)对于已知的n个人的信息、密码可以采用结构体存储,shuru函数将数据存入结构体数组中.
(2)根据约瑟夫问题的要求,构造Joseph函数,设当前人员编号为s1,密码为m,当前共有i个人,则要出列为s1=(s1+m-1)%i,输出出列的成员编号,并将该成员后面的人往前移.
(3)、在主函数中要设置是选择已知的n和n个人的密码的情况和还是要从键盘输入的n和n个人的密码的情况,然后调用响应的函数来得到n和n个密码.
数据结构
struct node /* 单向循环链表结点结构 */
{int num;
int m;
}node;
主程序
main()
{ node *head;
int n;
printf("输入人员总数\n");
scanf("%d",&n);
shuru()
joseph(head,n);
}
(1) 对于要从键盘输入的n和n个人的密码的情况(任选)
初始密码为7
input n:10
no:1 input m:9
no:2 input m:15
no:3 input m:3
no:4 input m:7
no:5 input m:14
no:6 input m:10
no:7 input m:19
no:8 input m:6
no:9 input m:12
no:10 input m:8
6 7 10 1 4 8 2 9 5 3
最好有数组和链表两个程序.
一个也可以,不过希望有适量的注释说明,
回复1楼：不能运行额.
分别用数组和链表实现约瑟夫环.约瑟夫(Joseph)问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人
#include
#include
int main()
{
int i,m,n;
cin>>n>>m;
int a[n];
for(i=0;i