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

SICP学习笔记 1.2.1 线性的递归和迭代

    博客分类:
  • SICP
 
阅读更多

  练习1.9

    对于过程

    (define (+ a b)

      (if (= a 0)

        b

        (inc (+ (dec a) b))))

    计算(+ 4 5)时的替换过程为

    -->(+ 4 5) 

    -->(if (= 4 0) 5 (inc (+ (dec 4) 5)))

    -->(inc (+ 3 5))

    -->(inc (if (= 3 0) 5 (inc (+ (dec 3) 5))))

    -->(inc (inc (+ 2 5)))

    -->(inc (inc (if (= 2 0) 5 (inc (+ (dec 2) 5)))))

    -->(inc (inc (inc (+ 1 5))))

    -->(inc (inc (inc (if (= 1 0) 5 (inc (+ (dec 1) 5))))))

    -->(inc (inc (inc (inc (+ 0 5)))))

    -->(inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5)))))))

    -->(inc (inc (inc (inc 5))))

    -->(inc (inc (inc 6)))

    -->(inc (inc 7))

    -->(inc 8)

    -->9

    为线性递归;

    对于过程

    (define (+ a b)

      (if (= a 0)

          b

          (+ (dec a) (inc b))))

    计算(+ 4 5)时的替换过程为

    -->(+ 4 5)

    -->(if (= 4 0) 5 (+ (dec 4) (inc 5)))

    -->(+ 3 6)

    -->(if (= 3 0) 6 (+ (dec 3) (inc 6)))

    -->(+ 2 7)

    -->(if (= 2 0) 7 (+ (dec 2) (inc 7)))  

    -->(+ 1 8)

    -->(if (= 1 0) 8 (+ (dec 1) (inc 8))) 

    -->(+ 0 9)

    -->(if (= 0 0) 9 (+ (dec 0) (inc 9)))

    -->9         

    为线性迭代.

 

  练习1.10

 

    (A 1 10)-->(A 0 (A 1 9))

        -->(* 2 (A 1 9))

        -->(* 2 (A 0 (A 1 8)))

        -->(* 2 (* 2 (A 1 7)))

        -->......

        -->2^10

    (A 2 4) -->(A 1 (A 2 3))

        -->(A 1 (A 1 (A 2 2)))

        -->(A 1 (A 1 (A 1 (A 1 (A 2 1)))))

        -->(A 1 (A 1 (A 1 (A 1 2))))

        -->(A 1 (A 1 (A 1 2^2)))

        -->(A 1 (A 1 2^4))

        -->(A 1 2^8)

        -->2^16

    (A 3 3) -->(A 2 (A 3 2))

        -->(A 2 (A 2 (A 3 1)))

        -->(A 2 (A 2 2))

        -->(A 2 2^2)

        -->2^16

 

    (A 0 n) -->2n

    (A 1 n) -->2^n

    (A 2 n) -->2^(2^n)

分享到:
评论

