NOIP算法:约瑟夫问题(C++)
发布时间:2023-02-22 11:39:00 来源:文档文库
小
中
大
字号:
约瑟夫问题也称为约瑟夫斯置换,在计算机编程的算法中,类似问题又称为约瑟夫环,又称“丢手绢问题”。一、一般形式1.N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。2.有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。算法思路:模拟(1)由于对于每个人只有在与不在环中两种状态(2)开始时每个人都在环中(3)模拟过程,直到环中只剩下一人。方法一:设立标记,每个元素标记为出队或在队中http://noi.openjudge.cn/ch0302/1748/#include#include#include#includeusingnamespacestd;constintmaxn=310;inta[maxn];intmain({intp,num,cnt,n,m,tmp;while(scanf("%d%d",&n,&m!=EOF&&(n!=0||m!=0{memset(a,0,sizeof(a;p=1;for(num=1;num<=n;num++{//一共要数n轮for(cnt=1;cnt<=m;cnt++{//每一轮数到mwhile(a[p]==1p=p%n+1;//如果指针所指已有标记指针后移tmp=p;//此时p指向环中的第cnt只猴子p=p%n+1;//指针后移}a[tmp]=1;//将第m只猴子标记}printf("%d\n",tmp;//第n轮的第m只猴子就是解}return0;}方法二:使用数组模拟链表codevs1282约瑟夫问题http://codevs.cn/problem/1282/#include#include#include#include#includeusingnamespacestd;constintmaxn=30050;inta[maxn];intmain({intn,m,i,j,p;scanf("%d%d",&n,&m;for(i=1;ifor(i=1;i<=n;i++{for(j=1;jprintf("%d",a[p];a[p]=a[a[p]];}return0;>>>>}
二、深入探讨对于约瑟夫问题,若需要依次记录退出编号的情况:优化方法是使用线段树维护区间和,并进行单点更新。具体方法见线段树章节。对于约瑟夫问题,若只需要求胜利者编号,而不需依次记录退出编号的情况:优化1:把问题稍微改变一下,并不影响原意:问题描述:n个人(编号0~(n-1,从0开始报数,报到(m-1的退出,剩下的人继续从0开始报数。求胜利者的编号。则第一轮报数出队者的编号:(m%n-1+n%n;第二轮报数由剩下的n-1个人组成了一个新的约瑟夫环,从k=m%n开始报数;其编号由第一轮的k,k+1...n,0,1,...k-2,变化为0,1,.........n-1若第二轮出队编号为x,则其在第一轮中的编号应该为x’=(x+k%n=(x+m%n推广到i-1个人报数若胜利者编号为x,则其在