首页 > 代码库 > 算法:约瑟夫环问题
算法:约瑟夫环问题
算法:约瑟夫环问题
【写在前面】
由于本人天生驽钝,所写代码和描述可能不堪入目,高手请移步。但是我一直在努力记录一下有用的知识点,给自己给朋友用,只是希望对大家有帮助。
【问题描述】
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从第一个人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,求最后一个出圈的人的标号。
【代码】
void JOSEF(int n,int m) //:n个人,m出列{ int people[n+1]; //我们定义的数组大小为n+1,因为我们不想涉及到0的操作,我们只取1到n这个范围内的标号,忽略0 for(int i=1;i<=n;i++) people[i]=i; //将数组内(除0)的每一个元素进行初始化,其实非0即可,值无所谓。 int flag=n-1; //我们要在数组里面删除多少个元素呢?答案是n-1个。剩下的一个为最后出圈的那一个 int p=1; //用来指示元素下标 int count=0; //计数器 while(flag) //没有删完的情况下继续 { if(people[p]==0) //如果p所指的元素为0,表示该元素已经出圈,可以跳过 { if(p==n) //这段代码就是让尾部连接头部 p=1; else p++; continue; } count++; //找打一个不为0的元素 if(count==m) //如果我们找够m个,就将这个元素出圈,也就是设为0 { people[p]=0; flag--; //待出圈的元素-1 count=0; //重新开始数 } if(p==n) //这段代码就是让尾部连接头部 p=1; else p++; }
for(int i=1;i<n;i++) //那个值不为0元素的下标的就是最后一个出圈的人的序号
{
if(people[i]!=0)
{printf("目标为%d\n",i);break;}
}
算法:约瑟夫环问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。