【正文】 = n=2。Similarly8or moreJ(J(...J(101101101101011)2...)) = 210 ? 1 = 1023。 hence if J(n) nwe can never get back up tonby continuing to iterate. Repeated application ofJproduces a sequence of decreasing values that eventually reach a fixed point, where J(n) = n The cyclic shift property makes it easy to see what that fixed point will be: Iterating the function enough times will always produce a pattern of all139。 the 0disappears when it bees the leading fact, J(n) must always be ≤n, by denition, sinceJ(n) is the survivor39。 so, sincenis an (m+1)bit number, we might expect to end up with nagain. But this doesn39。 (3)that is, in the lingo of puter programming, we get J(n) from nby doing a onebit cyclic shift left! Magic. For example, if n= 100 =(1100100)2 then J(n) = J(1100100)2=(1001001)2, which is 64+8+1=73. If we had been working all along in binary notation, we probably would have spotted this pattern immediately.if we start with nand iterate theJ function m+1 times, we39。that is,n=bm2m+bm12m1+....b12+b0where each bi is either 0or1and where the leading bit bm is 1. Recalling that n=2M+L, we have, successively, n=(1bm1bm2...b1b0)2 L=(0bm1bm2...b1b0)22L=( bm1bm2...b1b0)22L+1=(bm1bm2...b1b01)2J(n)= (bm1bm2...b1b0m)2(The last step follows because J(n) = 2l+ 1 and because bm=2L+1 and bm=1。snatural to look at the radix2 representations of nandJ(n). Suppose n39。ve learned a technique, it39。s pute J(100). In this case we have100 =26+ 36, so J(100) = 2*36 + 1 = 73Now that we39。 this is exactly what we want. A similar proof works in the odd case, when 2M+L=2L+1。 thus the basis of reduces to J(1) = 1, which is true. The induction step has two parts, depending on whetherl is 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。J(n) is always 1at the beginning of a group and it increases by2 within a group. So if we writenin the form n=2M+J, where 2M is the largest power of 2not exceedingnand wherel is what39。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。 for n ≥1。Combining these equations with J(1) = 1 gives us a recurrence that denes J in all cases:J(1) = 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 number has been doubled and decreased by1. That is,J(2n) = 2J(n)1。s suppose that we have2npeople originally. After the rst goround, we39。s try to make a better guess. Hmmm : : :J(n)always seems to be odd. And in fact, there39。s back to the drawing board。s number,J(n).We just saw thatJ(10) =5. We might conjecture that J(n) =n=2when nis even。 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。s to e. They have two traits in mon: They39。所以Josephus以及猶太—羅馬戰(zhàn)爭留給我們一些有趣的廣義遞歸式?，F(xiàn)在19 = (201)3，通過這個基數(shù)改變了的解法，我們把數(shù)字一位一位的替換，把每個數(shù)字從基于基數(shù)3的表示方法替換為基數(shù)是10的。所以，這個基數(shù)改變了的解法是f (bmbm?1...b1b0)d = (αbmβbm?1βbm?2 . . . βb1βb0)c. （11）例如，假設一個幸運的巧合19下我們獲得了一個遞歸式f(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 當n ≥ 1f(3n + 1) = 10f(n) ? 2 當n ≥ 1f(3n + 2) = 10f(n) + 8, 當n ≥ 1假設我們想計算f(19)。如果我們已經(jīng)不受約束了，我們就可以使它更加一般化18，所以遞歸式f(j) = aj, 當1 ≤ j d。如果我們把(5)式換一種寫法