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

SICP学习笔记 2.2.2 层次性结构

    博客分类:
  • SICP
阅读更多

    练习2.24

;; 嵌套结构的list
1 ]=> (list 1 (list 2 (list 3 4)))
;Value : (1 (2 (3 4)))

 *
/ \
1  *
 /   \
 2    * 
    /   \
    3   4

 

    练习2.25

;; (1 3 (5 7) 9)
1 ]=> (define list1 (list 1 3 (list 5 7) 9))
1 ]=> list1
;Value : (1 3 (5 7) 9)

1 ]=> (car (cdr (car (cdr (cdr list1)))))
;Value: 7

;; ((7))
1 ]=> (define list1 (list (list 7)))
1 ]=> list1
;Value : ((7))

1 ]=> (car (car list1))
;Value: 7

;; (1 (2 (3 (4 (5 (6 7))))))
1 ]=> (define list1 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
1 ]=> list1
;Value : (1 (2 (3 (4 (5 (6 7))))))

1 ]=> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr list1))))))))))))
;Value: 7
 

     练习2.26

1 ]=> (append x y)
;Value : (1 2 3 4 5 6)

1 ]=> (cons x y)
;Value : ((1 2 3) 4 5 6)

1 ]=> (list x y)
;Value : ((1 2 3) (4 5 6))

    

    练习2.27

(define (deep-reverse items)
  (cond ((null? items) '())
	      ((pair? (car items))
	       (append (deep-reverse (cdr items))
		             (list (deep-reverse (car items)))))
	      (else
	       (append (deep-reverse (cdr items))
		             (list (car items))))))
 

    练习2.28

;; 采用递归的方式,如果是序对就将左子树和右子树的结果拼接,否则直接拼接
(define (fringe items)
  (define (frings-iter things answer)
    (cond ((null? things) answer)
	        ((pair? things)
	         (append (frings-iter (car things) answer)
		               (frings-iter (cdr things) answer)))
	        (else
	         (append answer (list things)))))
  (frings-iter items '()))
 

    练习2.29

;; a
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (cdr mobile))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (car (cdr branch)))
  
;; b
;; 先检查是不是二叉活动体,如果是则递归求两个分支的重量
;; 再检查分支的structure是否仍然是活动体, 如果是则递归求structure的重量
;; 最后对于最简单的分支情况直接相加重量
(define (total-weight mobile)
  (define (mobile-flag m)
    (pair? (left-branch m)))
  (define (branch-flag m)
    (pair? (branch-structure m)))
  (define (total-weight-iter m tw)
    (cond ((null? m) tw)
	        ((mobile-flag m) (+ (total-weight-iter (left-branch m) tw)
			                        (total-weight-iter (right-branch m) tw)))
	        ((branch-flag m) (+ (total-weight-iter (branch-structure m) tw)))
	        (else (+ tw (branch-structure m)))))
  (total-weight-iter mobile 0))

;; 或者可以将活动体的重量看做是两个分支重量之和
;; 但是在对分支求重量时仍然要区分是否还有分支
(define (total-weight mobile)
  (if (pair? (left-branch mobile))
      (+ (branch-weight (left-branch mobile)) 
	       (branch-weight (right-branch mobile)))
      (branch-weight mobile))) 
(define (branch-weight branch)
  (let ((structure
	       (if (null? (right-branch branch))
	           (left-branch branch)
	           (branch-structure branch))))
    (if (pair? structure)
	      (branch-weight structure)
	      structure)))
;; c
;; 首先定义分支的力矩,依据其是否有分支分别处理
(define (branch-value branch)
  (if (null? (right-branch branch))
      (* (branch-length (left-branch branch)) (branch-weight branch))
      (* (branch-length branch) (branch-weight branch))))

;; 然后实现活动体的检测过程:两个分支平衡且两个分支的力矩相等
(define (check-balance mobile)
  (if (pair? (left-branch mobile))
      (and (check-balance (left-branch mobile))
	         (check-balance (car (right-branch mobile)))
	         (= (branch-value (left-branch mobile))
	            (branch-value (right-branch mobile))))
      #t))
  
;; d
;; 需要对structure过程修改
(define (branch-structure branch)
  ;;(car (cdr branch)))
  (cdr branch))
  
(define (check-balance mobile)
  (if (pair? (left-branch mobile))
      (and (check-balance (left-branch mobile))
	         ;;(check-balance (car (right-branch mobile)))
	         (check-balance (right-branch mobile))
	         (= (branch-value (left-branch mobile))
	            (branch-value (right-branch mobile))))
      #t))
;; 验证  
(define mtest 
  (make-mobile (make-branch 3 4)
			         (make-branch 2 6)))
1 ]=> (total-weight mtest)
;Value: 10			         
		
1 ]=> (check-balance mtest)
;Value: #t	
 

    练习2.30

(define (square-tree tree)
  (cond ((null? tree) '())
	      ((not (pair? tree)) (square tree))
	      (else (cons (square-tree (car tree))
		                (square-tree (cdr tree))))))
(define (map-square-tree tree)
  (map (lambda (sub-tree)
	        (if (pair? sub-tree)
	            (map-square-tree sub-tree)
	            (square sub-tree)))
       tree))
       
1 ]=> (square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))

1 ]=> (map-square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))

 

    练习2.31

