C语言数据结构中约瑟夫环问题如何解决
导读:本文共2788字符,通常情况下阅读需要9分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 问题描述约瑟夫环问题的一种描述是:将编号为1,2,...n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报道m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。基本... ...
目录
(为您整理了一些要点),点击可以直达。问题描述
约瑟夫环问题的一种描述是:将编号为1,2,...n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报道m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。
基本要求
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出个人的编号。
测试数据
m的初值为20;n = 7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序应为6,1,4,7,2,3,5)。
实现思路1
用的是数组索引。结合一点点的算法知识。
#include<stdlib.h>#include<stdio.h>//#用数组索引的模式intmain(){ intm; printf("请输入m的值:"); scanf("%d",&m); intn; printf("请输入n的值:"); scanf("%d",&n); inta[100]; for(inti=0;i<n;i++){ scanf("%d",&a[i]); } intcnt=0; intcnt1=0; inti=0; while(1){ if(a[i]!=0){ cnt++; if(cnt==m){ m=a[i]; a[i]=0; cnt=0; printf("%d",i+1); cnt1++; } if(cnt1==n){ break; } } i=(++i)%n; }}
实现思路2
利用单项循环链表的方式,上干货
运用的函数:
创建链表
取得链表的下标
删除链表指定下标的元素
得到第i个元素值
数据结构的定义:
结构体 LNode,成员包括:原始下标,元素值
主函数的思路:
其中上面的函数都是参考《数据结构(C语言版)》上面。只是将创建链表的函数改成创建单向循环链表的函数。写代码主要时间消耗在主函数上。
主函数的思路:
创建一个指定大小(n)的循环链表,每一次循环得到第m个元素,记录此元素的下标,然后移动头结点到删除元素前面的结点,再把此时的头节点后面1一个结点给删除。依次遍历到n个。
#include<stdlib.h>#include<stdio.h>//用单项循环列表的方式//数据类型的定义typedefstructLNode{ intdata; //定义密码值 intindex; //定义数据的下标 structLNode*next;}LNode,*LinkList;intGetElem_L(LinkListL,inti,int&e){ LNode*p; //注意这里的*号 p=L->next; intj=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i) { return-1; } e=p->data;// printf("%d",e); returne;}//GetElem_LintGetIndex_L(LinkListL,inti,int&e){ LNode*p; //注意这里的*号 p=L->next; intj=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i) { return-1; } e=p->index;// printf("%d",e); returne;}//GetIndex_LintListDelete_L(LinkList&L,inti,int&e){ LNode*p; //注意这里的*号 p=L; intj=0; while(p->next&&j<i-1){ p=p->next; ++j; } if(!(p->next)||j>i-1){ return-1; } LNode*q; q=p->next; p->next=q->next; e=q->data; free(q); returne;}//ListDelete_LvoidCreateList_L(LinkList&L,intn){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; LNode*tmp=(LinkList)malloc(sizeof(LNode)); tmp=L; for(inti=0;i<n-1;++i){ LNode*p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->index=i+1; p->next=tmp->next; tmp->next=p; tmp=tmp->next; } LNode*p=(LinkList)malloc(sizeof(LNode));//注意这里的*号 scanf("%d",&p->data); p->index=n; p->next=L->next; tmp->next=p;}//创建循环链表intmain(){ intm; intcnt; printf("请输入m的值:"); scanf("%d",&m); intn; printf("请输入n的值:"); scanf("%d",&n); LNode*L; //注意这里的*号 CreateList_L(L,n); inte=0; intindex=0; for(inti=0;i<n;i++){ GetElem_L(L,i+1,e); } for(inti=0;i<n;i++){ intl=0; l=GetIndex_L(L,m,index); printf("%d",l); inttmp=GetElem_L(L,m,e); for(inti=0;i<m-1;i++){ L=L->next; } ListDelete_L(L,1,e); m=tmp; }}
结果
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
C语言数据结构中约瑟夫环问题如何解决的详细内容,希望对您有所帮助,信息来源于网络。