C语言-约瑟夫环问题.doc
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 约瑟夫 问题
- 资源描述:
-
实验一:约瑟夫环问题 一.实验目的: 要求设计一个程序模拟约瑟夫环问题过程,求出出列编号序列。 二.实验内容: 约瑟夫环问题:设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m是停止报数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1报数。如此下去,直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程,求出出列编号序列。 三.实验过程: 用一个不带头结点的循环链表来处理Josephu 问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,把被删除结点的密码作为新的m值,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。 #include<stdio.h> #include<stdlib.h> #define MAX_NODE_NUM 30 #define TRUE 1 #define FALSE 0 typedef struct NodeType { int number; int password; struct NodeType *next; } NodeType; /* 创建单向循环链表 */ static void CreaList(NodeType **, const int); /* 运行"约瑟夫环"问题 */ static void StatGame(NodeType **, int); /* 打印循环链表 */ static void PrntList(const NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE,非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) { int n, m; NodeType *pHead=NULL; while(1) {printf("输入总的人数 n(<=%d):",MAX_NODE_NUM); scanf("%d",&n); printf("初始循环的密码为:"); scanf("%d",&m); if(n>MAX_NODE_NUM) {printf("数字太大,请重新输入!\n"); continue; } else break; } CreaList(&pHead,n); printf("\n打印出原始每个结点的序列号和密码\n"); PrntList(pHead); printf("\n最终每个结点退出的序列号和密码\n"); StatGame(&pHead,m); return 0; } static void CreaList(NodeType **ppHead, const int n) { int i,iCipher; NodeType *pNew, *pCur; for(i=1;i<=n;i++) { printf("第%d个人的密码为:",i); scanf("%d", &iCipher); pNew=GetNode(i,iCipher); if(*ppHead==NULL) { *ppHead=pCur=pNew; pCur->next=*ppHead; } else { pNew->next=pCur->next; pCur->next=pNew; pCur=pNew; } } printf("已完成结点初始化!\n"); } static void StatGame(NodeType **ppHead, int iCipher) { int iCounter, iFlag=1,i=1; NodeType *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; while(pPrv->next!=*ppHead) pPrv=pPrv->next; while(iFlag) { for(iCounter=1;iCounter<iCipher;iCounter++) { pPrv=pCur; pCur=pCur->next; } if(pPrv==pCur) iFlag=0; pDel=pCur; pPrv->next=pCur->next; pCur=pCur->next; iCipher=pDel->password; printf("第%d个退出的是序列号为%d的人,其密码为:%d\n", i, pDel->number, pDel->password); free(pDel); ++i; } *ppHead=NULL; } static void PrntList(const NodeType *pHead) { const NodeType *pCur=pHead; if (EmptyList(pHead)) return; do { printf("第%d 个人,密码:%d\n",pCur->number,pCur->password); pCur=pCur->next; } while (pCur!=pHead); } static NodeType *GetNode(const int iId,const int iCipher) { NodeType *pNew; pNew=(NodeType *)malloc(sizeof(NodeType)); if(!pNew) { printf("错误,内存不足!\n"); exit(-1); } pNew->number=iId; pNew->password=iCipher; pNew->next=NULL; return pNew; } static unsigned EmptyList(const NodeType *pHead) { if(!pHead) { printf("列表为空!\n"); return TRUE; } return FALSE; } 4展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


C语言-约瑟夫环问题.doc
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/10820595.html