Решение упражнения 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))))

Comment from Simka
Date: May 29, 2012, 12:57 am

(define(pascal x y)(cc x y))
(define(cc a z)
  (cond
    ((= a z)1)
    ((=(+ a z)0)1)
    ((< z 0)error)
    (else(+(cc(- a 1)(- z 1))(cc(+ a 1)(- z 1))))))

Comment from povloid
Date: December 10, 2012, 9:36 pm

решил сделать немного по другому. Повернуть пирамидку на 45 градусов и представить все как:

1 1 1 1 1 1 (ось x)
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252

(ось y)

нахождение нужного элемента по координатам x y


(define (f x y)
(if (or (= x 1) (= y 1)) 1
(+ (f (- x 1) y) (f x (- y 1)))))

Comment from povloid
Date: December 10, 2012, 10:11 pm

Продолжение темы про координаты x y. Теперь чтобы находить в координатах пирамиды то достаточно добавить функцию конвертации строки и номера элемента в координаты x y:


(define (f-xy x y)
(if (or (= x 1) (= y 1)) 1
(+ (f-xy (- x 1) y) (f-xy x (- y 1)))))

(define (f row num)
(f-xy num (+ row (- num) 1)))

Comment from Dzmitry
Date: October 22, 2016, 7:57 pm

Как я понимаю все решения здесь предполагают знание координат элемента. Но что если нам известен только порядковый номер числа Паскаля? То есть представим все числа Паскаля в виде последовательности 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 … и т.д. Нужно найти, например, число с порядковым номером 67, то есть к примеру (pascal 67). Предлагаю своё решение для данной постановки задачи:

(define (pascal n)
        (define ( x y)
                )
        )
        (define (stepM m count)
                (define (stepK m k count)
                        (define (stepCMK m k)
                                (define (factorial number)
                                        (if (= number (or 0 1)) 1 (* number (factorial (- number 1)))
                                        )
                                )
                                (/ (factorial m) (* (factorial k) (factorial (- m k)))
                                )
                        )
                        (if (< (+ count 1) n) (stepK m (+ k 1) (+ count 1)) (stepCMK m k)
                        )
                )
                (if (<= (+ (+ m 2) count) n) (stepM (+ m 1) (+ (+ m 2) count)) (stepK (+ m 1) 0 count)
                )
        )
        (stepM 0 1
        )
)

Comment from Dzmitry
Date: October 22, 2016, 8:02 pm

Извиняюсь за код выше – скопировался не правильно. Не знаю как пользоваться правильно редактором и тегами =). Если интересует решение – пишите на kosarev@tut.by – вышлю. Спасибо за сайт.

Write a comment