Решение упражнения 1.12 из SICP

20 August, 2007 (00:41) | Решения упражнений

Будем адресовать элементы треугольника Паскаля двумя числами: номером строки (строки нумеруются сверху вниз) и порядковым номером элемента в этой строке (число элементов растет с движением от более высоких строк к более низким и равно номеру строки). Нумеровать строки и элементы будем начиная с единицы.

Запишем функцию, вычисляющую заданный элемент в заданной строке треугольника Паскаля:

(define (pascal row element)
  (cond ((or (= element 1) (= element row)) 1)
        ((and (> element 1) (< element row)) (+ (pascal (- row 1) (- element 1))
                                                (pascal (- row 1) element)))))

Нужно учесть, что значение, которое возвращает процедура, неопределено для некорректных значений номеров строки и элемента, например для неположительных их значений или для номеров элемента больших номера строки.

Comments

Comment from Vitaly
Date: October 5, 2007, 1:48 am

Не совсем понял условие с and, для чего оно?

У меня вот такое решение:

(define (f x y)
  (cond ((or (= x 1) (= y 1)) 1)
        (else (+ (f x (- y 1))
                 (f (- x 1) y)))))

Comment from Sergey Khenkin
Date: October 5, 2007, 10:11 am

Виталий,
спасибо за комментарий.

У нас в решениях немного разные системы координат.
Я располагаю треугольник Паскаля основанием вниз и вершиной вверх. Далее первый параметр задает номер горизонтального ряда чисел (строку), а второй - номер элемента в этой строке. Количество элементов в строках разное и увеличивается. Оно равно номеру строки.

Условие с and - это проверка на выход номера элемента за границы допустимых значений (от 1 до номера строки).

По-хорошему, нужно добавить еще одну глобальную проверку на то, чтобы номер строки был не меньше 1.

В твоем (ничего, что я на ты?) решении система координат такова, что оси x и y направлены параллельно ребрам треугольника. В этом случае область допустимых значений параметров - все пары натуральных чисел. Поэтому проверка, подобная моей с and, не нужна.

Кстати, очень симпатичное и компактное решение. Мне нравится!

Comment from eugene0
Date: January 16, 2009, 10:24 am

Мой вариант:


(define (triangle row num)
(cond ((or ( num row)) 0)
((= row 1) 1)
(else (+
(triangle (- row 1) (- num 1))
(triangle (- row 1) num)
)
)
)
)

Плюсы этого решения:
- при некорректных аргументах всегда возвращается 0,
- за счет того, что в “неправильных” местах треугольника теперь нули, экономим на проверке условия о том, что крайний элемент ряда равен 1, это получится автоматически.

Comment from eugene0
Date: January 16, 2009, 10:25 am

Упс, извините, что такой странный код получился, к сожалению, не нашел возможности предпросмотра.

Comment from синдикат
Date: January 21, 2010, 5:12 pm

(define (paskal row col)
(if (or (= col 1) (= row col))
1
(+ (paskal (- row 1) col)
(paskal (- row 1) (- col 1)))))
Принципиально не отличается (=

Comment from Anonymous
Date: February 21, 2010, 10:24 am

(define (f x y)
        (cond ((or (> y x) (< y 1)) 0)
              ((or (= x 1) (= y 1)) 1)
        (else (+ (f (- x 1) (- y 1)) (f (- x 1) y))))

Write a comment