NOIP算法：约瑟夫问题(C++)
发布时间：2023-02-22 11:39:00 来源：文档文库
小
中
大
字号：
约瑟夫问题也称为约瑟夫斯置换,在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”。一、一般形式1.N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。2.有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。算法思路：模拟（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 