约瑟夫问题编写c语言程序解决约瑟夫问题,要求不用递归算法

约瑟夫问题  时间:2021-07-16  阅读:()

用单链表实现约瑟夫问题

#include typedef struct node { int num; struct node *next; }lnode; /*定义结构体*/ void main() { int i,j,n,s,m; lnode *p,*r,*head,*q ; /*指针变量*/ head=(lnode *)malloc(sizeof(lnode));/*头结点*/ p=head; printf("Please enter the num of the number:"); scanf("%d%d%d",&m,&s,&n); /*读入数据*/ for(i=1;i<=m;i++) { r=p; p=(lnode *)malloc(sizeof(lnode));/*申请节点*/ r->next=p; /*插入节点,存入数据*/ p->num=i; } p->next=head->next; /*构建循环链表*/ p=p->next; j=1; while(jnext; j++; } do { for(i=1;inext; } q=p->next; /*q指向要读取数据的节点*/ printf(" The out of the num:"); printf("%d",q->num); /*输出该数*/ p->next=q->next; /*指向下一个查数起点,释放节点*/ free(q); p=p->next; m--; /*m自减,控制循环次数,直到按顺序输出所有的数*/ }while(m>0); getch(); }

程序----约瑟夫问题的实现(用c语言)

约瑟夫环: 约瑟夫环问题的一种描述是:编号为1.2.3…….n的n个人按顺时针方向围坐一圈 ,每人手持一个密码(正整数),开始任意选一个整数作为报数上限值,从第一 个人开始顺时针自1开始顺序报数,报到m时停止报数。

报m的人出列,将他的密 码作为新的m值,从他顺时针下一个人开始重新从1开始报数,如此下去直到所有 的人全部都出列为止。

试设计程序实现。

要求:利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号。

测试数据:m的值初始为20:密码3 ,1,7,2,4,8,4。

正确的结果:6,1,4,7,2,3,5。

提示:程序运行后首先要求用户指定初始报数上限。

然后读取各人的密码。

设 n<30。

typedef struct node { int num,code; struct node *next; }lnode; void main() { int i,j,key,n; /*i,j为记数器,key为输入的密码,n为人的总个数*/ lnode *p,*s,*head; head=(lnode *)malloc(sizeof(lnode)); /*为头结点分配空间*/ p=head; printf("Please enter the num of the person:"); /*输入人的总个数*/ scanf("%d",&n); for(i=1;i<=n;i++) { printf("Person %d",i); printf(" code: "); scanf("%d",&key); /*输入各个人的密码*/ s=p; p=(lnode *)malloc(sizeof(lnode)); /*创建新的结点*/ s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); p=head; do { printf(" Person%d Code:%d",p->num,p->code); /*输出链表*/ p=p->next; }while(p!=head); printf(" Please enter your first key:"); /*输入第一个数*/ scanf("%d",&key); do { j=1; /*j为记数数*/ p=head; while(j<key) { s=p; p=p->next; j++; } i=p->num; key=p->code; printf(" The out of the num:"); printf("Person%d",i); s->next=p->next; head=p->next; /*重新定义head,下次循环的开始结点*/ free(p); n--; /*每循环一次人是减1*/ }while(n>0); getch(); }

数学上的约瑟夫问题怎么解

在M比较小的时候 ,可以用笔算的方法求解, M=2 即N个人围成一圈,1,2,1,2的报数,报到2就去死,直到只剩下一个人为止。

当N=2^k的时候,第一个报数的人就是最后一个死的, 对于任意的自然数N 都可以表示为N=2^k+t,其中t<n/2 于是当有t个人去死的时候,就只剩下2^k个人 ,这2^k个人中第一个报数的就是最后去死的。

这2^k个人中第一个报数的人就是2t+1 于是就求出了当M=2时约瑟夫问题的解: 求出不大于N的最大的2的整数次幂,记为2^k,最后一个去死的人是2(N-2^k)+1 M=3 即N个人围成一圈,1,2,3,1,2,3的报数,报到3就去死,直到只剩下一个人为止。

此时要比M=2时要复杂的多 我们以N=2009为例计算 N=2009,M=3时最后被杀死的人记为F(2009,3),或者可以简单的记为F(2009) 假设现在还剩下n个人,则下一轮将杀死[n/3]个人,[]表示取整,还剩下n-[n/3]个人 设这n个人为a1,a2,...,a(n-1),an 从a1开始报数,一圈之后,剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an 于是可得: 1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1) 2、若3|n,则最后死的人为新一轮的第F(n-[n/3])个人 若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-(n mod 3)人 若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-(n mod 3)人 3、新一轮第k个人对应原来的第 3*[(k-1)/2]+(k-1)mod 2+1个人 综合1,2,3可得: F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1, 当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-(n mod 3),F(n)=3*[(k-1)/2]+(k-1)mod 2+1 当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-(n mod 3) ,F(n)=3*[(k-1)/2]+(k-1)mod 2+1 这种算法需要计算 [log(3/2)2009]次 这个数不大于22,可以用笔算了 于是: 第一圈,将杀死669个人,这一圈最后一个被杀死的人是2007,还剩下1340个人, 第二圈,杀死446人,还剩下894人 第三圈,杀死298人,还剩下596人 第四圈,杀死198人,还剩下398人 第五圈,杀死132人,还剩下266人 第六圈,杀死88人,还剩下178人 第七圈,杀死59人,还剩下119人 第八圈,杀死39人,还剩下80人 第九圈,杀死26人,还剩下54人 第十圈,杀死18人,还剩36人 十一圈,杀死12人,还剩24人 十二圈,杀死8人,还剩16人 十三圈,杀死5人,还剩11人 十四圈,杀死3人,还剩8人 十五圈,杀死2人,还剩6人 F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1, 然后逆推回去 F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130 F(596)=191 F(894)=286 F(1340)=425 F(2009)=634 -----来自百度