相关推荐

    sicp-Structure and Interpretation of Computer Programs

    - **1.2.1 线性递归和迭代**(Linear Recursion and Iteration):比较两种不同的过程结构。 - **1.2.2 树形递归**(Tree Recursion):探讨树形递归的概念及其应用场景。 - **1.2.3 增长阶**(Orders of Growth...

    Structure and Interpretation of Computer programs sicp

    - **1.2.1 线性递归与迭代**: 探讨不同类型的递归模式。 - **1.2.2 树递归**: 分析更复杂的递归模式,如树形结构的遍历。 - **1.2.3 成长顺序**: 分析算法的时间和空间复杂度。 - **1.2.4 幂运算**: 讨论幂运算...

    SICP(计算机体系结构)

    - **1.2.1 线性递归与迭代**: 比较两种不同类型的递归算法。 - **1.2.2 树形递归**: 探讨一种复杂度较高的递归形式。 - **1.2.3 成长的阶次**: 分析算法的时间和空间复杂度。 - **1.2.4 幂运算**: 实现快速幂...

    Structure Interpration of Computer Programs(英文版)

    - **1.2.1 线性递归与迭代**:比较线性递归和迭代两种不同类型的算法,并分析它们之间的差异。 - **1.2.2 树形递归**:介绍树形递归的概念,这是一种常见的递归形式,用于解决具有复杂分支结构的问题。 - **1.2.3...

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

    通过学习SICP,学生将能够理解如何设计、分析和实现复杂的程序系统,培养出强大的抽象思维能力。 课程内容涵盖了以下几个关键知识点: 1. **基本编程概念**:包括变量、数据结构(如列表、树)、控制结构(条件...

    sicp_notes:SICP笔记和练习

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

    sicp 2016 from

    - **线性递归与迭代 (Linear Recursion and Iteration)**:比较了两种不同的计算方式及其效率差异。 - **树形递归 (Tree Recursion)**:探讨了如何通过递归来解决分治类型的问题。 - **增长阶次 (Orders of ...

    SICP 习题答案

    - **迭代与循环**:虽然函数式编程倾向于使用递归,但SICP也讨论了迭代结构,如do循环和while循环。 7. **过程的组合与复合**: - **过程复合**:将简单过程组合成复杂过程,以实现更复杂的计算逻辑。 - **局部...

    SICP LISP AI

    5. **控制结构和计算的表示**:书中详细分析了条件表达式、迭代和递归等控制结构,并探讨了如何用过程来模拟不同的计算模型,如图灵机和微处理器。 6. **对象和模拟**:通过引入面向对象的概念,SICP展示了如何用...

    sicp 2.2.4节图形语言

    总的来说,SICP 2.2.4节的图形语言不仅是学习Scheme或Racket编程的一个重要部分,更是对计算思维和编程艺术的一次深入探索。通过实践和理解这些概念,你将能更好地理解和创造计算世界中的视觉表现形式。

    SICP 解题集

    SICP是计算机科学领域的一本经典教材,由Harold Abelson、Gerald Jay Sussman和Julie Sussman共同撰写,它以其独特的视角深入浅出地介绍了计算机编程的本质,特别是函数式编程思想和递归算法的设计。 SICP的核心...

    a_book_sicp_py

    本书名为《a_book_sicp_py》,是一本以Python语言为基础介绍设计模式和计算机科学基础的书籍。根据描述和部分内容,可以提炼出以下知识点: 1. 编程语言的重要性:在计算机科学的宽泛领域中,编程语言扮演着至关...

    sicp第二章练习题的解答

    通过这个文件,读者可以系统地查看和学习整个章节的关键概念和解题策略。 3. **queens.ss**: "Queens问题"是一个经典的问题,涉及到在棋盘上放置皇后,使得没有任何两颗皇后可以相互攻击。这个文件可能包含了解决八...

    Learn_sicp:学习sicp的一些代码

    5. **递归和迭代**:SICP中,递归是解决各种问题的核心工具。通过递归,你可以解决包括排序、搜索和图遍历在内的各种问题。同时,Racket提供了一流的迭代支持,如for和match表达式。 6. **组合器和解释器**:SICP教...

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

    通过实践和思考这些习题,学习者不仅能掌握SICP的理论知识,还能提升编程思维和问题解决能力。对于想要深入理解计算机程序本质的人来说,SICP是一本不可或缺的参考书,而这些习题解答则为自学提供了宝贵的资源。

    SICP(python中文带书签)

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

    精通递归程序设计

    - [《Structure and Interpretation of Computer Programs》](https://mitpress.mit.edu/sites/default/files/sicp.pdf) —— 一本经典教材,深入探讨了递归和其他计算机科学主题。 - [《Programming Pearls》]...

    sicp in python 中文 sicp 中文

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

Global site tag (gtag.js) - Google Analytics