【正文】 even or odd. If m 0and2M+L=2n , then l is even andJ(2M+L)=2J(2M1+L/2)1=2(2L/2+1)1 = 2l+ 1。s applied. We could puteJ(1000000), say, with only 19 applications of (). But still, we seek a closed form, because that will be even quicker and more informative. After all, this is a matter of life or death.Our recurrence makes it possible to build a table of small values very quickly. Perhaps we39。 for n ≥1。re left with Again we almost have the original situation withnpeople, but this time their numbers are doubled andincreased by1. ThusJ(2n+ 1) = 2J(n) + 1。s suppose that we have2npeople originally. After the rst goround, we39。s back to the drawing board。 and their solutions all use the idea ofrecurrence, in which the solution to each problem depends on the solutionsto smaller instances of the same problem. THE JOSEPHUS PROBLEM In our Our nal introductory example is a variant of an ancient problem named for Flavius Josephus, a variation, we start withnpeople numbered 1 tonaround a circle, and we eliminate everysecondremaining person until only one survives. For example, here39。所以Josephus以及猶太—羅馬戰(zhàn)爭留給我們一些有趣的廣義遞歸式。所以，這個基數(shù)改變了的解法是f (bmbm?1...b1b0)d = (αbmβbm?1βbm?2 . . . βb1βb0)c. （11）例如，假設(shè)一個幸運(yùn)的巧合19下我們獲得了一個遞歸式f(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 當(dāng)n ≥ 1f(3n + 1) = 10f(n) ? 2 當(dāng)n ≥ 1f(3n + 2) = 10f(n) + 8, 當(dāng)n ≥ 1假設(shè)我們想計(jì)算f(19)。如果我們把(5)式換一種寫法17，我們會更早些看到這個模式：舉個例子，當(dāng)n = 100 = (1100100)2的時候，我們原來的Josephus取值為α = 1，β = ?1，且γ = 1帶入后構(gòu)造結(jié)論跟之前一樣。我們知道原來的遞歸式J有一個神奇的解法，也就是二進(jìn)制：J (bmbm?1...b1b0)2 = (bm?1...b1b0bm)2, 當(dāng) bm = 1.那么，廣義的Josephus遞歸式也能如此神奇么？當(dāng)然，為什么不呢？我們可以把這個廣義的遞歸式(4)重寫成如下形式f(1) = α。這個過程已經(jīng)接近于展示一個驚奇、有用的repertoire method來解決遞歸式問題。我們已經(jīng)知道f(n) = n在這個例子中是解，因?yàn)檫f歸式(4)為每個n的取值唯一的定義了f(n)。 n + β。 1 + γ。將常函數(shù)f(n) = 1帶入遞歸式(4)可得1 = α。A(2n + 1) = 2A(n)；當(dāng) n ≥ 1。使用數(shù)學(xué)歸納法證明(6)式和(7)式并不是一件非常艱難的事情，但是這個計(jì)算過程是繁雜而且沒有技術(shù)含量的。而γ的系數(shù)則從0開始每次增加1。f (2n) = 2f (n) + β, 當(dāng) n ≥ 1。(結(jié)果都是減半)。 2l+ 1 =(2m+l)/2 l =1/3(2m2)如果這個式子l =1/3(2m2) 是一個整數(shù)，那么n=2m+l將會是一個解，因?yàn)閘會小于2m 不難驗(yàn)證當(dāng)m是奇數(shù)，2m2是3的倍數(shù)，但當(dāng)m是偶數(shù)的時候不成立。同樣的8或更多J(J(...J(101101101101011)2...)) = 210 ? 1 = 1023。事實(shí)上，根據(jù)定義，J(n)必須總是≤n, 因?yàn)镴(n)是存活著的人的編號；所以如果J(n) n我們決不可能通過繼續(xù)迭代回溯到n。如果我們從一開始就一直用二進(jìn)制方法研究，我們可能會立即就發(fā)現(xiàn)這個模式。也就是 n=bm2m+bm12m1+....b12+b0每個bi 取值是0或1，且最高位bm 是1. 回想一下n=2M+L我們先后得到如下表達(dá)式， n=(1bm1bm2...b1b0)2 L=(0bm1bm2...b1b0)22L=( bm1bm2...b1b0)22L+1=(bm1bm2...b1b01)2J(n)= (bm1bm2...b1b0m)2(最后一個式子是因?yàn)镴(n) = 2l+ 1以及bm=2L+1以及bm=1。所以，在這節(jié)的余下部分，我們將會研究我們的解法(2)式以及研究遞歸式(1)的一些擴(kuò)展。為了展示解法(2)式，讓我們來計(jì)算一下J(100)。且通過(1)式和歸納法假設(shè)可得J(2M+L)=2J(2M1+L/2)1=2(2L/2+1)1 = 2l+ 1。如我們以前使用的數(shù)學(xué)歸納法一樣，但是這次我們的數(shù)學(xué)歸納是基于變量m的?？赡芪覀兛梢酝ㄟ^這張表看出模式并猜出結(jié)果。000)，如上所示，我們只要應(yīng)用19次(1)式。 當(dāng)n ≥1。與等式J(1) = 1組合，我們得到一個定義了J的所有取值的遞推式:J(1) = 1。 當(dāng)n ≥1:我們現(xiàn)在可以快速的計(jì)算一下當(dāng)n比較大的時候的值。之后我們又回到了與我們開始的時候類似的情形，除了人數(shù)只有原來一半的人，而且他們的編號改變了。但是其他一些數(shù)字比較小的情況告訴我們|當(dāng)n= 4和n= 6的時候這個假設(shè)錯誤了。所以編號是5的人活下來了。但是在這些叛軍中的Josephus和他沒有被告發(fā)的同伴覺得這么做毫無意義，所以他快速的計(jì)算出他和他的朋友應(yīng)該站在這個惡毒的圓圈的哪個位置。它們有兩個共同的特點(diǎn)：它們都是數(shù)學(xué)家們一直反復(fù)地研究的問題；它們的解都用了遞歸的概念，按遞歸概念，每個問題的解都依賴于相同問題的若干較小場合的解。這三個樣本問題給出了遞歸問題的感性知識。在猶太|羅馬戰(zhàn)爭中，他是被羅馬人困在一個山洞中的41個猶太叛軍之一，這些叛軍寧死不屈，決定在羅馬人俘虜他們之前自殺，他們站成一個圈，從一開始，依次殺掉編號是三的倍數(shù)的人，直到一個人也不剩。這時的消滅順序是2, 4, 6, 8, 10, 3, 7, 1, 9。我們可能會推測當(dāng)n是偶數(shù)的時候J(n) =n=2；而且當(dāng)n= 2的時候結(jié)論驗(yàn)證了假設(shè)：J(2) = 1。而且事實(shí)上，這個現(xiàn)象的原因是：圍成的圓圈的第一輪消滅了所有的編號是偶數(shù)的人。那就是， J(2n) = 2J(n)1。 當(dāng)n ≥1。 J(2n+ 1) = 2J(n) + 1。000。 用我們的遞歸式，我們可以很快地建造一張較小取值的表。這樣我們的遞歸式的解法看起來是J(2M+L)=2L+1 當(dāng)m≥0且0≤L2M （2）(注意如果2M≥n2M+1, 那么余下的數(shù)l =n2M 滿足不等式0≤L2M+12M=2M.)我們現(xiàn)在必須證明(2)式。如果m 0且2M+L=2n那么l是偶數(shù)。我們可能也注意到式子(1)還表達(dá)了這樣一個關(guān)系J(2n+1)J(2n)=2總之，這個數(shù)學(xué)歸納法證明完畢，且(2)式被證明了。當(dāng)我們已經(jīng)掌握一項(xiàng)技巧，完整的研究它，看看借助它我們可以走多遠(yuǎn)是非常值得的。假設(shè)n的二進(jìn)制表達(dá)式是n=(bmbm1...b1b0)2。例如，如果n= 100 =(1100100)2, 那么J(n) = J(1100100)2=(1001001)2, 也就是64 + 8 + 1 = 73。舉個例子，當(dāng)n= 13， 我們有J(1101)2=(1011)2, 但是之后J(1011)2=(111)2, 這時處理過程中斷了；當(dāng)0出現(xiàn)在首位的時候會被忽略。所以，當(dāng)v(13) = 3，我們有 2或更多的JJ(J(...J (13)...)) = 23 ? 1 = 7。一般而言這個結(jié)論