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 的大作中提到】
: 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 的大作中提到】
: 杀完快一圈的时候还剩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; |
