牡丹江市营商环境建设监督局网站,wordpress主题自动更新,net网站开发net网站开发,建设旅游网站的意义n个人编号为0…n-1围成一个圈,从0开始报数,每经过k个人那个人就退出这个圈不再报数,问最后留下来的人的编号.
朴素的做法当然是模拟,但是n,k的值一旦变得比较大的时候就难以解决问题.
我们考虑归纳的解决问题 当只有一个人的时候答案显然为0, 假设我们已知n-1个人的时候答案为…n个人编号为0…n-1围成一个圈,从0开始报数,每经过k个人那个人就退出这个圈不再报数,问最后留下来的人的编号.
朴素的做法当然是模拟,但是n,k的值一旦变得比较大的时候就难以解决问题.
我们考虑归纳的解决问题 当只有一个人的时候答案显然为0, 假设我们已知n-1个人的时候答案为ans[n-1],那么当人数为n时 显然的,我们首先得选一个人出去,这个人是(k-1)%n,然后我们从下一个起点(k%n)开始算起,我们不难发现问题变成了n-1个人的问题,因此ans[n](ans[n-1]k)%n
可是这样当n比较大的时候我们还是难以很快的解决问题.当n比较大的时候,前n/k次我们都是很容易确定的,因此我们直接考虑Josephus(n−n/k,k)Josephus(n-n/k,k)Josephus(n−n/k,k),直到n-n/k小于k,这样就能很快将复杂度变成O(k)级别的.根据刚才的想法,Josephus(n,k)Josephus(n−n/k,k)n/k∗kJosephus(n,k)Josephus(n-n/k,k)n/k*kJosephus(n,k)Josephus(n−n/k,k)n/k∗k就可以了吗?问题并不是这么简单. 我们看一个例子: 当n10,k4的时候我们选择两次以后的序列为 0 1 2 * 4 5 6 * 8 9 因此我们应该考虑n8的情况 2 3 4 * 5 6 7 * 0 1 假设n8时最后选出来的人为5,按照上面的式子原答案为(58)%103,但是正确的答案却应该是4,问题出在哪里呢? 原来我们选过以后的数列不是连续的了,必须考虑已经选过的没法再次选.我们观察,对于n8时,越过n%k后每4-1个数出现一个已经选择后的情况,需要加1
所以我们分类讨论: 设s’Josephus(n−n/k,k)Josephus(n-n/k,k)Josephus(n−n/k,k) 当s’n%k时,ss’n/k*k; 当s’n%k时,ss’-n%k(s’-n%k)/(k-1)
根据上面的讨论我们得到解决问题的算法:
int Josephus(int n,int k)
{if(n1) return 0;int ret;if(nk){ret0;for(int i2;in;i){ret(retk)%i;}return ret;}retJosephus(n-n/k,k);if(retn%k){retn/k*k;}else{ret-n%k;retret/(k-1);}return ret;
}
