【正文】 兩倍加一。 當(dāng)n ≥1。J(2n) = 2J(n)1。 J(2n+ 1) = 2J(n) + 1。這個(gè)公式不是從J(n1)計(jì)算J(n)，這個(gè)遞歸式更加的“高效”，因?yàn)樗?為因子使n遞減了一半或更多。000。但是，我們依舊要尋找一個(gè)閉合形式的公式，因?yàn)槟菢訒?huì)更加快速和更有意義。 用我們的遞歸式，我們可以很快地建造一張較小取值的表。瞧！看起來我們可以以2的冪分組(通過表中的豎線)；在每組的開始，J(n)總是1，而且在一組內(nèi)以2遞增。這樣我們的遞歸式的解法看起來是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)式。當(dāng)m= 0我們一定有l(wèi) = 0；因此(2)式的基礎(chǔ)就變成了J(1) = 1，這時(shí)是正確的。如果m 0且2M+L=2n那么l是偶數(shù)。這個(gè)就是我們想要的。我們可能也注意到式子(1)還表達(dá)了這樣一個(gè)關(guān)系J(2n+1)J(2n)=2總之，這個(gè)數(shù)學(xué)歸納法證明完畢，且(2)式被證明了。在這個(gè)例子中，我們有100 =26+ 36，所以J(100) = 2*36 + 1 = 73現(xiàn)在，我們解決了艱難的部分(解決問題)。當(dāng)我們已經(jīng)掌握一項(xiàng)技巧，完整的研究它，看看借助它我們可以走多遠(yuǎn)是非常值得的。這些研究將會(huì)展示出所有這樣問題的結(jié)構(gòu)和基礎(chǔ)。假設(shè)n的二進(jìn)制表達(dá)式是n=(bmbm1...b1b0)2。) 我們已經(jīng)證明 J((bm1bm2...b1b0)2)= (bm1bm2...b1b0m)2。例如，如果n= 100 =(1100100)2, 那么J(n) = J(1100100)2=(1001001)2, 也就是64 + 8 + 1 = 73。如果我們以n個(gè)人開始，迭代J函數(shù)m+ 1次，計(jì)算機(jī)將會(huì)作m+ 1次的一位循環(huán)左移；所以當(dāng)n是一個(gè)(m+ 1)位的數(shù)字，我們可能希望最后又得到n。舉個(gè)例子，當(dāng)n= 13， 我們有J(1101)2=(1011)2, 但是之后J(1011)2=(111)2, 這時(shí)處理過程中斷了；當(dāng)0出現(xiàn)在首位的時(shí)候會(huì)被忽略。 重復(fù)的應(yīng)用過程J產(chǎn)生一個(gè)遞減的序列值，最終到達(dá)一個(gè)“固定的值”，也就是當(dāng)J(n) = n的時(shí)候。所以，當(dāng)v(13) = 3，我們有 2或更多的JJ(J(...J (13)...)) = 23 ? 1 = 7。很奇怪，但是是正確的。一般而言這個(gè)結(jié)論是明顯但不正確的，但我們現(xiàn)在可以看看它到底在什么情況下是正確的： J(n) = n=2。(我們將會(huì)在第四章研究這個(gè)問題。這些二進(jìn)制數(shù)一位循環(huán)左移的結(jié)果和一位循環(huán)右移的結(jié)果一樣。好了，我們對(duì)函數(shù)J了解的全面了；下一步是將這個(gè)問題一般化。讓我們通過引入常量α，β和γ 12 研究這個(gè)問題，并嘗試為較一般的遞歸式找到一個(gè)閉合形式的公式 f (1) = α。（4）f (2n + 1) = 2f (n) + γ, 當(dāng) n ≥ 1.(我們開始的遞歸式中α = 1，β = ?1，且γ = 1。另外，在2的冪的范圍內(nèi)，β的系數(shù)每次減1，直到0。所以，我們的表達(dá)式f(n)的形式是f(n) = A(n)α + B(n)β + C(n)γ, （6）通過與之相關(guān)的α，β和γ分離，可得 A(n) = 2m。C(n) = l. （7）這里跟以往一樣，n = 2m + l且0 ≤ l 2m，當(dāng)n ≥ 1。而且現(xiàn)在有個(gè)更好的方法來計(jì)算，通過帶入選定具體的值，然后對(duì)比計(jì)算他們。A(2n) = 2A(n)；當(dāng) n ≥ 1?？梢钥隙ǖ氖?A(2m + l) = 2m是正確的(通過對(duì)m進(jìn)行數(shù)學(xué)歸納法可以證明)。我們以一個(gè)簡(jiǎn)單的f(n)函數(shù)開始，看看是否存在常數(shù)(α, β, γ)可以確定它。2 = 2 3 = 2 所以取值(α, β, γ) = (1, ?1, ?1)滿足這些等式，且有A(n) ? B(n) ? C(n) =f(n) = 1。2n = 2 2n + 1 = 2 當(dāng)α = 1，β = 2且γ = 1的時(shí)候，這些等式對(duì)于所有的n成立，所以我們不必用數(shù)學(xué)歸納法證明這些參數(shù)滿足f(n) = n。現(xiàn)在我們已經(jīng)完成了核心的部分！我們已經(jīng)表示了(6)式的函數(shù)A(n)，B(n)以及C(n)，他們解決了廣義的(4)式，滿足公式A(n) = 2m, 當(dāng) n = 2m + l且0 ≤ l 2m。A(n) + C(n) = n.我們的對(duì)于(7)式的推測(cè)可以通過如下的式子立即解出來：C(n) = n ? A(n) = l以及B(n) = A(n) ? 1 ? C(n) = 2m ? 1 ? l。首先，我們要尋找我們的解法中已知的通用參數(shù)；這給予了我們能解得各個(gè)部分的特例。練習(xí)16和20提供了更多的相關(guān)例子。f(2n + j) = 2f(n) + βj, 當(dāng) j = 0, 1且n （8）若我們?cè)O(shè)β0 = β且β1 = γ。這樣就會(huì)得到 f (bmbm?1...b1b0)2 = (αβbm?1βbm?2 . . . βb1 + βb0)2. （9）好了。這個(gè)循環(huán)左移的特點(diǎn)之所以能滿足是因?yàn)槊總€(gè)二進(jìn)制數(shù)據(jù)塊(10...000)2在表示n的時(shí)候的時(shí)候轉(zhuǎn)化為(1 ?1... ?1 ?1)2 = (0 0 ... 0 1)2.所以我們改變?cè)o出的對(duì)遞歸式(8)的精簡(jiǎn)的解法(9)式。 f(dn + j) = cf(n) + βj 當(dāng)0 ≤ j d且n ≥ 1, （10）如同之前的那個(gè)，除了我們的起始的數(shù)字的基數(shù)是d，產(chǎn)生值是基數(shù)c。這里我們有d = 3和c = 10。所以，使2變?yōu)?，并假設(shè)0和1變成76和2，代入f(19) = f (201)3 = (576 ?2)10 = 1258,這就是我們的結(jié)果。161. Recurrent ProblemsTHIS CHAPTER EXPLORES three sample problems that give a feel forwhat39。ve all been investigated repeatedly by mathematicians。s the starting conguration forn=10:The elimination order is2, 4, 6, 8, 10, 3, 7, 1, 9, so 5survives. The problem:Determine the survivor39。 and the case n=2supports the conjecture: J(2) = 1. But a few other small cases dissuade us | the conjecture fails forn=4andn=6.It39。 let39。s a good reason for this: The rst trip around the circle eliminates all the even numbers. Furthermore, if nitself is an even number, we arrive at a situation similar to what we began with, except that there are only half as many people, and their numbers have changed. So let39。re left withnd3will be the next to go. This is just like starting out withnpeople, except that each person39。 當(dāng)n ≥1:We can now go quickly to largen. For example, we know that J(10) =5, soJ(20) = 2J(10)1 = 2*51 = 9:Similarly J(40) = 17，and we can deduce that J(5*2M)=2M+1 +1But what about the odd case? With2n+1 people, it turns out that person number1is wiped out just after person number 2n, and we39。 for n ≥1。J(2n) = 2J(n)1。 J(2n+ 1) = 2J(n) + 1。Instead of gettingJ(n)from J(n1), this recurrence is much more effcient,because it reducesnby a factor