约瑟夫环(严蔚敏答案).doc

约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。直到所有人全部出列。#include#include#define OK 1#define ERROR 0typedef int Status;typedef struct int num; /结点编号 int password; /结点密码ElemType;typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;int m,n;Status InitList_L(LinkList &L) /建立一个空的单循环链表，L为带头结点的单循环链表的头指针. _ L=(LinkList )malloc(sizeof(LNode);_ /生成新结点 if(!L) return ERROR; _L-next=L_/生成循环链表return OK; /InitList_LStatus ListInsert_L(LinkList &L, int i, ElemType e)/在带头结点的单循环链表L中第i个位置之后插入元素e LinkList p,s; int j; p = L; j = 0; while ( p-next!=L & jnext; +j; if (ji-1) return ERROR; /i 小于1或者大于表长 s = (LinkList )malloc(sizeof(LNode); /生成新结点 _s-data = e;_/新结点输入信息 _ s-next = p-next;_ /将新结点插入 _p-next = s;_ /将新结点插入 return OK;/ListInsert_Lvoid Joseph(LinkList &L) LinkList p,q; int i; m=m%n; /若mn时 q=L; p=L-next; while(_L-next!=L_)/只要还有结点 i=1; while(inext;_/p往后寻找 if(p!=L) i+; q-next=p-next; /第m个结点脱链 _printf(%3d,p-data.num);_ /输出第m个结点信息 m=_p-data.password;_; /将第m个人的密码作为新的m值 _free(p);_/删除第m个结点 p=q-next; if(p=L) q=p; p=p-next; free(L);int main() LinkList L,p; int i; int *a; ElemType e; scanf(%d,&n); /参加n个人 scanf(%d,&m); /初始第m个人出列 a=(int *)malloc(n*sizeof(int); for(i=0; in; i+) scanf(%d,a+i);/读入n个人的密码 InitList_L(L); for(i=1; i=n; i+) /创建循环链表，表示n个人围成一圈的约瑟夫环 e.num= _