约瑟夫环问题

看解二,妙。
http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html

妙处在于如何找到子问题,并且找出子问题和原问题的关联。

1, 2, 3, … , k, k+1, k+2, … , n

子问题f(n-1)是:
1, 2, 3, … , k, k+1, … , n-1

但如何得到这个子问题呢?
我的错误想法是将k+1变为k, k+2变为k-1, … , n变为n-1

正确的子问题是这样得到的:
k+1, k+2, … , n, 1, 2, … , k-2, k-1

然后做变换:
x -> x
k+1 -> 1
k+2 -> 2
...
n -> k
...
k-2 -> n-2
k-1 -> n-1

变换公式是:x = (x-k+n)%n
变回来的公式是:x = (x`+ k)%n

所以有递归式:f(n) = (f(n-1)+k)%n, f(1)=1

Leave a Reply