SICP学习笔记04 vvipi 发表于2018年11月9日,阅读:2257 ### 练习1.12 画帕斯卡三角形,也就是杨辉三角 ### 解答 ```scheme (define (pascal row col) ; 计算某行某列的数字 (if (or (= col 1) (= col row)) 1 (+ (pascal (- row 1) col) (pascal (- row 1) (- col 1))))) (define (drawrow n) ; 画出第n行 (define (dr count n) (if (= count n) (begin (display (pascal n count)) (display "\n")) (begin (display (pascal n count)) (display " ") (dr (+ count 1) n)))) (dr 1 n)) (define (spaces n) ; 画n个空格 (define (repeat count n) (if (= n 0) (display "") (if (= count n) (display " ") (begin (display " ") (repeat (+ count 1) n))))) (repeat 1 n)) (define (pascaltriangle x) ; 画x行杨辉三角 (define (loop count x s) (if (= count x) (begin (spaces s) (drawrow count)) (begin (spaces s) (drawrow count) (loop (+ count 1) x (- s 1))))) (loop 1 x (- x 1))) (pascaltriangle 6) (exit) ``` ### 理解 最初卡在如何构造递归的函数,不知道该用什么参数去递推。想了半天没有突破就看了参考答案,发现可以用row和col两个参数来计算特定位置的一个数字,于是按这个思路开始写。能求出指定位置的数字后,就可以顺理成章画出一行,为了美观再增加一个画n个空格的方法。效果如下: ![](/download?fn=img_0015417302379266210587256d34197baec9be4c776ccb4000) 迭代版本太难,半天想不出来。参考答案和维基百科指出第n行k列的数字等于C(n,k),即排列组合中,从n个元素中取k个,可能的组合数。感觉很神奇,不知道是如何联系起来的。没有看到证明。 运用这个特性,可以有另一个公式C(n,k) = n! / (k! * (n - k)!),可以根据这个公式写出迭代版的方法。迭代版本计算很快,可以快速输出很多行。 观察发现用这个公式算出来的是去掉最左边的一列数字1的,因此略微改动代码,使之输出题目中的形态。 书中没有对scheme的语法进行专门介绍,用多少讲多少,我搜索后才知道可以用(begin task1 task2)来顺序执行。没有for循环还是不太习惯,但已经可以用递归写出简单的1-n循环。 ```scheme (define (pascal row col) ; 计算某行某列的数字 (if (or (= col 1) (= row col)) 1 (/ (factorial (- row 1)) (* (factorial (- col 1)) (factorial (- (- row 1) (- col 1))))))) (define (factorial n) ; 计算阶乘 (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) (fact-iter 1 1 n)) ```