约瑟夫环C语言的实现验证报告

1、约瑟夫环姓 学 系 班名号别信息与电子系级计算填写日期 2010年10月30一 问题描述约瑟夫(joseph)问题的一种描述是：编号为1, 2, n的n个人按顺 时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数 作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到 m时停止报数。报m的人岀列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求岀出列顺序o二.基本要求利用利用顺序表存储结构及单向循环链表存储结构模拟约瑟夫环，按照出 列的顺序印出各人的编号三测试数据m的上限为20,初值为6；(1)

2、 对于门二7, 7个人的密码依次为：3, 1, 7, 2, 4, 8, 4进行测试。(2) 对于从键盘输入的n和n个人的密码进行测试。用数组实现约瑟夫环程序代码：#include<stdio. h>void ma in ()int num100;i nt m, n, i, k=0, s二0;int *p=num;pr i ntf ("输入初始密码和人数n n"); scanf("%d%ct, &m, &n);printfc个人密码n，z);for (i=1;i<=n;i+)scanf ("%d", &n

3、umi);i 二1 ；whi le(s<=(n-1) /当未退出人数(s)大于等于一时执行循环体 if (*(p+i) !二0)k+;if (k 二二 m)printf (，z%d ，i);m=* (p+i);*(p+i)二0; /对退出的人编号置零k 二0;s+；i+；i f (i二二(n+1) /当循环到最后一位时返回到第一位i 二1 ；测试数据结果:cdt:usersstyledesktopdebugcppl.exe *输入初始密码和人数n6 7个人密码31724846147235 press any key to continue五用链表实现约瑟夫环程序代码：#i nciude&

4、lt;stdio.h>#i nciude<mai ioc h>typedef struet i i stint num;int passward;struet 丨 i st *next;node;node *creatlist(int n)node *p,*q,*head;int i二1;head二(node *)ma i ioc (s i zeof (node); head->num=i;printff请输入第1个密码:，z);scanf("%d"，&head->passward);p二head;for (i =2; i <=n

5、; i +)q二(node *)ma i ioc (s i zeof(node);if (q=0) return 0;pr intf c请输入第%4个人的密码i); scanf (，%d，/, &q->passward);q->num二 i; p->next二q;p 二q；p->next二head; return head;void josephus (node *1, int k)int i;node *p=l,*q,*s; while (p->next!二p)for (i二1; i<k; i+)q 二p；p二p->next;printf c

6、%d，z, p->num); k=p->passward;s 二p;q->next二p->next;p二p->next;free (s);pr intf r%d，z, p->num); printf (，n<，);void ma in ()node *l;i nt n, k;printfc请输入实验人数：“)； scanf ("%d",&n);pr i ntf ("请输入初始key的值：); scanf("%ct, &k);丨二crea11 i st (n); josephus (i, k);测试

7、数据结果:请输入实验人数：7 请输入材站key的值:6 请输入寬1个密科：3 请鎰入重2个人的密码:1 请输入童3个人的密利:? 请输入寬4个人的密箱:2 请输入第5个人的密箱:4 请输入童6个人的密柜）:8 请输入寬?个人的密码：46 1 4 7 2 3 5press any key to continue六：学习体会和实验中遇到的问题约瑟夫环，经过理解，可以认为是一个数学应用题：已知n个人围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一 个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到桌周围的人全部出列。用数组实现约瑟夫环的过程中，我第一个遇到的 问题是理解了实验问题，但算法无法写成表达式，怎样让数组中的元素重 复剔除，后来通过网络上的学习和同学的参考理解了。在数组的实现过程 中，我感觉最难的是循环的剔除。用链表实现过程中，我觉得通过指针的