这个函数的要求是返回1个list，这个list的每个元素是杨辉三角的1行， 子list的每个元素则对应杨辉三角该行的每个值。

完整的问题描述及要求是这样的： 函数要求

思路

算法复杂度就不去分析了，只考虑如何用racket把这个要求做出来。

这个问题，显然是一个递归问题，下一行的某些元素需要根据上一行的元素求出来， 不断重复这个过程，直到全部求解完成。头2行比较特殊一点，全部元素都是每行2端的元素， 都是1。

按照图片中的提示，先写element函数，再调用element求出每行的结果， 这个做法当然是可以的，只是，很显然存在大量的重复计算问题，因为， 上一行的结果是可以“缓存”下来的，它却没有。

函数实现

element函数的实现如下：

1
2
3
4
5
6
7
8
9

(define (element row col)
  ;; 作者：徐工， 微博：@徐工徐工2020，头条：@徐工徐工
  (cond
    ((or (> 1 row) (> 1 col) (< row col))
     '()) 
    ((or (= 1 col) (= row col))
     1)
    (else
     (+ (element (- row 1) (- col 1)) (element (- row 1) col)))))

level函数就是对一个list迭代，用haskell写的话会很简单，直接写成[1..x]就o了， racket依然要上递归，再套层壳整优雅点儿。

1
2
3
4
5
6
7

(define (level n)
  ;; 作者：徐工， 微博：@徐工徐工2020，头条：@徐工徐工
  (define (_lev i c)
    (if (< i c)
        '()
        (cons (element i c) (_lev i (+ 1 c)))))
  (_lev n 1))

测试结果

做了2组测试，(level 4) = '(1 3 3 1)，(level 7) = '(1 6 15 20 15 6 1)，看上去一切正常。

benchmark一下，求杨辉三角27行的元素，Dr Racket v8.10下(time (void (level 27)))用时5.668s， 28行似乎已经跑不出来了。😂

使用带“缓存”的方式重写了一下，优化后level的跑333行毫无压力，用(time (void (level2 333)))测试， Dr Racket v8.10下跑完用时0.017s！😁

收工，优化版的就不贴出来了。