Concrete Mathematics R. L. Graham, D. E. Knuth, O. Patashnik 《Concrete Mathematics》，1.3 THE JOSEPHUS PROBLEM R. L. Graham, D. E. Knuth, O. Patashnik Sixth printing, Printed in the United States of America 1989 by Addison-Wesley Publishing Company，Reference 1-4 pages 详细数学 R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克 《详细数学》，1.3，约瑟夫环问题 R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版企业，1989 年，引用 8-16 页 而且3将是下一个出局。这个就像是以n 个人开始情况，除了每个人编号变为两倍减一。那就是， J(2n) = 2J(n)-1; 当 n ≥1: 我们现在能够快速计算一下当n 比较大时候值。比如，我们知道 J(10) = 5，所以 J(20) = 2J(10)-1 = 2*5-1 = 9: 一样可知 J(40) = 17，深化我们能够推算出 J(5*2M )=2M+1 +1 不过，奇数情况呢？当有2n+ 1个人时候， 编号是1人会在第2n 个人出局后紧接着出局，然后，我们剩下 我们再次取得了形如n 个人情况，不过这次他们编号是两倍加一。所以 J(2n+ 1) = 2J(n) + 1; 当 n ≥1; 与等式 J(1) = 1组合，我们得到一个定义了J 全部取值递推式: J(1) = 1; J(2n) = 2J(n)-1; 当 n ≥1; J(2n+ 1) = 2J(n) + 1; 当 n ≥1; 这个公式不是从J(n-1)计算 J(n)，这个递归式愈加“高效”，因为他以 2为因子使 n 递减了二分之一或更多。我们能够计算J(1;000;000)，如上所表示，我们只要应用19次(1)式。不过，我们依旧要寻找一个闭合形式公式，因为那样会愈加快速和更有意义。总之，这是非常主要事情。 每个 bi 取值是 0 或 1，且最高位 bm 是 1. 回想一下 n=2M+L 我们先后得到以下表示式， n=(1bm-1bm-2...b1b0)2 L=(0bm-1bm-2...b1b0)2 2L=( bm-1bm-2...b1b0)2 2L+1=(bm-1bm-2...b1b01)2 J(n)= (bm-1bm-2...b1b0m)2 (最终一个式子是因为 J(n) = 2l+ 1 以及 bm=2L+1 以及bm=1。) 我们已经证实 J((bm-1bm-2...b1b0)2)= (m-1b bm-2...b1b0m)2; (3) 这么，用计算机编程专业术语解释就是我们从 n 计算 J(n)只需要做一位循环左移！多么奇妙。比如，假如 n= 100 =(1100100)2, 那么 J(n) = J(1100100)2=(1001001)2, 也就是 64 + 8 + 1 = 。假如我们从一开始就一直用二 73 进制方法讨论，我...
