【正文】 17，我們會更早些看到這個模式：舉個例子，當(dāng)n = 100 = (1100100)2的時候，我們原來的Josephus取值為α = 1，β = ?1，且γ = 1帶入后構(gòu)造結(jié)論跟之前一樣。這個遞歸式的展開式，二進制表示如下：f (bmbm?1...b1b0)2 = 2f (bmbm?1...b1)2 + βb0 = 4f (bmbm?1...b2)2 + 2βb1 + βb1 = 2mf (bm)2 + 2m?1βbm?1 + . . + βb0 = 2mα + 2m?1βbm?1 + . . .+ βb0.假設(shè)我們現(xiàn)在不管162的基數(shù)標(biāo)記，隨便讓數(shù)字取代二進制中的0和1。我們知道原來的遞歸式J有一個神奇的解法，也就是二進制：J (bmbm?1...b1b0)2 = (bm?1...b1b0bm)2, 當(dāng) bm = 1.那么，廣義的Josephus遞歸式也能如此神奇么？當(dāng)然，為什么不呢？我們可以把這個廣義的遞歸式(4)重寫成如下形式f(1) = α。我們需要跟獨立的參數(shù)數(shù)量(在這個例子中是三個，α，β和γ)同樣多的獨立的特解。這個過程已經(jīng)接近于展示一個驚奇、有用的repertoire method來解決遞歸式問題。A(n) ? B(n) ? C(n) = 1。我們已經(jīng)知道f(n) = n在這個例子中是解，因為遞歸式(4)為每個n的取值唯一的定義了f(n)。 n + γ。 n + β。同樣我們可以帶入f(n) = n：1 = α。 1 + γ。 1 + β。將常函數(shù)f(n) = 1帶入遞歸式(4)可得1 = α。接下來，我們將反用遞歸式(4)以及解法(6)式。A(2n + 1) = 2A(n)；當(dāng) n ≥ 1。13讓我們通過具體的例子α = 1，β = γ = 0來說明這個方法，當(dāng)假設(shè)f(n)等于A(n)：遞歸式(4)變?yōu)锳(1) = 1。使用數(shù)學(xué)歸納法證明(6)式和(7)式并不是一件非常艱難的事情，但是這個計算過程是繁雜而且沒有技術(shù)含量的。B(n) = 2m ? 1 ? l。而γ的系數(shù)則從0開始每次增加1。)以f (1) = α開始計算，我們可以構(gòu)建出來接下來的廣義形式遞歸式的對n取值較小的表： 可以看出來α的系數(shù)是小于n的最大的2的冪。f (2n) = 2f (n) + β, 當(dāng) n ≥ 1。如果我們的問題得到一個像(1)的遞歸式，但是常數(shù)不同，將會發(fā)生什么？我們可能就沒有這么幸運能猜到答案了，因為答案可能很復(fù)雜。(結(jié)果都是減半)。)所以有無窮多個解可以滿足J(n) =n/2，以如下形式開頭：注意這個模式中最右邊的一列。 2l+ 1 =(2m+l)/2 l =1/3(2m2)如果這個式子l =1/3(2m2) 是一個整數(shù)，那么n=2m+l將會是一個解，因為l會小于2m 不難驗證當(dāng)m是奇數(shù)，2m2是3的倍數(shù)，但當(dāng)m是偶數(shù)的時候不成立。讓我們回到這個問題的最初猜想，也就是當(dāng)n是偶數(shù)的時候J(n) =n=2。同樣的8或更多J(J(...J(101101101101011)2...)) = 210 ? 1 = 1023。這種循環(huán)位移特點使得很容易觀察出來這個固定的值將會是多少：迭代這個方法足夠多的次數(shù)，總會產(chǎn)生每個位都是1的模式，其值為 2v(n)1 , 當(dāng)v(n)是1位在整個二進制序列的出現(xiàn)的次數(shù)。事實上，根據(jù)定義，J(n)必須總是≤n, 因為J(n)是存活著的人的編號；所以如果J(n) n我們決不可能通過繼續(xù)迭代回溯到n。但是實際上不是。如果我們從一開始就一直用二進制方法研究，我們可能會立即就發(fā)現(xiàn)這個模式。 (3)這樣，用計算機編程的專業(yè)術(shù)語解釋就是我們從n計算J(n)只需要做一位循環(huán)左移！多么神奇。也就是 n=bm2m+bm12m1+....b12+b0每個bi 取值是0或1，且最高位bm 是1. 回想一下n=2M+L我們先后得到如下表達式， n=(1bm1bm2...b1b0)2 L=(0bm1bm2...b1b0)22L=( bm1bm2...b1b0)22L+1=(bm1bm2...b1b01)2J(n)= (bm1bm2...b1b0m)2(最后一個式子是因為J(n) = 2l+ 1以及bm=2L+1以及bm=1。在我們尋找解法的時候，2的冪起到了重要的作用，所以很自然的，我們想用2的基數(shù)表示n和J(n)。所以，在這節(jié)的余下部分，我們將會研究我們的解法(2)式以及研究遞歸式(1)的一些擴展。我們再說點輕松的：每解決一個問題都可以泛化，使得可以應(yīng)用一大類問題。為了展示解法(2)式，讓我們來計算一下J(100)。奇數(shù)的情況證明方法類似，當(dāng)2M+L=2L+1。且通過(1)式和歸納法假設(shè)可得J(2M+L)=2J(2M1+L/2)1=2(2L/2+1)1 = 2l+ 1。通過l是奇數(shù)還是偶數(shù)，這次的歸納證明分兩部分。如我們以前使用的數(shù)學(xué)歸納法一樣，但是這次我們的數(shù)學(xué)歸納是基于變量m的。所以，如果我們把n寫成形如n=2M+J的公式，當(dāng)2M是不超過n的2的最大次冪，且l是剩余的數(shù)。可能我們可以通過這張表看出模式并猜出結(jié)果?？傊?，這是非常重要的事情。000)，如上所示，我們只要應(yīng)用19次(1)式。我們可以計算J(1。 當(dāng)n ≥1。 當(dāng)n ≥1。與等式J(1) = 1組合，我們得到一個定義了J的所有取值的遞推式:J(1) = 1。所以J(2n+ 1) = 2J(n) + 1。 當(dāng)n ≥1:我們現(xiàn)在可以快速的計算一下當(dāng)n比較大的時候的值。這個就像是以n個人開始的情況，除了每個人的編號變?yōu)閮杀稖p一。之后我們又回到了與我們開始的時候類似的情形，除了人數(shù)只有原來一半的人，而且他們的編號改變了。呃...，J(n)看起來總是奇數(shù)。但是其他一些數(shù)字比較小的情況告訴我們|當(dāng)n= 4和n= 6的時候這個假設(shè)錯誤了。我們剛剛看到的是J(10) = 5的情況。所以編號是5的人活下來了。例如，這里我們以設(shè)n= 10做開始。但是在這些叛軍中的Josephus和他沒有被告發(fā)的同伴覺得這么做毫無意義，所以他快速的計算出他和他的朋友應(yīng)該站在這個惡毒的圓圈的哪個位置。據(jù)傳說，如果沒有Josephus的數(shù)學(xué)天賦，他就不可能活下來而成為著名的學(xué)者。它們有兩個共同的特點：它們都是數(shù)學(xué)家們一直反復(fù)地研究的問題；它們的解都用了遞歸的概念，按遞歸概念，每個問題的解都依賴于相同問題的若干較小場合的解。Concrete MathematicsR. L. Graham, D. E. Knuth, O. Patashnik《Concrete Mathematics》， THE JOSEPHUS PROBLEMR. L. Graham, D. E. Knuth, O. PatashnikSixth printing, Printed in the United States of America 1989 by AddisonWesley Publishing Company，Reference 14 pages具體數(shù)學(xué)，《具體數(shù)學(xué)》，約瑟夫環(huán)問題，第一版第六次印刷于美國，韋斯利出版公司，1989年，引用816頁1. 遞歸問題本章研究三個樣本問題。這三個樣本問題給出了遞歸問題的感性知識。2. 約瑟夫環(huán)問題我們最后一個例子是一個以Flavius Josephus命名的古老的問題的變形，他是第一世紀(jì)一個著名的歷史學(xué)家。在猶太|羅馬戰(zhàn)爭中，他是被羅馬人困在一個山洞中的41個猶太叛軍之一，這些叛軍寧死不屈，決定在羅馬人俘虜他們之前自殺，他們站成一個圈，從一開始，依次殺掉編號是三的倍數(shù)的人，直到一個人也不剩。在我們的變形了的問題中，我們以n個人開始，從1到n編號圍成一個圈，我們每次消滅第二個人直到只剩下一個人。這時的消滅順序是2, 4, 6, 8, 10, 3, 7, 1, 9。這個問題：就是定位最后活下來的人的數(shù)字J(n)。我們可能會推測當(dāng)n是偶數(shù)的時候J(n) =n=2；而且當(dāng)n= 2的時候結(jié)論驗證了假設(shè)：J(2) = 1。于是我們回到了起點；讓我們試著來個更好的猜測。而且事實上，這個現(xiàn)象的原因是：圍成的圓圈的第一輪消滅了所有的編號是偶數(shù)的人。所以，讓我們假設(shè)最開始有2n個人，在第一輪結(jié)束后，我們剩下而且3將是下一個出局的。那就是， J(2n) = 2J(n)1。例如，我們知道J(10) = 5，所以J(20) = 2J(10)1 = 2*51 = 9:同樣可知J(40) = 17，進一步我們可以推算出 J(5*2M)=2M+1 +1但是，奇數(shù)的情況呢？當(dāng)有2n+ 1個人的時候，編號是1的人會在第2n個人出局后緊接著出局，然后，我們剩下我們再次獲得了形如n個人的情況，但是這次他們的編號是