(define (tree-map fun tree)
  (map (lambda (sub-tree)
      	 (if (pair? sub-tree)
      	     (tree-map fun sub-tree)
      	     (fun sub-tree)))
       tree))
       
1 ]=> (define (square-tree-test tree) (tree-map square tree))
;Value : square-tree-test

1 ]=> (square-tree-test (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))
 

    练习2.32

;; 仿照换零钱的例子
;; rest取不包含(car s)元素的所有剩余元素的组合
;; 则应加上(car s)元素与所有剩余元素的组合
(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
	      (append rest (map (lambda (r) (append (list (car s)) r)) rest)))))
	
1 ]=> (subsets s)
;Value : (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
 

 

 

 

0
0
分享到:
评论

相关推荐

    SICP(计算机体系结构)

    - **2.2.2 层次结构**: 探讨层次数据结构的特点和优势。 - **2.2.3 作为传统接口的序列**: 讲解序列作为数据交互标准的重要性。 - **2.2.4 示例:图像语言**: 通过图形化语言的例子进一步理解层次数据结构的应用...

    SICP 习题答案

    - **递归数据结构**:如树和图,可以通过递归定义来表示,这在处理层次结构的问题中非常有用。 - **表处理**:SICP介绍了基于链表的表结构,包括表的创建、访问和修改操作,以及表操作的高效实现,如尾递归优化。 ...

    sicp 2.2.4节图形语言

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

    sicp in python 中文 sicp 中文

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

    SICP:学习计算机程序的结构和解释

    《SICP:学习计算机程序的结构和解释》是一本极具影响力的计算机科学教材,由Harold Abelson和Gerald Jay Sussman合著,并由 MIT Press 出版。这本书主要探讨了程序设计的基础原理和方法,通过使用Scheme编程语言...

    SICP中文第二版

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

    SICP 解题集

    《SICP解题集》是一份专注于探讨和解答《结构与解释程序》(Structure and Interpretation of Computer Programs,简称SICP)一书中习题的资源。SICP是计算机科学领域的一本经典教材,由Harold Abelson、Gerald Jay ...

    SICP(python中文带书签)

    Python虽然并非原书中的教学语言,但由于其易读性和广泛应用,许多读者选择使用Python来实践SICP中的概念。 在Python中实现SICP的概念,可以帮助我们更好地理解函数式编程的精髓,例如高阶函数、闭包、递归以及过程...

    SICP LISP AI

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

    数据结构与算法分析学习笔记chm

    ^_^这本教科书所使用的是C语言,也许很多人会说C语言已经过时了,但是,我认为在数据结构的学习中,应该用尽量简单的语言,以免进入了语言的细枝末节中,反而冲淡了主题。实际上在国外的许多大学中(甚至中学),...

    sicp_notes:SICP笔记和练习

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

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

    SICP的第一章通常会介绍Lisp语言的基础,包括如何创建基本的函数,如何使用递归来处理数学问题,以及如何通过过程抽象将重复代码封装起来,提高代码的可读性和复用性。例如,可能会有求阶乘、斐波那契数列等典型的...

    sicp-Structure and Interpretation of Computer Programs

    ### SICP——《计算机程序的结构与解释》 #### 一、概述 《计算机程序的结构与解释》(Structure and Interpretation of Computer Programs, 简称SICP)是一本由MIT电气工程与计算机科学系教授Harold Abelson和...

    a_book_sicp_py

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

    SICP-Python版本

    SICP-Python版本

    sicp 2016 from

    ### 结构与解释计算机程序 (SICP) #### 标题和描述中的核心知识点解析 **《结构与解释计算机程序》(Structure and Interpretation of Computer Programs, SICP)** 是由哈佛大学的 Harold Abelson 和麻省理工学院...

    Python SICP epub版本

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

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

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

    SICP 使用的scheme解释器

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

Global site tag (gtag.js) - Google Analytics