（NGU）100分求解“约瑟夫问题”
关于“约瑟夫”问题
有看过“具体数学”的，我有一处看不懂，懂的人帮忙解释下
J(2n) = 2J(n) - 1 的推导过程
约瑟夫算法可以用循环链表和数组来解(这两个我会)，下面2个程序都是用来解决该算法的，其中第（2）直接给出答案，每个程序都有证明和讲解，我实在看不懂(看不懂的地方有标记，只要分析有带标记的地方就行)，谁帮忙分析下！(分析得非常好的，我另外开贴送100)
程序1(递归法):
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n;
int m;
int i = 0;
int p;
scanf("%d%d", &n, &m);
while (++i <= n )
{
p = i * m;
while (p>n)
{
p = p - n + (p-n-1) / (m-1);
}
printf("%d\n", p);
}
return 0;
}
程序2(递推法):
#include <stdio.h>
int main(void)
{
int i;
int s = 0;
int n;
int m;
scanf("%d%d", &n, &m);
for (i = 2; i <= n; i++)
{
s = (s + m) % i;
}
printf("最后的获胜者是: %d\n", s + 1);
return 0;
}
程序1证明：
(完全不知所云)
假设数到第p个数时遇到的数, 和数到第x个数到遇到的数一样,且p - n < x < p,而且x % m != 0, 否则会被跳过和第个p数遇到的数肯定不一样,那么说明数了x个数之后再数一圈就数到了第p个数,而数一圈数过的数应该是n减去要跳过的数,因为已经数过了x个数,所以要跳过[x / m]个数( []表示取整数部分 ),所以x + n - [x / m] = p
问题转化为: p - n = x - [x / m]...(1),且 x % m != 0, p - n < x < p, 求解x
因为x % m != 0 => x / m - 1 < [x / m] < x / m
=> x - x / m + 1 > x - [x / m] > x - x / m
=> [x - x / m + 1] >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] >= [x - x / m] + 1
=> [x - x / m] + 1 = x - [x / m]
( 代入(1)式 )=> p - n - 1 = [x - x / m] = [x * ( m - 1 ) / m] ... (2)
因为x % m !=0 且 ( m - 1 ) % m != 0 => ( x * ( m - 1 ) ) % m != 0
由(2)式 => 0 < x * ( m - 1 ) - m * ( p - n - 1 ) <= m - 1
由左边: => m * ( p - n - 1 ) < x * ( m - 1 )
=> m * ( p - n - 1 ) / ( m - 1 ) < x
=> [m * ( p - n - 1 ) / ( m - 1 )] < x
=> [m * ( p - n - 1 ) / ( m - 1 )] + 1 <= x ...(3)
由右边: => x * ( m - 1 ) - ( m - 1 ) <= m * ( p - n - 1 )
=> ( x - 1 ) * ( m - 1 ) <= m * ( p - n - 1 )
=> x - 1 <= m * ( p - n - 1 ) / ( m - 1 )
=> x - 1 <= [m * ( p - n - 1 ) / ( m - 1 )]
=> x <= m * ( p - n - 1 ) / ( m - 1 ) + 1 ...(4)
由(3),(4) => x = [m * ( p - n - 1 ) / ( m - 1 )] + 1
= [ p - n - 1 + ( p - n - 1 ) / ( m - 1 )] + 1
= p - n - 1 + [( p - n - 1 ) / ( m - 1 )] + 1
= p - n + [( p - n - 1 ) / ( m - 1 )]
由于计算机算整数除法直接就取整了,所以递归时就写成
p = p - n + ( p - n - 1 ) / ( m - 1 )
程序2证明：
Josephus(约瑟夫)问题的数学方法(转)约瑟夫 （转）
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: (下面这句看不懂)
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：(下面转换看不懂)
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：
#include <stdio.h>
main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。
[解决办法]
程序2的证明可以看懂，n个人报数，编号为0，1，2.....n-1,n,第一次报数淘汰了编号为(k-1)的人，第2次报数则从编号为k的人开始，此时报数对应的编号为:k,k+1,k+2......n-1,n-1,0,1,2...k-2,k-1,最后的这个编号为k的人第一次被淘汰了，然后可以找出n个人报数的结果和(n-1)个人之间的关系，
k -- > 0
k+1 -- > 1
k+2 -- > 2
...
...
k-2 -- > n-2
k-1 -- > n-1
也就是n个人报数的结果等于(n-1)个人报数的结果+m,当然还要考虑到总数不能大于当前报数的总人数，而且n个人报数的结果必然在这(n-1)个人中，所以有f[1]=0;
f[i]=(f[i-1]+m)%i; (i >1)
[解决办法]
J(2n)=2J(n)-1 的推导：
设J(n)表示：n个人排成一列，1212地报数，最后剩下的人的原始标号(原始标号：即在最开始排队时的序号)。
原排列设为{Ai}： 1 2 3 4 ...... 2n
考虑J(2n)。
当1212地报数一圈回到原排列{Ai}的开头位置的1时，显然，有n人出列。
另外，容易知道：剩下的n人的原始标号，排成的形式是：1 3 5 7 ...... 2n-1。
将这个排列记为{A'i},显然，最后剩下的那个人必然在{A'i}中。
现在，开始第二圈报数。
在{A'i}中，人的原始标号不是连续的，但是，在{A'i}中的人的下标是连续的。
{A'i}中人的原始标号与人的下标：
原始标号：1 3 5 7 ...... 2n-1
下标 ：1 2 3 4 ...... n
由上面的表，对比，知道：原始标号=2*下标-1。 （1）
现在，考虑J(n)，也就是排列{Bi}： 1 2 3 4 ...... n 的报数结果。
容易发现，{A'i}中的人的下标组成的排列就是{Bi}。
因此，若知道{Bi}1212报数，剩下的原始标号是x，也就是J(n)=x。
那么由关系（1），知道：J(2n)=2*x-1，
即:J(2n)=2J(n)-1。
