频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
ACM:数论专题(3)——约瑟夫问题
2016-04-21 09:25:30         来源:octopusflying的专栏  
收藏   我要投稿

(p.s: 以前做约瑟夫问题都是用链表模拟,今天发现了一个效率更高的方法,受教了。。。)

 

题目描述:

小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长。

首先N个候选人围成一个圈,依次编号为0..N-1。然后随机抽选一个数K,并0号候选人开始按从1到K的顺序依次报数,N-1号候选人报数之后,又再次从0开始。当有人报到K时,这个人被淘汰,从圈里出去。下一个人从1开始重新报数。

也就是说每报K个数字,都会淘汰一人。这样经过N-1轮报数之后,圈内就只剩下1个人了,这个人就作为新的班长。

举个例子,假如有5个候选人,K=3:

初始 0: 0 1 2 3 4
从0号开始报数,第1次是2号报到3
1: 0 1 - 3 4 // 0 1 2, 2号候选人淘汰
从3号开始报数,第2次是0号报到3
2: - 1 3 4 // 3 4 0,0号候选人淘汰
从1号开始报数,第3次是4号报到3
3: 1 3 - // 1 3 4, 4号候选人淘汰
从1号开始报数,第4次是1号报到3
4: - 3 // 1 3 1, 1号候选人淘汰

题目要求给定人数n和k值后,求出最后获选班长的人的编号。

解答:
本题最原始的办法是用环形链表模拟所有候选人的编号,当一个候选人淘汰时就将对应的节点从链表中删除,直到整个链表中只剩下一个节点时结束。这样的算法的时间复杂度为O(nk),效率比较低,并且如果n很大的话,会占用庞大的内存空间,这是不现实的。
下面给出两种基于递推的解法:

·递推方法(1):
设f(x)为给定k值的情况下,有x个候选人时,最后获选的人的编号。显然:
f(1) = 0 (只有1个人候选人时,他就是最后的获选者).
当 x>1 时,f(x)的值可以用下面的递推公式计算:
f(x) = (k + f(x - 1)) % n.
该公式的证明如下:如果有n个候选人,则第一个淘汰的候选人一定的编号为k-1的候选人,如下图:

\

淘汰掉编号为k-1的候选人后,还剩n-1个候选人,此时对这n-1个人重新编号,编号为k的候选人改为编号0,编号为k+1的候选人改为编号1 ...... 编号为n-1的候选人则改为编号n-k-1,然后,编号为0的候选人改为编号n-k,编号为1的候选人改为n-k+1 ...... 编号为k-2的候选人则改为编号n-2。如下图:

\

此时,假设已经知道了n-1个候选人时的最后获选人的编号,那么此时将该编号作为新编号再转化为旧编号时,就是n个候选人时最后获选的人的编号。
可以发现:在mod n的范围内,新旧编号的差别在于旧编号比新编号增加了一个k值,即:
(new + k) % n = old.
而对应到递推式中,旧编号就是要求的编号f(n),而新编号就是已经求得的结果f(n-1),于是:
f(n) = (f(n-1) + k)%n
于是,以上递推式得证。
利用该定理,可以在O(n)的时间内得到结果。

·递推方法(2):
第2种递推方法是对第一种递推方法的改进,使得f(n)的值不再直接从f(n-1)求得,在枚举计算时实现了一定距离的“跳跃”。方法如下:
对于n个候选人,当对所有的候选人扫描一次后,所有编号取模k的结果为k-1的候选人均被淘汰。即:满足编号 s % k = k-1时,就会被淘汰,此时,共淘汰了n-n/k个人。如下图:

\

此时,和方法1类似,从最后一个被淘汰者之后重新设置编号,如下(假设图中3k-1之后没有淘汰者):

\

此时,观察新旧编号的关系,可以发现:图中绿色部分的编号关系为新编号加n-n%k取模n后就是旧编号:
old = new + n - n%k
而前面蓝色的部分,新旧编号的关系则不是那么明显,主要的原因在于蓝色部分的序列并不是连续的。可以看到,删除的数据把整个蓝色部分划分为为若干个长度为k-1的连续序列。所以这部分的新旧编号的转换关系则由新编号覆盖了多少个k-1序列来决定,每覆盖一个k-1序列,那么就编号就要在原有的转换结果(方法1中的转换方式)的基础上再偏移1位。
因此:蓝色部分的转换公式如下:
old = (new + n - n%k) % n+ (new - n % k) / (k - 1)
= new - n%k + (new - n%k) / (k-1)
以上是第2种递推计算方法,该方法要求n必须不小于k。

因此在解答本题时的思路便是:首先判定n是否大于k,如果n>k,那么利用方法(2)将f(n)转换为一个较小规模的问题f(n - n/k),反复运用方法(2)直到n
利用以上算法就可以在O(n)的时间复杂度下完成求解。


输入输出格式:
输入:首先输入一个正整数t表示测试数据的组数;接下来的t行每行为2个整数n,k。
输出:对于每组测试数据输出一行,表示最后获选者的编号。

数据范围:
1≤t≤100
2≤n≤1,000,000,000
2≤k≤1,000

程序代码:

 

/****************************************************/
/* File        : Hiho_Week_94.cpp                   */
/* Author      : Zhang Yufei                        */
/* Date        : 2016-04-19                         */
/* Description : HihoCoder ACM program. (submit:g++)*/
/****************************************************/

#include

/*
 * This function deals with one test case.
 * Parameters:
 *		None.
 * Returns:
 *		None.
 */
void function (void);

/*
 * This function get the result of the given n and k.
 * Parameters:
 *		@n: The number of candidate.
 *		@k: The 'k' parameter in this question.
 * Returns:
 *		The result for the given n and k.
 */ 
int compute(int n, int k);

/*
 * The main program.
 */
int main (void) {
	int t;
	scanf("%d", &t);
	
	for(int i = 0; i < t; i++) {
		function();
	}
	
	return 0;
}

/*
 * This function deals with one test case.
 * Parameters:
 *		None.
 * Returns:
 *		None.
 */
void function (void) {
	int n, k;
	scanf("%d %d", &n, &k);
	
	printf("%d\n", compute(n, k)); 
}

/*
 * This function get the result of the given n and k.
 * Parameters:
 *		@n: The number of candidate.
 *		@k: The 'k' parameter in this question.
 * Returns:
 *		The result for the given n and k.
 */ 
int compute(int n, int k) {
	if(n == 1) {
		return 0;
	} 
	
	if(n < k) {
		return (k + compute(n - 1, k)) % n; 
	} else {
		int r = compute(n - n / k, k);
		if(r < n % k) {
			return r - n % k + n;
		} else {
			return r - n % k + (r - n % k) / (k - 1);
		}
	}
} 


 

点击复制链接 与好友分享!回本站首页
上一篇:[从头学数学] 第187节 仗剑题海载酒行(下)
下一篇:【hdu 5521】【 2015ACM/ICPC亚洲区沈阳站重现赛】Meeting题意&题解&代码
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站