约瑟夫环推广
上一节课说到,约瑟夫环问题的解是
其中
将 n 写成二进制可以发现, 就是 n 的二进制循环左移1位。
现在做一下推广,求解如下递推式:
可以设
同样,令
可以解出
再从二进制角度理解一下,将递推式继续推广:
可以得到解为
上一节课说到,约瑟夫环问题的解是
其中
将 n 写成二进制可以发现, 就是 n 的二进制循环左移1位。
现在做一下推广,求解如下递推式:
可以设
同样,令
可以解出
再从二进制角度理解一下,将递推式继续推广:
可以得到解为