求解约瑟夫环问题 C语言_百度知道
求解约瑟夫环问题 C语言
&& 求解约瑟夫环问题。设有n个人，其编号分别为1，2，3，…，n，安装编号顺序顺时针围坐一圈。选定一个正整数m，从第一个人开始顺时针报数，报到m时，则此人出列，然后从他的下一个人从1重新报数，依此类推，直到所有人全部出列为止，求出列的顺序。
提问者采纳
#include&stdio.h&#include&stdlib.h&
typedef struct node{
struct node * }NODE;NODE *createlink(int n){
NODE *head=NULL,*p=NULL,*q=NULL;
head=p=(struct node*)malloc(sizeof(struct node));
p-&value=i;
for(i=2;i&=n;i++){
q=(struct node*)malloc(sizeof(struct node));
if(q==0) return 0;
p-&next=q;
p-&value=i;
}void jose(NODE *p,int n,int m){ int i,j,g=0; NODE *q=NULL; for(i=1;i&=n;i++){
for(j=1;j&m;j++){
p-&next=q-&
if(g%5==0)
{g++;printf(&\n&);}
printf(&%3d:%3dout &,i,q-&value-1);
free(q); } printf(&\n&); p-&next=NULL;}int main( ){ int m=0; int n=0;
scanf(&%d&,&m);
scanf(&%d&,&n);
NODE *head=NULL; head=createlink(n); jose(head,n,m);return 0;}
其他类似问题
按默认排序
其他1条回答
#include&iostream&struct Node//循环节点的定义{//编号 Node *};Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数void Joseph(Node *L,int n,int m);//输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数int LengthList(Node *L);//计算环上所有人数函数void main()//主函数{
Node *L; L=NULL;//初始化尾指针 int n, cout&&&请输入人数N：&; cin&&n;//环的长度 if(n&1){cout&&&请输入正整数!&;}//人数异常处理 else {
cout&&&请输入所报数M：&;
if(m&1){cout&&&请输入正整数!&;}//号数异常处理
L=CreateList(L,n,m);//重新给尾指针赋值
Joseph(L,n,m);
} }system(&pause&);}Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）{ Node *q; for(int i=1;i&=n;i++) {
p-&number=i;
p-&next=NULL;
if(i==1) L=q=p;//工作指针的初始化
q-&next=p;
} } q-&next=L; if(L!=NULL){return(L);}//返回尾指针 else cout&&&尾指针异常!&&&//尾指针异常处理}void Joseph(Node *L,int n,int m)//输出每次出列的人{ cout&&&请输入第一个报数人：&; cin&&k; if(k&1||k&n){cout&&&请输入1-&&&n&&&之间的数&&&} else {
cout&&&\n出列顺序:\n&;
for(int i=1;i&n;i++)
Node *q = new N
if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数
else q=DeleteList(&L,m,q);
cout&&&号数：&&&q-&number&&//释放出列人的存储空间
cout&&&最后一个出列号数是：&&&L-&number&&;//输出最后出列人的号数 }}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{ if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式 Node *p; p=*L; int j=0; while(j&i-2) {p=p-&j++;}
q = p-& p-&next=p-&next-& *L = p-& return(q);}int LengthList(Node *L)//计算环上的人数{ if(L){cout&&&尾指针错误!&&&}//异常处理 else {
Node *p=L-&
while(p!=L)
return(i); }}
约瑟夫环的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁1315人阅读
约瑟夫环问题描述：编号为1，2& n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数， 报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程 序求出出列顺序。
&&&& 我们可以利用数组解决这个问题：
#include &stdio.h&
#define N 7&&/*圈里有7个人*/
void main(){&&/*circle数组的每一个数组元素表示圈内的一个人，元素的第一个域存放密码，第二个域存放与他顺时针
&&& 相邻的人得序号*/
&&/*count为计数器，alive为活& 着的人数*/& /*prev上一个报数的人的序号，当前报数人的序号*/&&int circle[N][2], count = 0, alive = N, pre = 0, cur, i,&
& for(i = 0; i & N; i++)&&{&&&&& circle[i][1] = (i+1) % N;&&&&/*初始化next域*/& }
& printf("请输入初始密码");&&&&&/*输入初始密码*/& scanf("%d", &passwd);
&&printf("请陆续输入圈内%d个人的密码：", i);& for(i = 0; i & N; i++)&&&&&&&&&&&&&&&&&&&&& /*输入密码*/&&{&&&& &scanf("%d", &circle[i][0]);& }
& /*报数*/&&printf("/n出列顺序为：");& for(cur = 0; alive != 0; cur = circle[cur][1])&&{&&&& &count++;&&& &if(count == passwd)&&& &{&&&&&&&&&& printf("%d ", cur);&&&&&&&&&&&passwd = circle[cur][0];&&&/*更改密码*/&&&&&&&&&& circle[pre][1] = circle[cur][1];&/*前一个人的next域改变*/&&&&&&&&&& count = 0;&&&&&&&/*报数归0*/&&&&&&&&&& alive--;&&&&&&&/*活人数目减1*/&&&& }&&&&& else&&& {&&&&&&&&&& pre =&&&&&&&/*上一个报数的序号改变*/&& &}&&}}
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：12837次
排名：千里之外
原创：15篇急！求解C语言关于约瑟夫环的程序？_百度知道
急！求解C语言关于约瑟夫环的程序？
然后读取各人的密码.n的n个人按顺时针方向围坐一圈，7，1，2，4，5：编号为1：程序运行后首先要求用户指定初始报数上限，将他的密码作为新的m值：密码3 ，4：约瑟夫环问题的一种描述是。
正确的结果，从第一个人开始顺时针自1开始顺序报数.3……。报m的人出列：利用循环链表存储结构模拟此过程，2。要求。提示，每人手持一个密码（正整数），8：6，3，开始任意选一个整数葼芈百继知荒打戎作为报数上限值.2，按照出列的顺序打印各人的编号。测试数据，从他顺时针下一个人开始重新从1开始报数，7，如此下去直到所有的人全部都出列为止，4，报到m时停止报数;30：m的值初始为20。试设计程序实现。设n&lt，1约瑟夫环
提问者采纳
scanf(&*输入人的总个数*/*重新定义Person%d&quot,
printf(&quot,*s;\code=
p=(lnode *)malloc(sizeof(lnode));=n;
}while(p;%d&quot,j为记数器;
struct node *key)
n--;nPlease
free(p);;*j为记数数*/p=next,i);
p-&gt,下次循环的开始结点*/
/););*输入各个人的密码*/
head=head-&),n;
lnode *p;*创建新的结点*/void main(){
int itypedef struct node{*每循环一次人是减1*&#47: &
&#47,p-&gt,j;
s-&gt,key为输入的密码;&#92,n为人的总个数*/nThe out 坎取贬渡撞盗碟掠next=p;
printf(&code):%d&quot:&
head=p-&gt,&n),*
head=(lnode *)malloc(sizeof(lnode));*输入第一个数*/0);next=p-&
/nPerson%d C;
/*输出链表*/
i=p-&*为头结点分配空间*/\
free(p),&key);*i;printf(&i++)
printf(&quot:&;num=i,p-&
scanf(&next:&
p=p-&i&Please enter t
p-&next=head-&%d&
j=1;!=head);Person %d&
getch();next,&key);
printf(&quot,key
提问者评价
多谢你了！
其他类似问题
按默认排序
其他1条回答
下载知道APP
随时随地咨询
出门在外也不愁急求C语言关于约瑟夫环问题，关于指针_百度知道
急求C语言关于约瑟夫环问题，关于指针
#include &stdio.h&#include &malloc.h&#include &stdlib.h&#define ElemType inttypedef int S// 链表类型typedef struct Node{ ElemT struct Node *} Node, *LinkL// 判断存储分配是否成功Status MallocOK(LinkList P){ if(P) return(1); printf(&\n Malloc Error \n&); return(0);}// 建立一个带头结点的、能够产生n个数据元素的线性链表Lvoid CreateJosephus(LinkList &L,int n){ L=(LinkList) malloc(sizeof(Node));
if (MallocOK(L)==0) L-&next=L; LinkList p,q=L; for (i=1; i&=n; ++i) {
p = (LinkList)malloc(sizeof(Node)); //生成新结点
if (MallocOK(p)==0)
q-&next=p;
p-&data=rand()%100+1;
q=p; } p-&next=L;}// 输出线性链表L中的所有数据元素void PrintJosephus(LinkList L){ LinkList p=L-& printf(&\nJosephus = ( &); while (p!=L && L-&next!=L) {
printf(&%d &,p-&data);
p=p-& } printf(&)\n&);}// 销毁线性链表Lvoid DestroyJosephus(LinkList &L){ free(L);
L=NULL; printf(&\n线性链表L已销毁\n&);}// 根据计数情况依次弹出线性链表L中的n个数据元素void Josephus(LinkList &L,int n,int k,int m){ int j=0; int i=1; LinkList q,p=L-& while (i&k) {
if (p==L) p=p-& } printf(&\nResult is ( &); while (j&n) {
i=1; //指针指向第m个结点
while (i&m)
if (p==L) p=p-&
printf(&%d &,p-&data); //输出被弹元素
if (q==L) q=q-&
p-&data=q-&
p-&next=q-&
free(q); //删除并释放结点
++j; } printf(&)\n&);}void main(){ LinkList L; int n0,k0,m0; printf(&\nPlease input Terms n = &); scanf(&%d&,&n0); if (n0&1) {
printf(&\n%d & 1\n&,n0); } CreateJosephus(L,n0); PrintJosephus(L); printf(&\nPlease input k, m = &); scanf(&%d, %d&,&k0,&m0); if (n0&0 && k0&0 && m0&0) Josephus(L,n0,k0,m0); DestroyJosephus(L);}
其他类似问题
按默认排序
其他1条回答
以前做过一个，函数结合指针的，还有用单链表处理的，给你贴一个，仅供参考
#include&stdio.h&#include&stdlib.h&//应用函数调用来实现void Fun_Kill(int *pa,int n,int m){ for(int i=0;i&n;i++) {
*(pa+i)=i+1;//给每个人编号 } i=0; int mCount=0; int iCount=0; while(iCount&n-1)//控制循环条件：出局人数小于总人数 {
if(*(pa+i)!=0)//报数条件,编号不为0
if(mCount==m)
printf(&%d is out!\n&,*(pa+i));//输出出局者的编号
mCount=0;//重新开始报数
iCount++;//出局人数统计
*(pa+i)=0;//出局者编号改为0,下次报数不进入计数
i++;//报数的同时指针也开始走动
i=0;//当i==n的时候，让i=0，让指针重新指向第一个人，循环计数
} } for(i=0;i&n;i++) {
if(*(pa+i)!=0)
printf(&%d is survival!&,*(pa+i));
} }}int main(){ int n,m; printf(&请输入总人数:&); scanf(&%d&,&n); printf(&请输入要报的数:&); scanf(&%d&,&m); int *pKill=(int *)malloc(sizeof(int)*n); Fun_Kill(pKill,n,m); free(pKill); pKill=NULL; return 0;}
约瑟夫环的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁c语言实现约瑟夫环问题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
2页免费3页1下载券25页免费1页¥0.502页免费 4页免费1页免费2页免费9页1下载券1页免费
喜欢此文档的还喜欢2页免费7页1下载券1页1下载券9页1下载券3页1下载券
c语言实现约瑟夫环问题|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢}