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))))))

If you don't consider out of bounds cases, like negative numbers and other places outside the triangle, you can get a pretty simple solution. Push the triangle so it's left aligned with the 0th column, and you will see that if the column is 0 (in a 0-based world it's the left most of any depth) or if the col equals the depth (the last valid entry in that depth for the triangle), you will get 1. Otherwise, the value of the triangle is the number directly above it added to the number above and to the left.

 ;;;Left-aligned triangle, assuming the top most is at (col=0, depth=0) 
 ;;;1 
 ;;;1  1 
 ;;;1  2  1 
 ;;;1  3  3  1 
 ;;;1  4  6  4  1 
 ;;;1  5  10 10 5  1 
  
 (define (pascal col depth) 
   (cond  
     ((= col 0) 1) 
     ((= col depth) 1) 
     (else (+ (pascal (- col 1) (- depth 1))  
              (pascal col ( - depth 1)))))) 

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