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

看板Programming作者hijkxyzuw (i,j,k) ×(x,y,z)時間7年前 (2017/09/03 11:30)推噓0(0推 0噓 0→)

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

最近在讀 sicp ，在 1-2-4 章，有介紹一種將 n 次計算簡化為 log(n) 次的作法。他應用在費氏數列上，但他使用的費氏數列算法我看不懂……。原文： > *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) 別人的 scheme 程式碼： (define (fib n) (define (even? n) (= (remainder n 2) 0)) (define (fib-iter a b p q count) (display (list a b p q count)) (newline) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (square p) (square q)) (+ (* 2 p q) (square q)) (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1))))) (fib-iter 1 0 0 1 n)) 翻譯成 javascript ：（應該算比較多人懂的程式語言） function fib(n) { return iter(1,0,0,1, n) // 用尾端遞迴，和 scheme 相同 return whileLoop(n) // 改寫成 javascript 的 while 迴圈 function square(n) { return n*n } function isEven(n) { if (n%2 == 0) return true else return false } // while 迴圈 function whileLoop(n) { var a = 1 var b = 0 var p = 0 var q = 1 var count = n while (count != 0) { console.log(a,b,p,q, count) // 展示用 if (isEven(count)) { var nextP = square(p) + square(q) var nextQ = 2*p*q + square(q) p = nextP q = nextQ count /= 2 } else { var nextA = b*q + a*q + a*p var nextB = b*p + a*q a = nextA b = nextB count-- } } return b } // 尾端遞迴 function iter(a, b, p, q, count) { console.log(a,b,p,q, count) // 展示用 if (count == 0) return b else if (isEven(count)) { return iter( a, b, square(p) + square(q), 2*p*q + square(q), count / 2 ) } else { return iter( b*q + a*q + a*p, b*p + a*q, p, q, count -1 ) } } } 我不了解的是，為什麼費氏數列可以這樣算？書裡也沒仔細寫，（或我看不懂？）範例還把 p 和 q 的計算遮起來，要我們自己填該怎麼算。簡化為 log(n) 的作法我看得懂，就是原本 a^7 要 a * a * a * ... * a 乘 7 次，簡化為 a^2^2 * a^2 * a ，只要乘 4 次。（ a*a , a*a * a*a , a * a*a , a*a*a * a*a*a*a ）有人可以介紹一下那個費氏數列算法的原理嗎？ -- 8Ｈ(( ((88( ((((((((888(8((( ∫8段段??????? ﹊∴……﹛﹜ [m -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.102.187 ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1504409402.A.4D5.html