作者hijkxyzuw (i,j,k) ×(x,y,z)
看板Programming
標題[問題] 費氏數列快速計算的 scheme 程式
時間Sun Sep 3 11:29:59 2017
最近在讀 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://webptt.com/m.aspx?n=bbs/Programming/M.1504409402.A.4D5.html