约瑟夫问题编写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;
}
}
tmthosting怎么样?tmthosting家本站也分享过多次,之前也是不温不火的商家,加上商家的价格略贵,之到斯巴达商家出现,这个商家才被中国用户熟知,原因就是斯巴达家的机器是三网回程AS4837线路,而且也没有多余的加价,斯巴达家断货后,有朋友发现TMTHosting竟然也在同一机房,所以大家就都入手了TMTHosting家的机器。目前,TMTHosting商家放出了夏季优惠,针对VPS推...
95idc是一家香港公司,主要产品香港GIA线路沙田CN2线路独服,美国CERA高防服务器,日本CN2直连服务器,即日起,购买香港/日本云主机,在今年3月份,95IDC推出来一款香港物理机/香港多ip站群服务器,BGP+CN2线路终身7折,月付350元起。不过今天,推荐一个价格更美的香港物理机,5个ip,BGP+CN2线路,月付299元起,有需要的,可以关注一下。95idc优惠码:优惠码:596J...
IMIDC是一家香港本土运营商,商家名为彩虹数据(Rainbow Cloud),全线产品自营,自有IP网络资源等,提供的产品包括VPS主机、独立服务器、站群独立服务器等,数据中心区域包括香港、日本、台湾、美国和南非等地机房,CN2网络直连到中国大陆。目前主机商针对日本独立服务器做促销活动,而且提供/28 IPv4,国内直连带宽优惠后每月仅88美元起。JP Multiple IP Customize...
约瑟夫问题为你推荐
开票系统怎样开普通发票系统附清单fclose为什么fclose之后remove还是不成功showwindowVB6.0中ShowWindow函数的使用查字网“很”去掉双人旁读什么?rdl电脑主机上的dvd+rdl是什么意思webcrack我用WebCrack4 在破解路由器密码的时候为什么在破解密码的中途自动关闭掉bindserviceservice在手机程序中起什么作用李昊天铠甲勇士2刑天的李昊天秘密是什么jdk6JDK6和JDK7两个版本有什么区别,初学者选那个好?vipjrvipjr跟哒哒英语比,两家公司的区别在哪里?各自的特点有哪些?
国内ip代理 网站域名空间 查域名 西安服务器租用 韩国vps俄罗斯美女 yardvps kddi 网络星期一 免费ddos防火墙 服务器架设 admit的用法 免费防火墙 国外代理服务器软件 重庆双线服务器托管 怎么建立邮箱 789 阿里云邮箱登陆 ssl加速 七牛云存储 蓝队云 更多