Exercise1-11 <---> Exercise1-13
Exercise 1.12
The following pattern of numbers is called Pascal's triangle.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
Ru: Приведенная выше таблица называется треугольником Паскаля (Pascal's triangle).
Все числа по краям треугольника равны 1, а каждое число внутри треугольника равно сумме двух чисел над ним. Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощью рекурсивного процесса.
Scheme solution:
(define (pascal m n)
(cond
((> m n) 'error) ;; return error symbol, incorrect input data
((= 0 m) 1)
((= m n) 1)
(else (+
(pascal (- m 1) (- n 1))
(pascal m (- n 1))))))
Caution: The solutions below differ from the Scheme solution above. In the solution above, "m" designates the row number, and "n" designates the place in a row. In the solutions below, the rows run "diagonally"; i.e. the row number is "m+n", and "n" designates the place in a row.
Haskell solution:
pascal 1 _ = 1
pascal _ 1 = 1
pascal n m = pascal (n-1) m + pascal n (m-1)
OCaml solution:
let rec pascal n m = match n, m with
1, _
| _, 1 -> 1
| n, m -> pascal (n-1) m + pascal n (m-1)
Standard ML solution:
fun pascal (1, _) = 1
| pascal (_, 1) = 1
| pascal (n, m) = pascal (n-1, m) + pascal (n, m-1)
Oberon/Component Pascal solution:
PROCEDURE Pascal (n, m : INTEGER) : INTEGER;
VAR result : INTEGER;
BEGIN
IF (n = 1) OR (m = 1) THEN
result := 1
ELSE
result := Pascal(n-1, m) + Pascal(n, m-1)
END;
RETURN result
END Pascal;
Exercise1-11 <---> Exercise1-13
Comments
| Чёй-то я не допонял решение на схеме - зачем нужна проверка на (m > n) ? | ||||
| Posted by Geniepro at 2007-09-15 13:49:41 | ||||
А, понял, мы по разному представляем себе оси треугольника: я так: n 1 2 3 4 5 m 1 1 1 1 1 1 2 1 2 3 4 3 1 3 6 4 1 4 5 1 или 1 1
2/1\2
3/1 1\3
4/1 2 1\4
5/1 3 3 1\5
n/1 4 6 4 1\mа ты, видимо, типа так: n 012345678 m 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 | ||||
Posted by Geniepro  at 2007-09-15 14:03:55 | ||||
У меня треугольник представляется так: n 1 2 3 4 5 m 1 1 2 1 1 3 1 2 1 4 1 3 3 1 5 1 4 6 4 1 При такой нумерации каждый элемент треугольника равен соответствующему биномиальному коэффициенту, то есть pascal(m, n) = c(m, n) Так вроде идейнее | ||||
| Posted by IvanVeselov at 2007-09-15 15:08:01 | ||||
Wait, I'm confused. This doesn't generate a triangle of numbers. Am I missing something? | ||||
| Posted by dsl081-032-138 at 2008-09-23 19:09:56 X | ||||
;; Typically, the call of pascal would be (pascal m n). ;; This will generate the number at row m, ;; column n in a pascal triangle. Typically, n <= m. ;; So, n will reach 0 before m. In this case, we simply ;; return 0 to avoid computing such branches of recursion tree. (define (pascal m n)
(cond
[(= m 0) 1]
[(= n 0) 0]
[(= m n) 1]
[else (+
(pascal (- m 1) (- n 1))
(pascal (- m 1) n))]))
;; generate a list to represent a pascal sequence triangle
(define (gen-pascal m n)
(if (= m 0)
'()
(cons (gen-pascal-row m n)
(gen-pascal (- m 1) (- n 1)))))
(define (gen-pascal-row m n)
(if (= n 0)
'()
(cons (pascal m n)
(gen-pascal-row m (- n 1))))) | ||||
| Posted by Nikolai Roman at 2008-10-07 08:11:40 | ||||
Более понятное решение, которое способно рассчитать элемент №2 из строки №4 (т.е. где m>n) (define (pascal stringNumber elementNumber)
| ||||
| Posted by 62 at 2008-10-20 17:44:18 X | ||||
| Извиняюсь, слетело форматирование (define (pascal stringNumber elementNumber) (cond ((= stringNumber 1) 1) ((= stringNumber elementNumber) 1) ((= elementNumber 1) 1) (else (+ (pascal(- stringNumber 1) (- elementNumber 1)) (pascal(- stringNumber 1) elementNumber))))) | ||||
| Posted by 62 at 2008-10-20 17:46:31 X | ||||
;To generate the Pascal triangle call (pascal n) with n as the depth of the triangle you want to display. Replace print and newline by whatever writes to console. Gives output in the form:
;1
;11
;121
;1331
;14641
;15101051
;1615201561
(define (inc x)
(+ x 1))
(define (dec x)
(- x 1))
(define (pascal-element row col)
(cond ((= col 1) 1)
((= row col) 1)
(else (+
(pascal-element (dec row) (dec col))
(pascal-element (dec row) col)))))
(define (pascal-row row colcount)
(cond ((not (= colcount row))
(print (pascal-element row (inc colcount)))
'()
(pascal-row row (inc colcount)))))
(define (pascal-row-col row rowcount)
(cond ((not (> rowcount row))
(pascal-row rowcount 0)
(newline)
(pascal-row-col row (inc rowcount)))))
(define (pascal n)
(pascal-row-col n 1))
;(pascal 7) etc. | ||||
| Posted by SriramDevadas at 2009-03-11 20:20:06 | ||||
