快捷搜索: 脱发

【算法】约瑟夫环原理及其公式

问题描述

将n个人围成一个圈,从1开始依次数数,数到k或者k的倍数时,这个人出局,如此循环直到环中只剩一个人的时候这个人获胜

算法原理

可以把这个圈想想成一条直线,假设一开始有11人,k=3

将这11个人从1到11进行编号

从1开始报数,此时的人数是11

第一个被淘汰出局的是3

注意,这里淘汰到三继续往后数的话,就相当于4是第一个人,再从1开始计数,此时的人数为10

可以看出11个人从1开始报数,可以等效为10个人从4开始报数,不过少一个3号,但是我们找的是对应的下标,而不是具体的人,所以并没有什么影响

数次循环往复,相当于每淘汰一个人,数组整体向前移动k位(此处k=3,所以是移动三位),因为是整体移动,说明最后获胜的人也是向前移动k位,当已知11个人k=3时最终获胜的人的标号为6(数组中的下标为5)时,易推出10个人k=3时最终获胜的人为(6-3)%10(当前的人数)

可以推出,每增加一个人后,数组整体向后移动k位,这样n就可以从1开始通过递归推出

每当淘汰一个人,数组整体向前移动k位

每当增加一个人,数组整体向后移动k位

公式为

f(n,k)=(f(n-1,k)+k)%n 求出的是下标位置,而不是这个人的编号,如果是编号的话还需要加1

(下标是从0开始的,编号是从1开始的)

当n=1时,代表只有一个人,获胜者就是这个人,他的编号是1,但是下标位置为0

当n=2时,f(1,k)=0,f(2,k)=k%n;

...

依次类推即可求出f(n,k);

最后结果要+1,因为求出来的结果是下标位置,而不是这个人的编号

核心代码实现
int cir(int n,int k)
{
	int p=0;
	for(int i=2;i<=n;i++)    //因为i==1开始的时候就是p=0,所以直接让p=0,跳过第一个
	{
		p=(p+k)%i;
	}
	return p+1;        //返回的是下标位置,+1才是人的编号
}
例题
经验分享 程序员 微信小程序 职场和发展