好吧，我正在努力学习克努特的具体数学，有些例子我还不明白。
j（n）=2*j（n/2）-1
这是第一章它专门为那些可能熟悉具体数学的人解决了约瑟夫斯问题。有一个解决方案，但绝对没有解释。
我试着用迭代法来解决它。这是我到目前为止想到的
j（n）=（2^k）*j（n/（2^k））—（2^k-1）
我被困在这里了。任何帮助或提示将不胜感激。
最佳答案
我要先回忆一下约瑟夫斯问题。
我们有N个人围成一圈。刽子手将以以下方式处理圆圈：
刽子手从I=1位置的人开始
在我的位置上，他饶了我但杀了我的跟班
他一直这样直到只有一个人活着
通过快速查看这个过程，我们可以看到，在第一次运行中，每个处于平衡位置的人都将被杀死。当所有的“偶数”都死了，剩下的人是谁？这取决于n的奇偶性。
如果n是偶数（比如n=2i），那么剩下的人是1,3,5，…，2i-1。剩下的问题是一个i人的圆，而不是n人的圆。让我们介绍一个映射图，甚至是“新”圆中的位置和n人的圆中的初始位置之间的映射图。
map偶（x）=2.x-1
这意味着在新圆的位置x的人在最初的圆的位置2.x-1如果幸存者在新圆圈中的位置是j（i），那么某人必须占据的位置才能在n=2.i的圆圈中生存。
马普文（j（i））=2.j（i）-1
我们有第一个递归规则：
对于任意整数n：
j（2.n）=2.j（n）-1
但如果n是奇数（n=2.j+1），那么第一次跑完就杀死了所有的“evens”，刽子手在n的位置，n的跟随者是1……所以下一个被杀的是1。幸存者是3，5，…，2J+1，刽子手继续前进，好像我们有一个J人的圈子。映射与偶数情况有点不同：
mapodd（x）=2.x+1
3是新的1，5是新的2，等等…
如果幸存者在j人圈中的位置是j（j），那么想要在n=2j+1的圈中生存的人必须占据j（2j+1）的位置：
j（2j+1）=mapodd（j（j））=2.j（j）+1
绘制第二个递归关系：
对于任何整数n，我们有：
J（2.n+1）=2.J（n+1
从现在起，我们可以使用2个递归关系计算任意整数n的j（n）。但如果我们再看远一点，我们可以让它更好…
因此，对于每个n=2k，我们有j（n）=1。好吧，那太好了，但是其他数字呢如果你写下第一个结果（比如n=20），你会看到序列看起来是伪周期的：
1 2 3 4 5 6 7 8 9 10 11
1 1 3 1 3 5 7 1 3 5 7
从一个二次方开始，似乎每一步位置增加2，直到下一个二次方，我们从1开始…因为，给定一个整数n，有一个唯一的整数m（n），使得
2m（n）≤n设s（n）为整数，使得n=2m（n）+s（n）（我称之为“s”表示“移位”）。
我们观察到的数学翻译是j（n）=1+2.s（n）
让我们用强归纳法来证明它。
对于n=1，我们有j（1）=1=1+2.0=1+2.s（1）
对于n=2，我们有j（2）=1=1+2.0=1+2.s（2）
假设任意k的j（k）=1+2.s（k），使得k∈[1，n]，我们证明j（n+1）=1+2.s（n+1）。
我们有n=2m（n+1）+s（n+1）。显然，2m（n）是偶数的（除了n=1的平凡情况），因此n的奇偶性由s（n）携带。
如果s（n+1）是偶数，那么我们表示s（n+1）=2j。
j（n+1）=2.j（（n+1）/2）-1=2.j（2m（n+1）-1+j）-1
由于该语句对于任何k∈[1，n]都是真的，因此对于1≤k=（n+1）/2J（n+1）=2。（2j+1）-1=2.s（n+1）+1
我们同样可以解决这个奇怪的案子。
为任意整数n建立公式：
j（n）=2.s（n）+1，其中m（n），s（n）∈_是唯一的整数
2m（n）≤n其他术语：m（n）=ln2（n）⌋和s（n）=n-2⌊ln2（n）⌋
关于algorithm - 解决复发，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16045494/