选猴王问题.doc

1.实验内容： 约瑟夫问题： n只猴子要选猴王，所有的猴子按照1，2，.n编号围成一圆，从第1还开始按1，2，.m报数，凡是报m的猴子退出圈外，如此循环直到圈内剩下一只猴子，这只猴子就是猴王。编写程序n和m由键盘输入。2.实验要求： （1.）用顺序表和单链表分别实现约瑟夫问题； （2.）实验报告要求：A.实验名称：线性表的应用 B.实验目的： a.掌握基本操作在顺序和链式存储上的实现； b.以各种操作（建立，插入，删除，遍历）为重点； c.掌握线性表的动态分配，顺序存储结构的定义以及基本操作的实现；d.通过本章实验帮助学生加深C语言的使用。（特别是函数的参数的调用，指针类型的调用和链表的建立等各种操作） C.实验内容：（问题的描述，算法的描述，程序清单，测试数据）方法一：#include#define size 100 /* 输入人数的上限 */void main() int personsize; int i, j,d=0; /* 循环修正变量 */ int arrayLen; /* 数组长度 */ int start, overNum; /* 开始位置各跨过位置 */ int deleNum; /* 出列人所在数组中的下标 */ int name, total; /* 输入时,人的信息以及人的总数 */ printf( 请输入圆桌上人的总数: ); scanf( %d, &arrayLen ); printf( n ); if( ( arrayLen size ) | ( arrayLen 0 ) ) printf( 超出范围,请重新输入: ); scanf( %d, &arrayLen ); printf( n ); ; printf( 请输入各个人的信息(以输入整数表示每个人相应的位置): n ); for( i = 0; i arrayLen; i+ ) printf( 第%d个人相应的位置所对应的整数: ,+d); scanf( %d, &name ); personi = name; printf( 你输入的数据的顺序为: ); for( i = 0; i , personi ); printf( %d n, personarrayLen - 1 ); printf( n ); printf( 你打算从第几个人开始? 请输入开始号: ); scanf( %d, &start ); printf( n); start = start - 1; printf( 请输入相邻两出列人之间的间隔: ); scanf( %d, &overNum ); printf( n ); total = arrayLen; printf( 程序运行后,出列人的顺序为:nn ); for( i = 0; i , persondeleNum ); for ( j = deleNum; j arrayLen; j+ ) /* 将出列元素后面的各元素前移 */personj = personj+1; start = deleNum; arrayLen = arrayLen - 1; /* 移动完毕后,数组长度减1 */ printf( nn );方法二：#include #include typedef struct list int data; struct list *next; linklist; void main() int n,m,k,i=1; linklist head,*p,*q,*l; printf(输入总猴子数n: );scanf(%d,&n); printf(n );printf(输入开始报数猴子m: );scanf(%d,&m); printf(n );printf(输入循环数k: );scanf(%d,&k); printf(n );l=&head; p=l; for(i=1;inext=q; q-data=i; p=q; p-next=l-next; /*创建循环表*/ p=l-next; for(i=1;inext; while(p-data!=p-next-data) for(i=1;inext; q=p-next; printf(%3d,q-data); p-next=q-next; p=q-next; /*p指向第k+1猴子的位置*/