l*********y 发帖数: 142 | 1 long long Joseph(long long n, int k)
{
long long d = n/k;
long long res = Joseph(n-d, k);
res -= n % k;
if (res < 0) res += n;
else res += res / (k-1);-------->这是要干什么?
return res;
}
没明白这句话,网上也没找到清楚的答案,wiki上说的很含糊,谁给解释以下,谢谢了 |
l*********y 发帖数: 142 | 2 ding
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : long long Joseph(long long n, int k) : { : long long d = n/k; : long long res = Joseph(n-d, k); : res -= n % k; : if (res < 0) res += n; : else res += res / (k-1);-------->这是要干什么? : return res; : } : 没明白这句话,网上也没找到清楚的答案,wiki上说的很含糊,谁给解释以下,谢谢了
|
I*********g 发帖数: 93 | 3 杀完快一圈的时候还剩n-d 个人,从编号 n-n%k 的人又会重复这个过程,
所以先递归求解(n-d, k)的解,然后推(n,k)的解
对(n-d, k)的解x有两种情况
(1)编号 < n%k, 这说明原来就是从编号 n-n%k到尾部的那些人
所以x+ n - n%k就是解
(2)不然就要看插多少个人
每k-1个人插一个人, 所以 += res/k-1 |
l*****a 发帖数: 559 | 4 赞。
另lz抄少了n/k = 0的情况。
【在 I*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 杀完快一圈的时候还剩n-d 个人,从编号 n-n%k 的人又会重复这个过程, : 所以先递归求解(n-d, k)的解,然后推(n,k)的解 : 对(n-d, k)的解x有两种情况 : (1)编号 < n%k, 这说明原来就是从编号 n-n%k到尾部的那些人 : 所以x+ n - n%k就是解 : (2)不然就要看插多少个人 : 每k-1个人插一个人, 所以 += res/k-1
|
b*****o 发帖数: 715 | 5 更简单的答案参看
http://zhedahht.blog.163.com/blog/static/2541117420072250322938
lz贴的这个算法,想法是有的,但是细节上有不少问题。
需要在最开始加上边界处理:
while(k>n) k -= n;
if (n==1) return 0;
if (k==1) return n-1; |