HDOJ 1443 约瑟夫环的最新应用分析详解

时间:2021-05-20

k个男生和k个女生站成一列,前面k个是男生,后面k个是女生,从第一个男生开始报数,报到队列最后一个同学,循环到队首继续报,并且如果一个同学报到的数是m,这个同学就出列,然后后面的同学继续从1开始报数,现在求一个数m,使k个女生全部出列,而男生没有出列。

输入:男生女生的个数k(男生女生人数相等都为k,输出:m值
例: 输入:2,输出:7
输入:4,输出:30

本题是约瑟夫环变形 先引入Joseph递推公式,设有n个人(0,...,n-1),数m,则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人(当前序列编号为0~(n-i));
拿个例子说:K=4,M=30;
复制代码 代码如下:
f(0)=0;
f(1)=(f(0)+30-1)%8=5; 序列(0,1,2,3,4,5,6,7)中的5
f(2)=(f(1)+30-1)%7=6; 序列(0,1,2,3,4,6,7)中的7
f(3)=(f(2)+30-1)%6=5; 序列(0,1,2,3,4,6)中的6
f(4)=(f(3)+30-1)%5=4; 序列(0,1,2,3,4)中的4
........

依据题意,前K个退出的人必定是后K个人,所以只要前k轮中只要有一次f(i)<k则此m不符合题意。
注意:
本题有几点需要注意,否则很容易超时;
第一点、运用公式j=(j+m-1)%(n-i),推导出下一个出现的元素在第几号位置,如果j<k的话,不符合题意。
第二点、就是m,当只剩下k+1个数的时候,则上一个消失的数一定是在目前仅剩的bad左边或者是右边,所以m%(k+1)==0或者1
有了这两个条件,可以加快程序的速度。。。
完整的实现代码如下:
复制代码 代码如下:
#include "stdio.h"
#include "stdlib.h"
int x[15];

int test(int k,int m)
{
int i,j=0,len=k*2;
for(i=0;i<k;i++)
{
j=(j+m-1)%(len-i); //约瑟夫环公式
if(j<k)
return 0; //遇到前k轮中有小于k的直接返回0
}
return 1;
}

void Joseph(void)
{
int m,k;
for(k=1;k<15;k++)
{
m=k+1;
while(1)
{
if(test(k,m)) // m%(k+1)==0的情况
{
x[k]=m;
break;
}
if(test(k,m+1)) // m%(k+1)==1的情况
{
x[k]=m+1;
break;
}
m+=k+1;
}
}
}
int main(void)
{
int k;
Joseph();
while(scanf("%d",&k),k)
printf("%d\n",x[k]);
system("pause");
}

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章