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

SICP学习笔记 1.2.3 增长的阶

    博客分类:
  • SICP
 
阅读更多

    练习1.14

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
		((or (< amount 0) (= kinds-of-coins 0)) 0)
		(else (+ (cc amount (- kinds-of-coins 1))
				 (cc (- amount (first-denomination kinds-of-coins))
					 kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
		((= kinds-of-coins 2) 5)
		((= kinds-of-coins 3) 10)
		((= kinds-of-coins 4) 25)
		((= kinds-of-coins 5) 50)))

 

 

    图为二叉树,其中由根节点到最底层的叶子的路径为
    (cc 11 5)->(cc 11 4)->(cc 11 3)->(cc 11 2)->(cc 11 1)->(cc 10 1)->(cc 9 1)->(cc 8 1)->(cc 7 1)->(cc 6 1)->(cc 5 1)->(cc 4 1)->(cc 3 1)->(cc 2 1)->(cc 1 1)->(cc 0 1)
    则数的深度为n+5,则空间增长阶为O(n)
  

    设f(n, k)为计算amount分为kinds种货币时需要的步骤,则由图中可知
    f(1, 1)=2
    f(2, 1)=4
    f(3, 1)=6
    ......
    则有f(n, 1) = 2*n,则f(n, 1)步骤增长阶为O(n)

    而f(n, 2) = f(n, 1) + f(n-5, 2)f(n-5, 2), f(n-5, 2) = f(n-5, 1) + f(n-5*2, 2) ......
    设m=n/5(整数),则有
    f(n, 2) = f(n-5*0, 1) + f(n-5*1, 1) + f(n-5*2, 1) + ...... + f(n-5*m, 1)
              = 2*[(n-5*0) + (n-5*1) + (n-5*2) + ...... + (n-5*m)]
              = 2*[n*m - 5*(0 + 1 + 2 + ...... +m)]
              = 2*[n*m - 5*[m*(m+1)/2]]
              = 2*n*m - 5*(m^2+1)
    则有f(n, 2)步骤增长阶为O(n^2)

    同理推得f(n, 5)步骤增长阶为O(n^5)

 

    练习1.15

 

define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

 

    (sine 12.15) --> (p (sine 4.05))
                      --> (p (p (sine 1.35)))
                      --> (p (p (p (sine 0.45))))
                      --> (p (p (p (p (sine 0.15)))))
                      --> (p (p (p (p (p (sine 0.05))))))
            
    a) 12.15=0.05*3^5,p被使用5次
    b) 设a=x*3^n,其中x小于0.1,则有
    a/3^n=x<0.1
    --> 10a/3^n<1
    --> 10a<3^n
    --> lg(10a)<lg(3^n)
    --> lg(10a)/lg3<n
    则其增长的阶为O(lga)

 

  • 大小: 39.9 KB
0
0
分享到:
评论

相关推荐

    sicp-Structure and Interpretation of Computer Programs

    - **1.2.3 增长阶**(Orders of Growth):分析算法的时间复杂度。 - **1.2.4 幂运算**(Exponentiation):介绍幂运算的不同实现方法。 - **1.2.5** - **第二章:通过数据构建抽象**(Building Abstractions ...

    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 2.2.4节图形语言

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

    SICP(python中文带书签)

    在Python中实现SICP的概念,可以帮助我们更好地理解函数式编程的精髓,例如高阶函数、闭包、递归以及过程抽象等。Python提供了`lambda`表达式、`map()`、`filter()`和`reduce()`等工具,这些都与Lisp的特性相呼应,...

    sicp_notes:SICP笔记和练习

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

    SICP 解题集

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

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

    SICP常常引导学生用列表来表示和操作数据,如列表的过滤、映射、折叠等高阶函数。1.22可能是一个关于列表处理的挑战,如实现一个函数,可以对列表进行特定的变换或者查找列表中的模式。 3. **1.28.ss**: 可能与环境...

    SICP 习题答案

    - **高阶函数**:能够接受函数作为参数或返回函数的函数,例如map、filter和reduce等。 - **递归**:函数调用自身的技术,常用于解决可重叠子问题,如斐波那契数列的计算。 3. **数据结构**: - **列表**:SICP...

    SICP-Python版本

    SICP-Python版本

    Python SICP epub版本

    Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用

    SICP 使用的scheme解释器

    SICP 使用的scheme解释器 以前叫DrScheme

    a_book_sicp_py

    6. 高阶函数的应用:高阶函数是那些可以接受其他函数作为参数或者返回一个函数的函数。这种抽象是函数式编程的核心特征之一,它在Python中也被广泛支持,并可以用来编写更加灵活和可重用的代码。 7. 计算机程序的...

    SICP LISP AI

    4. **数据结构和抽象**:SICP介绍了各种数据结构,如列表、树和队列,以及如何使用递归和高阶函数来操作它们。此外,还讨论了如何通过抽象隐藏实现细节,提高代码的复用性和可维护性。 5. **控制结构和计算的表示**...

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

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

    sicp 2016 from

    - **使用高阶过程建立抽象 (Formulating Abstractions with Higher-Order Procedures)** - **作为参数的过程 (Procedures as Arguments)**:展示如何将过程作为参数传递给其他过程。 - **使用 lambda 构建过程 ...

    PyPI 官网下载 | sicp-0.0.1b102.dev4.tar.gz

    标题中的"PyPI 官网下载 | sicp-0.0.1b102.dev4.tar.gz"指的是从Python的官方包索引(Python Package Index,简称PyPI)上下载的一个名为"sicp"的软件包的版本号为0.0.1b102.dev4的压缩文件,其格式是tar.gz。...

    Learn_sicp:学习sicp的一些代码

    《学习SICP:探索Racket编程的艺术》 SICP,全称为《Structure and Interpretation of Computer Programs》(计算机程序的结构与解释),是一本经典的计算机科学教材,由Harold Abelson和Gerald Jay Sussman合著,...

    sicp-memo-ans:SICP笔记和答案

    请参考那些正在学习SICP的人。 笔记 如果你想在 gauch 中使用随机函数 (use math.mt-random) (define m (make &lt;mersenne&gt; :seed (sys-time))) (mt-random-integer m 1000) (define (random n) (mt-random-integer ...

Global site tag (gtag.js) - Google Analytics