Re: [問題] 費氏數列快速計算的 scheme 程式

看板Programming作者jimfan (jimfan)時間7年前 (2017/09/09 18:07)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串3/3 (看更多)

: > *Exercise 1.19:* There is a clever algorithm for computing the : > Fibonacci numbers in a logarithmic number of steps. Recall the : > transformation of the state variables a and b in the 'fib-iter' : > process of section *note 1-2-2::: a <- a + b and b <- a. Call this : > transformation T, and observe that applying T over and over again n : > times, starting with 1 and 0, produces the pair _Fib_(n + 1) and : > _Fib_(n). In other words, the Fibonacci numbers are produced by : > applying T^n, the nth power of the transformation T, starting with : > the pair (1,0). Now consider T to be the special case of p = 0 and : > q = 1 in a family of transformations T_(pq), where T_(pq) : > transforms the pair (a,b) according to a <- bq + aq + ap and b <- : > bp + aq. Show that if we apply such a transformation T_(pq) twice, : > the effect is the same as using a single transformation T_(p'q') of : > the same form, and compute p' and q' in terms of p and q. This : > gives us an explicit way to square these transformations, and thus : > we can compute T^n using successive squaring, as in the 'fast-expt' : > procedure. Put this all together to complete the following : > procedure, which runs in a logarithmic number of steps:(5) 就係不明白他說的"transformation"是啥......我數學太爛了不過算法確實精彩，假設要找fib(17)，以下列舉每項 fib-iter 的輸入： a b p q count ========================== 1 0 0 1 17 1 1 0 1 16 1 1 1 1 8 1 1 2 3 4 1 1 13 21 2 1 1 610 987 1 2584 1597 610 987 0 count 為零時，b = 1597，所以 f(17) = 1597 神奇的是，count 為 1 時，f(15) 與 f(16) 分別出現為 p、q count 為 2 時，f(7) 與 f(8) 分別出現為 p、q 往上推如是 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 14.199.97.157 ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1504951623.A.4D0.html