練習1.11

??????? 函數f如下定義: 如果n<3， 那么f(n)=n; 否則f(n)=f(n-1)+2*f(n-2)*3*f(n-3). 寫出一個遞歸和一個迭代求這個問題.

??????? 遞歸:

(define (f n)(if (< n 3)n(+ (f (- n 1))(* 2 (f(- n 2)))(* 3 (f(- n 3))))))

??????? 迭代:

(define (f n)(if (< n 3)n(f-iter 2 1 0 n))) (define (f-iter a b c count)(if ( = count 2)a(f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

練習1.12

??????? 寫一個pascal函數, 輸入行和列, 求帕斯卡三角形中這個行和列的值.

??????? 答案非常巧妙的把帕斯卡三角形放到了一個表格中. 表格中每一行的第一個數從表格的第一列開始, 那么求第row行第col列就可以非常形象描述成求第row-1行col列和row-1行和col列的和, 而這種方法最好的地方在于它表示每一行第一個數和最后一個數是1.

(define (pascal row col)(cond ((= row 1) 1) ;第一行值為1((= row col) 1) ;行和列相同的項值為1((= col 1) 1) ;第一列值都為1(else (+ (pascal (- row 1) col)(pascal (- row 1) (- col 1))))))

練習1.13

??????? 證明斐波那契數列第n個數Fib(n)是最接近Φⁿ/根號5的整數，其中Φ=(1+根號5)/2.

??????? 這題是看的答案, 證明過程也非常的直觀明了.

設fi = (1+根號5)/2, psi = (1-根號5)/2

第一步目的要證明Fib(n) = (fiⁿ - psiⁿ)/根號5， 采用數學歸納法:

當n=0時, Fib(0) = (fi⁰ - psi⁰)/根號5 = 0， 成立

當n=1時, Fib(1) = (fi¹ – psi¹)/根號5 = 1， 成立

推廣到n時, Fib(n) = Fib(n-1) + Fib(n-2) = (fiⁿ-1 – psiⁿ-1 + fiⁿ-2 – psiⁿ-2)/根號5

??????????????????????? = ((fi + 1)fi^n-2 – (psi +1)psi^n-2)/根號5??? , 式1

?????????????? 因為fi² = fi + 1， psi² = psi + 1

?????????????? 所以式1= (fiⁿ - psiⁿ)/根號5, 即可證明第一步的式子.

當n趨向于無窮大的時候, 因為psi=-0.618， 所以psiⁿ趨向于0， 即可得證Fib(n)是最接近Φⁿ/根號5的整數.

總結

以上是生活随笔為你收集整理的SICP学习笔记(P27-P28)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。