首页 > ACM题库 > HDU-杭电 > HDU 3089-Josephus again-递推-[解题报告]HOJ
2014
03-01

HDU 3089-Josephus again-递推-[解题报告]HOJ

Josephus again

问题描述 :

In our Jesephus game, we start with n people numbered 1 to n around a circle, and we eliminated every k remaining person until only one survives. For example, here’s the starting configuration for n = 10, k = 2, The elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9. So 5 survives.The problem: determine the survivor’s number , J(n, k).

输入:

There are multiple cases, end with EOF
each case have two integer, n, k. (1<= n <= 10^12, 1 <= k <= 1000)

输出:

There are multiple cases, end with EOF
each case have two integer, n, k. (1<= n <= 10^12, 1 <= k <= 1000)

样例输入:

10 2
10 3

样例输出:

5
4

约瑟夫循环问题,不过此题的n很大,不能使用O(n)的递推方法,会TLE的

参考了网上的优化方法,是在O(n)的递推方法上优化的

观察递推式 num = (num+m)%i

当num,m比较小,而i比较大时,按照递推式,num的变化实际上是每次增加m的

而增加m的次数其实是可以计算出来的

所以当num+m >= i时我们使用普通递推式, 而num+m < i时我们可以使用下面的方法

设增加次数为x,x要满足下式

num+x*m < i+(x-1) //注意后面是x-1,因为每次都是当num增加完后才增加i的,可以用小数据模拟一下就清楚了

解次式可得

x < (i-num)/(m-1)

即x = floor((i-num)/(m-1))-1

这样我们就可以直接用下面的式子来跳过这些num递增的步骤了

num += x*m

i += x

但要注意此处的 i+x可能会大于n

这时候,其实我们已经可以求得最终解了,只要加个特判就可以,详细可以见注释

//约瑟夫循环问题
//编号从0开始
//假设n = 4, m = 2, k = 1
//第一个出队的人的编号是3
LL josephus(LL n, LL m, LL k)//分别为:人数,出圈步长,起使报数位置
{ 
	LL num = 0;
	if(m == 1)
	{
		return (n-1+k)%n;
	}
	for(LL i = 2; i <= n;)
		if((num+m) < i) 
		{
			LL temp = (i-1-num)%(m-1)? (i-1-num)/(m-1): (i-1-num)/(m-1)-1;
			if(i+temp > n)   //当i+temp > n时特判
			{
				num += (n+1-i)*m;    //直接得到最终解
				break;
			}
			num += temp*m;
			i += temp;
		}
		else
		{
			num = (num+m)%i;  //普通递推
			++i;
		}
	num = (num+k)%n;
	return num;
}








参考:http://blog.csdn.net/gyarenas/article/details/9073045


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。