`
SavageGarden
  • 浏览: 221421 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

SICP学习笔记 1.3.4 过程作为返回值

    博客分类:
  • SICP
 
阅读更多

    练习 1.40

(define (cubic a b c)
  (lambda (x)
    (+ (cube x) (* a (square x)) (* b x) c)))

1 ]=> (newtons-method (cubic 1.0 1.0 -3.0) 1.0)
;Value: 1.

 

   练习 1.41

(define (double f)
  (lambda (x) (f (f x))))
(define (inc x)
  (+ x 1))
  
1 ]=> (((double (double double)) inc) 5) 
;Value: 21

 

    练习 1.42

(define (compose f g)
  (lambda (x) (f (g x))))
  
1 ]=> ((compose square inc) 6)
;Value: 49

 

   练习 1.43

(define (repeated f n)
  (cond ((= n 1) f)
	((even? n) (compose f (repeated f (/ n 2))))
	(else (compose f (repeated f (- n 1))))))
	
1 ]=> ((repeated square 2) 5)
;Value: 625

 

    练习 1.44

(define (smooth f)
  (lambda (x)
    (/ (+ (f (+ x dx))
	  (f x)
	  (f (- x dx)))
       3)))

(define (smooth-n f n)
  (repeated smooth n))

 

    练习 1.45

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))
1 ]=> (sqrt 4.0)
 *** 1.
 *** 2.5
 *** 2.05
 *** 2.000609756097561
 *** 2.0000000929222947
;Value: 2.000000000000002

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))
1 ]=> (cube-root 8.0)
 *** 1.
 *** 4.5
 *** 2.447530864197531
 *** 1.8914996576441667
 *** 2.0637643832634476
 *** 1.9710425766479744
 *** 2.0151199754332096
 *** 1.992609760395472
 *** 2.0037362842809587
 *** 1.998142301706526
 *** 2.0009314406381735
 *** 1.9995349299633447
 *** 2.0002326972862416
 *** 1.9998836919616
 *** 2.0000581641656563
 *** 1.999970920454376
 *** 2.0000145404070393
 *** 1.9999927299550464
 *** 2.000003635062117
;Value: 1.9999981824788517

(define (fourth-root x)
  (fixed-point (average-damp (lambda (y) (/ x (cube y)))) 1.0))
  
1 ]=> (fourth-root 16.0)
 *** 1.
 *** 8.5
 *** 4.263026663952778
 *** 2.2347742162681095
 *** 1.8341723103276433
 *** 2.2135774006557023
 *** 1.844363126744897
 ......
 *** 1.983599149847315
 *** 2.016809915138478
 *** 1.983608081177677
 *** 2.0168005353295855
 *** 1.983616997866416
 *** 2.0167911711462776
 *** 1.983625899953568
;Quit!
;; 出现振荡,Ctrl+C杀掉

;; 对x求n次方根时,使用repeated调用m次average-damp(即做m次平均阻尼)

(define (fast-expt x n)
  (fast-expt-iter x n 1))
  
(define (fast-expt-iter x counter product)
  (cond ((= counter 0) product)
	((even? counter) (fast-expt-iter (square x) (/ counter 2) product))
	(else (fast-expt-iter x (- counter 1) (* x product)))))
	
(define (find-root x n m)
  (fixed-point ((repeated average-damp m) (lambda (y) (/ x (fast-expt y (- n 1))))) 1.0))
  
1 ]=> (find-root 4.0 2 1)
 *** 1.
 *** 2.5
 *** 2.05
 *** 2.000609756097561
 *** 2.0000000929222947
;Value: 2.000000000000002

1 ]=> (find-root 8.0 3 1)
 *** 1.
 *** 4.5
 *** 2.447530864197531
 *** 1.8914996576441667
 *** 2.0637643832634476
 *** 1.9710425766479744
 *** 2.0151199754332096
 *** 1.992609760395472
 *** 2.0037362842809587
 *** 1.998142301706526
 *** 2.0009314406381735
 *** 1.9995349299633447
 *** 2.0002326972862416
 *** 1.9998836919616
 *** 2.0000581641656563
 *** 1.999970920454376
 *** 2.0000145404070393
 *** 1.9999927299550464
 *** 2.000003635062117
;Value: 1.9999981824788517

1 ]=> (find-root 16.0 4 2)
 *** 1.
 *** 4.75
 *** 3.5998232249599065
 *** 2.7856139316659103
 *** 2.274263910561008
 *** 2.045743730517053
 *** 2.0015115314098866
 *** 2.000001711389449
;Value: 2.0000000000021965

;; 尝试对求5次方根时做两次平均阻尼以查看收敛性, 可以得到近似正确的结果
1 ]=> (find-root 32.0 5 2)
 *** 1.
 ......
;Value: 2.000001512995761

;; 求6次方根, 做两次平均阻尼仍然能得到正确的近似结果
1 ]=> (find-root 64.0 6 2)
 *** 1.
 ......
;Value: 2.0000029334662086

;; 7次方根
1 ]=> (find-root 128.0 7 2)
......
;Value: 2.0000035538623377

;; 8次方根
1 ]=> (find-root 256.0 8 2)
......
 *** 2.0036413071907813
 *** 1.9964048473987912
 *** 2.0036406355855547
 *** 1.9964055020263292
 *** 2.0036399643510747
 *** 1.9964061562955964  C-c C-c
 *** 2.0036392934869998
;Quit!
;; 出现振荡,Ctrl+C杀掉

;; 在求8次方根时又出现振荡,因此再多做一次平均阻尼,即如下调用,得到正确的近似结果
1 ]=> (find-root 256.0 8 3)
......
;Value: 2.000000000003967

;; 发现如下规律
;; 2、3 次方根时做一次平均阻尼
;; 4、5、6、7 次方根时做两次平均阻尼
;; 8 次方根时做三次平均阻尼
;; 可见对 X 开 N 次方根与做 M 次平均阻尼有如下关系
;; M = (/ (log N) (log 2))
;; 对9、15次方根验证

1 ]=> (find-root 512.0 9 3)
;Value: 1.9999997106840102


1 ]=> (find-root (fast-expt 2.0 15) 15 3)
;Value: 2.0000040951543028

;; 因此修改过程为
(define (find-root x n)
  (let ((m (round (/ (log n) (log 2)))))
    (fixed-point
     ((repeated average-damp m)
      (lambda (y) (/ x
		  (fast-expt y (- n 1))))) 1.0)))

;; 但是继续验证, 发现还有问题  
;; 继续对3^16验证, 做四次平均阻尼仍然会出现振荡, 需要做五次平均阻尼才会得到正确的近似结果
;; 继续对3^32验证, 做六次平均阻尼仍然会出现振荡, 需要做七次平均阻尼才会得到正确的近似结果
;; 继续对3^64验证, 做八次平均阻尼仍然会出现振荡, 需要做十一次平均阻尼才会得到正确的近似结果

;; 于是又发现变化过程
;; 取 K = (/ (log N) (log 2))
;; 取 M = 能得到正确近似结果时需要做的平均阻尼次数
;; K 			M										
;; 1			1
;; 2			2
;; 3 			3
;; 4			5
;; 5 			7
;; 6			11
;; 于是推测
;; 7 			15
;; 漫长的等待后, 终于收敛到了近似结果 ..... -_-|
;; 继续推测
;; 8			21 ?
;; 更加漫长的等待, 不收敛!!! -_-|
;; 那就试试
;; 8 			23 !
;; MBP MD102 主频i7 2.9 内存8G 跑了近10分钟才收敛到近似结果 -_-|
;; 再往后收敛时间太过漫长, 没有继续测试, 应该有简单的办法可以得到求N次方根与做M次平均阻尼的关系

 

    练习 1.46

;; 对iterative-improve过程的实现
(define (iterative-improve good-enough? improve)
  (define (iter guess)
    (if (good-enough? guess)
			guess
			(iter (improve guess))))
  (lambda (guess) (iter guess)))
  
;; 根据iterative-improve过程对sqrt重新实现
(define (iterative-improve-sqrt x)
  (define (sqrt-good-enough? guess)
    (< (abs (- (square guess) x)) tolerance))
  (define (sqrt-improve guess)
    (average guess (/ x guess)))
  ((iterative-improve sqrt-good-enough? sqrt-improve) 1.0))
  
1 ]=> (iterative-improve-sqrt 9.0)

;Value: 3.000000001396984

;; 根据iterative-improve过程对fixed-point重新实现
(define (iterative-improve-fixed-point f)
   (define (fixed-point-good-enough? guess)
     (< (abs (- guess (f guess))) tolerance))
   ((iterative-improve fixed-point-good-enough? f) 1.0))
   
1 ]=> (iterative-improve-fixed-point cos)

;Value: .7390893414033928

;; 计算结果与原始fixed-point过程计算结果精度略低, 经查
1 ]=> (cos 0.7390893414033928)

;Value: .7390822985224023

;; 即原始fixed-point过程中定义了
let ((next (f guess)))

;; 即对于guess, 原始过程经过next处理后进行检测, 如果足够好返回的是(f guess)
;; 而iterative-improve过程对于guess无此处理, 返回的是guess
 
0
4
分享到:
评论

相关推荐

    SICP(计算机体系结构)

    - **1.3.4 作为返回值的过程**: 了解过程作为函数返回值的应用场景。 **2. 通过数据构建抽象** 本部分侧重于如何利用数据结构来创建抽象。主要内容包括: - **2.1 数据抽象简介** - **2.1.1 示例:有理数的算术...

    sicp 2016 from

    - **返回值的过程 (Procedures as Returned Values)**:探讨了过程可以作为函数返回值的概念。 ##### 2. 使用数据建立抽象 (Building Abstraction with Data) - **数据抽象简介 (Introduction to Data Abstraction...

    SICP 习题答案

    - **过程**:在SICP中,过程是λ演算中的核心概念,代表可执行的计算操作。 - **组合器**:通过组合简单的过程来构建复杂的过程,这是λ演算的基本思想,也是编程中的模块化原则。 2. **函数式编程**: - **纯...

    SICP(python中文带书签)

    在Python中实现SICP的挑战在于,Python的语法和Lisp有很大区别,但这也为学习者提供了思考不同编程范式的机会。例如,Python的面向对象特性可以用来模拟SICP中的一些过程抽象,而Lisp中的动态作用域在Python中需要...

    a_book_sicp_py

    函数作为程序的核心构建块,允许程序员通过参数和返回值来控制数据的流程和处理过程。函数的艺术在于能够将复杂的任务分解为更小、更易于管理的部分。 5. 使用对象构建抽象:在第二章中,书中探讨了如何使用对象来...

    sicp in python 中文 sicp 中文

    sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download&gt;&gt;&gt;https://github.com/wizardforcel/sicp-py-zh

    SICP中文第二版

    SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版

    sicp-Structure and Interpretation of Computer Programs

    SICP不仅在MIT内部被广泛用作教学材料,而且在全球范围内也享有极高的声誉,被视为学习计算机科学理论基础的必读之作。 #### 二、书籍内容概览 SICP的内容涵盖了程序设计的基本概念、过程抽象、数据抽象、模块化...

    SICP 计算机程序的构造与解释

    在Scheme中,函数可以作为其他函数的参数,也可以作为返回值,这种特性使得函数式编程能更好地支持抽象和模块化。 2. **过程抽象**:书中的一个重要概念是过程抽象,即通过定义新的函数来封装复杂逻辑,使其在后续...

    sicp 2.2.4节图形语言

    《SICP 2.2.4 节:图形语言》是计算机科学经典教材《结构与解释程序》(Structure and Interpretation of Computer Programs)中的一个重要章节,它深入介绍了如何利用编程来创建图形,以及如何设计和理解复杂的计算...

    SICP LISP AI

    1. **过程和数据**:书中首先介绍了过程(函数)作为基本的抽象机制,以及如何将数据结构视为可组合的过程。这种观点改变了我们看待计算问题的方式,强调了将复杂问题分解为简单过程的重要性。 2. **环境模型**:...

    sicp_notes:SICP笔记和练习

    《SICP笔记和练习》是一份详尽的资源,主要涵盖了由MIT教授们编写的经典计算机科学教材《Structure and Interpretation of Computer Programs》(简称SICP)的学习笔记和练习解答。这份资料以HTML格式呈现,便于在线...

    SICP 解题集

    通过学习SICP,读者可以掌握如何用基本的构建块来构造复杂的计算系统,并理解这些系统的行为。书中的习题设计巧妙,旨在引导读者深入思考编程语言的内部机制以及如何设计和实现自己的编程环境。 《SICP解题集》中...

    sicp-core

    4. **过程作为第一类对象**:在Lisp中,过程是与数字、字符串等数据类型同等对待的第一类对象,可以被赋值、传递给其他过程或作为其他过程的返回值。 5. **元编程**:SICP探讨了元编程的概念,即编写处理程序自身...

    sicp 2nd 英文chm

    5. **过程**:SICP讲解了过程作为“计算的封装”的概念,使得过程可以作为值传递,从而实现了高阶函数。 6. **元编程**:SICP还涉及元编程,即编写操作代码的代码。通过这种方式,读者可以理解编程语言是如何工作的...

    SICP习题解答,主要第一章的内容习题答案

    本资料集包含了对SICP第一章习题的解答,旨在帮助学习者巩固基础,深化对函数式编程的理解。 首先,让我们关注一下习题解答中的几个关键部分: 1. **1.6.ss**: 这部分可能涉及到函数定义、递归和过程抽象。SICP的...

    北京大学,计算机程序构造和解释(SICP)课件,裘宗燕老师主讲

    它以Lisp语言作为教学工具,因为Lisp的简洁性和表达力强,非常适合用来展示程序的构造和解释过程。通过学习SICP,学生将能够理解如何设计、分析和实现复杂的程序系统,培养出强大的抽象思维能力。 课程内容涵盖了...

Global site tag (gtag.js) - Google Analytics