解决方案概述 约瑟夫环 约瑟夫环-概述,约瑟夫环-解决

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。

约瑟夫问题_约瑟夫环 -概述


约瑟夫环是一个数学的应用问题:

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

这个就是约瑟夫环问题的实际场景,有一种是要通过输入n,m,k三个正整数,来求出列的序列。这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素。 p->link=head

约瑟夫问题_约瑟夫环 -解决

解决问题的核心步骤:
1.建立一个具有n个链结点,无头结点的循环链表
2.确定第1个报数人的位置
3.不断地从链表中删除链结点,直到链表为空

void JOSEPHUS(int n,int k,int m) //n为总人数,k为第一个开始报数的人,m为出列者喊到的数
{
/* p为当前结点r为辅助结点,指向p的前驱结点list为头节点*/
LinkList p,r,list;

/*建立循环链表*/
for(int i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p>link=list; /*使链表循环起来*/
p=list; /*使p指向头节点*/

/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p;
p=p->link;
}

/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素:%4d ",p->data);
free(p);
p=r->link;
}
printf("n最后被删除的元素是:%4d",P->data);
}

解决方案概述 约瑟夫环 约瑟夫环-概述,约瑟夫环-解决
  

爱华网本文地址 » http://www.413yy.cn/a/8103560103/136984.html

更多阅读

2015谷歌无法访问,最新终极解决方案 终极定制学习解决方案

2015谷歌无法访问,最新终极解决方案——简介谷歌接二连三被屏蔽,2014年5月被封锁,10月再次被封锁,12月Gmail又被封锁,2015年1月下旬再次被封锁,额,我都服了,不多说,往下看:2015谷歌无法访问,最新终极解决方案——工具/原料博软G搜索(一款软件,自

vs2013解决方案资源管理器怎样靠左 vs2015解决资源管理器

vs2013解决方案资源管理器怎样靠左——简介用着 vs2013 编写代码,解决方案资源管理器一直是在左边的,有天突然跑到另一边去了,而且 ,自己拖来拖去怎么也拖不好,这该怎么办呢?vs2013解决方案资源管理器怎样靠左——工具/原料vs2013vs2013

Apache无法启动解决方案 win10 apache无法启动

Apache无法启动解决方案——简介Apache服务器无法使用原因Apache无法启动解决方案——工具/原料 原因一:80端口占用例如IIS,另外就是迅雷。我的apache服务器就是被迅雷害得无法启用!原因二:软件冲突装了某些软件会使apache无法启动如D

建行企业网银登陆不上解决方案 建行企业网银登陆密码

建行企业网银登陆不上解决方案——简介建行企业网银能给会计工作带来极大的方便,但有时会遇到登陆不上的情况,去营业厅咨询可能人家很忙,在网上咨询客服可能浪费时间,以下是我的解决经验,其实跟个人网银安装一样简单。建行企业网银登陆

声明:《解决方案概述 约瑟夫环 约瑟夫环-概述,约瑟夫环-解决》为网友酒伴清風分享!如侵犯到您的合法权益请联系我们删除