关于约瑟夫环的解法

《关于约瑟夫环的解法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于约瑟夫环的解法自己曾经考过三级遇到过一些问题，自己也琢磨过其中有一道排队的题日叫“约瑟夫环”。自己曾经查过一些资料答案有几种有的用链表解决思路清晰，但对初学链表的人却不是很好理解，有的用数组排列的方法解决程序干净简洁但其中有一段对初学者也较为困难。经过我自己研究我找到了一种理解起来相对较容易的方法，可能程序运行效率不如上面第二种高但对有一定基础的初学者还是比较容易的。首先我们看一道题目：有一组数，1,2,3,4,5,6。请通过数组元素移动的方法将其变为4,_5二6,1,2,3。很简单：main(){inta[6]={

2、l,2,3,4,5,6};intfor(i=0;i<3;i++)//向左移动三次{t=a[O];〃将第一个元素首先保护起来for(j=0;j<5;j++)a『Fa[j+l];//向左移动一个位置a[j]=t;//降第一个元素放至最后一位}理解了上面这道题，约瑟夫环就快解决了；按照题目的要求我们是要把报到M的人提出来排队，如果我们把报到M的人放到到最后一位，并且下一次报数时不让他参与问题就简单了我们假设要把报道“3”的人踢世队伍，而且从第一个人开始报数1—2——6—7—8—9—10:234<—5678—9*—1013<-4

3、<-5<-6<-7<-8<-9<-10<-1<-24——7—8—9—10—1—2—3经过第一轮报数得：4—5—6—7—8—9—10—1—2—3其实这个过程是让整个队伍向前走，第一个人走到队尾第二个人跟到第一个人后面，第三个人跟到第二个人后面，当第三个人走到对尾时第一轮结束，并且剩下的九个人准备开始下一轮这就犹如一个游戏：有一对人编号为1——10,游戏开始第一个人报”1”完成此轮报数并且走到对尾，第二个人报”2“完成此伦报数并且走到对尾，第三个人报”3”完成此轮报数，走到现有10人的对尾并且不再参加下一轮报数。剩余九人保持

4、现有相对顺序不变，继续按照前述规则进行，此轮报到”3“的人站在现有9人的对尾。如此继续，报数的人越来越少，报过”3”的人也自成一队列。第一轮后的结果：4—5—6—7—8—9—10—1—2—3;5—6—7—8—9—10—1—2—4—36—7—8—9—10—1—2-4—5—37<-8<-9<-10—1—2<-4—5—6—3笫—轮结果：7—8—9—10—1—2—4—5—6—3do{for(i=0;i

5、的例子完全一样只不过n在变化}while(n-);//直到将所冇位置都排上人，每排一轮就冇一个人退出，不再参加下一轮这段代码是完成人员的排列移动其中最关键就是运用doTTwhile,n・■表示每轮报数结束后对尾那个报“3”的人不再参加下--轮报数。接下來就需要满足从笫S个人开始的要求，为了简便我们将给成员编号和从第S个人开始的要求同时满足for(i=0;i

6、到n编号，从笫s个人开始进行1到ni的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所有的人都出圈为止。现要求按出圈次序，每10人一组，给出这n个人的顺序表。请考生编制函数Joscgh()实现此功能并调用函数WriteDat()把结果p输出到文件OUT.DAT屮。设n=100,c=l,m=10o(1)将1到n个人的序号存入一维数组p中；(2)若第1个人报数后出圈，则将p[i]置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置；(3)重复第(2)步直至圈

7、中只剩下p

8、l

9、为止。部分源程序已给出。请勿改动主函数main()和输出数据函数writeDat()的内容。#include//defineN100#defineS1#defineMIOintp[100],n,s?m;voidWritcDat(void);voidJosegh(void)intn,s,m,t,ij;n=N;s=S;m=M;for(i=0;i

10、i]=i+s;elsep[i]=i+s-n;}〃给数组中赋值，同时将第S个人排到了第一位do{for(i=0;i

11、