编写c语言程序解决约瑟夫问题,要求不用递归算法

楼主你好! 下面这个就是关于约瑟夫问题的题目,代码(不是递归的)及题目已经给出,希望对你有帮助! 原题: n个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将部分乘客投入海中,其余人才能幸免于难。

无奈,大家只得同意这种办法,并议定n个人围成一圈,由第1个人数起,依次报数,数到第m人,便把他投入大海中,然后再从他的下一个人数起,数到第m人,再将他扔到大海中,如此循环地进行,直到剩下k个乘客为止。

问哪些位置是将被扔下大海的位置。

#include<stdio.h> #include<stdlib.h> struct list{ //定义链表的节点结构 int number; //用于给乘客的位置编号 struct list*next; }; main(){ int i,n; //n表示人数,i用于for循环 struct list*head=NULL,*p,*q,*temp,*r; printf("请输入船上的人数n: "); scanf("%d",&n); for(i=1;i<=n;i++){ /*根据人数n,建立带头结点head循环链表*/ p=(struct list*)malloc(sizeof(struct list)); p->number=i; //给每位乘客位置编号 if(head==NULL){head=p;} else {q->next=p;} q=p; } p->next=head; r=head; int m,k,a=0; //m表示乘客数到这个需要下船的数,k表示最终船上剩余的乘客人数,a用于记录乘客总共报数的次数 printf("请输入数到需要下船的数m "); scanf("%d",&m); printf("请输入最终船上剩余人数k "); scanf("%d",&k); while(r!=NULL&&n!=k){ ++a; if((a+1)%m==0){ /*找出需下船乘客的前一位乘客,将需下船的乘客的节点删除,并将与下船乘客的相邻的两位乘客节点连起来,保证认是一个循环链表 */ temp=r->next; r->next=r->next->next; printf("编号为%d位置的乘客需要下船! ",temp->number); //输出下船乘客的位置编号 free(temp); n--; } else r=r->next; } }

HaBangNet(6.95美元/月)美国vps 5TB流量/德国vps 香港双向CN2 GIA VPS

HaBangNet支持支付宝和微信支付,只是价格偏贵,之前国内用户并不多。这次HaBangNet推出三个特价套餐,其中美国机房和德国机房价格也还可以,但是香港机房虽然是双向CN2 GIA线路,但是还是贵的惊人,需要美国和德国机房的可以参考下。HaBangNet是一家成立于2014年的香港IDC商家,中文译名:哈邦网络公司,主营中国香港、新加坡、澳大利亚、荷兰、美国、德国机房的虚拟主机、vps、专用...

HostKvm四月优惠:VPS主机全场八折,香港/美国洛杉矶机房$5.2/月起

HostKvm是一家成立于2013年的国外主机服务商,主要提供基于KVM架构的VPS主机,可选数据中心包括日本、新加坡、韩国、美国、中国香港等多个地区机房,均为国内直连或优化线路,延迟较低,适合建站或者远程办公等。本月商家针对全场VPS主机提供8折优惠码,优惠后美国洛杉矶VPS月付5.2美元起。下面列出几款不同机房VPS主机产品配置信息。套餐:美国US-Plan0CPU:1cores内存:1GB硬...

特网云,美国独立物理服务器 Atom d525 4G 100M 40G防御 280元/月 香港站群 E3-1200V2 8G 10M 1500元/月

特网云为您提供高速、稳定、安全、弹性的云计算服务计算、存储、监控、安全,完善的云产品满足您的一切所需,深耕云计算领域10余年;我们拥有前沿的核心技术,始终致力于为政府机构、企业组织和个人开发者提供稳定、安全、可靠、高性价比的云计算产品与服务。公司名:珠海市特网科技有限公司官方网站:https://www.56dr.com特网云为您提供高速、稳定、安全、弹性的云计算服务 计算、存储、监控、安全,完善...

约瑟夫问题为你推荐
soapui下载测试管理工具的soapUI开源测试工具mindmanager破解版求mindmanager 2019 的注册机mindmanager破解版谁有MindManager破解版的layout_gravityandroid 布局中 为什么能够通过android:layout_above 、android:layout_alignTop 、等 还要在之前加入索引超出了数组界限索引超出了数组界限是怎么回事啊?vipjrvipjr跟哒哒英语比,两家公司的区别在哪里?各自的特点有哪些?vipjr大家觉得vipjr少儿英语怎么样?靠谱不spawning在c语言编译时出现Error spawning cl.exe,是怎么回事?booth算法利用补码booth计算【xy】补,其中x=0.1110,y=-0.1101新手怎么制作表格怎样能学会制作表格
美国免费虚拟主机 php主机租用 美国加州vps 域名主机基地 个人域名备案 cve-2014-6271 监控宝 商务主机 天互数据 ftp教程 太原网通测速平台 gtt paypal注册教程 smtp虚拟服务器 php服务器 百度云空间 贵阳电信 可外链的相册 国外免费网盘 时间服务器 更多