sicp-ex-1.12


Computes an entry in the Pascal triangle given the row and column. Rows start from 1, counting from above; columns start from 1 too, counting from left to right.

  
 ;; ex 1.12 
  
 (define (pascal-triangle row col) 
   (cond ((> col row) 0) 
         ((< col 0) 0) 
         ((= col 1) 1) 
         ((+ (pascal-triangle (- row 1) (- col 1)) 
             (pascal-triangle (- row 1) col))))) 
  
 ;; Testing 
 (pascal-triangle 1 1) 
 (pascal-triangle 2 2) 
 (pascal-triangle 3 2) 
 (pascal-triangle 4 2) 
 (pascal-triangle 5 2) 
 (pascal-triangle 5 3) 
  

I find this one easier to grok, it allows only values though:

 (define (pascal row col) 
   (cond ((or (< row col)  
              (< col 1)) 0 ) 
         ((or (= col 1) 
              (= col row)) 1) 
         (else (+ (pascal (- row 1) (- col 1)) 
                  (pascal (- row 1) col ))))) 
  

Not having to worry about zero values makes it clearer to me:

 ;; rows / elements numbered starting at 1 
 ;; first / last elements in a row = 1 
 (define (ptcell r e) 
     (cond ((= e 1) 1) 
           ((= e r) 1) 
           (else (+ (ptcell (- r 1) (- e 1)) 
                    (ptcell (- r 1) e))))) 

Another intuitive version:

 ;;; Represent pascal-triangle in coordination: the point 1 is at (0, 0); 
 ;;; (-1, 0) is occupied by 0, and other potential blank places are 
 ;;; also 0. Then 
 ;;;                         |- yanghui(r+1, c-1) + yanghui(r+1, c+1), if r < 0 
 ;;; yanghui(r, c) =    | 1, if r = 0, c = 0 
 ;;;                         |- 0, otherwise 
 (define (yanghui r c) 
   (cond 
    ((< r 0) 
     (+ (yanghui (+ r 1) (- c 1)) 
                 (yanghui (+ r 1) (+ c 1)))) 
    ((and (= r 0) (= c 0)) 1) 
    (else 0))) 
  

Off on a tangent having misread the question & skipping ahead a few chapters:

;;; calculates nth row of pascal's triangle as a list
(define (pascal n)
  (define (p-row prev)
    (cond ((null? (cdr prev)) (list 1))
          ((= 1 (car prev)) (cons 1 (cons (+ (car prev) (cadr prev)) (p-row (cdr prev)))))
          (else (cons (+ (car prev) (cadr prev)) (p-row (cdr prev))))))
  (cond ((< n 1) (display "error: one or more rows"))
        ((= n 1) 1)
        ((= n 2) (list 1 1))
        (else (p-row (pascal (- n 1))))))

<< Previous exercise (1.11) | sicp-solutions | Next exercise (1.13) >>