练习1.11
递归过程
(define (func n)
(if (< n 3)
n
(+
(* 1 (func (- n 1)))
(* 2 (func (- n 2)))
(* 3 (func (- n 3))))))
迭代过程
(define (func n)
(fun-iter 0 1 2 n))
(define (fun-iter a b c count)
(if (= count 0)
a
(fun-iter b c (+ (* 1 c) (* 2 b) (* 3 a)) (- count 1))))
练习1.12
(define (pasca n i)
(cond ((= i 1) 1)
((= i (+ n 1)) 1)
(else (+ (pasca (- n 1) (- i 1)) (pasca (- n 1) i)))))
练习1.13
已知:f(n+1) = f(n) + f(n-1) (1)
设存在f(n+1) + x*f(n) = y*[f(n) + x*f(n-1)] (2),则有
f(n+1) = (y-x)*f(n) + x*y*f(n-1)
根据(1),则有y-x=1, x*y=1,则有x*(x+1)=1
此方程有解
x=(√5-1)/2、y=(√5+1)/2
则存在等比数列f'(n),其首项为f(2) + [(√5-1)/2]*f(1) = (√5+1)/2,公比为(√5+1)/2
则f'(n) = [(√5+1)/2]^n,即
f(n+1) + [(√5-1)/2]*f(n) = [(√5+1)/2]^n
f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n (3)
设存在f(n+1) + x*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) + x*[(√5+1)/2]^n] (4),则有
f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n*(-√5*x)
根据(2),则有
-√5*x=1,则x=-√5/5
代入(4),得
f(n+1) - (√5/5)*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) - (√5/5)*[(√5+1)/2]^n]
则存在等比数列f''(n),其首项为f(1)- (√5/5)*[(√5+1)/2] = (5-√5)/10,公比为(1-√5)/2
则f''(n) = [(5-√5)/10]*[(1-√5)/2]^(n-1),则
f(n)- (√5/5)*[(√5+1)/2]^n = -(√5/5)*[(1-√5)/2]^n
f(n) = (√5/5)*[(√5+1)/2]^n - (√5/5)*[(1-√5)/2]^n
若有φ=(√5+1)/2、ψ=(1-√5)/2,则有
f(n)=(φ^n-ψ^n)/√5
所以 φ^n/√5 = f(n) + ψ^n/√5
而ψ=(1-√5)/2,-1 < ψ < 0,则-1 < ψ^n < 1,则-√5/5 < ψ^n/√5 < √5/5
又√5/5 < 1,所以f(n)是最接近φ^n/√5的整数
分享到:
相关推荐
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
SICP 使用的scheme解释器 以前叫DrScheme
Learn_sicp 学习sicp的一些代码
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
sicp_notes SICP笔记和练习 资源 笔记 使用第一版,最高为ex 1.24。 从ex 1.31开始切换到第二版。
SICP 解题集
SICP CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
请参考那些正在学习SICP的人。 笔记 如果你想在 gauch 中使用随机函数 (use math.mt-random) (define m (make <mersenne> :seed (sys-time))) (mt-random-integer m 1000) (define (random n) (mt-random-integer ...
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
SICP习题解答,主要第一章的内容习题答案
资源来自pypi官网。 资源全名:sicp-0.0.1b102.dev4.tar.gz
sicp-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案