Month: January, 2008

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

31 January, 2008 (22:59) | Решения упражнений | 3 comments

Определим сначала процедуру, генерирующую все наборы различных троек. Она строится аналогично процедуре, генерирующей все уникальные пары из прошлого упражнения (можно даже использовать unique-pairs в реализации, но я этого не буду делать: (define (unique-triples n)     (flatmap (lambda (i)           (flatmap (lambda (j)                 (map (lambda (k) (list i j k))                      (enumerate-interval 1 (- j […]

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

31 January, 2008 (22:45) | Решения упражнений | 1 comment

Процедура unique-pairs определяется способом, описанным в тексте параграфа: (define (unique-pairs n)   (flatmap (lambda (i) (map (lambda (j) (list i j))                             (enumerate-interval 1 (- i 1))))            (enumerate-interval 1 (- n 1)))) Теперь процедуру prime-sum-pairs легко определить таким образом, чтобы она генерировала все уникальные пары, фильтровала их, оставляя только пары с простой суммой, а затем строила тройки […]

Язык Scheme и обучение программированию

31 January, 2008 (21:41) | Языки программирования, Преподавание | 2 comments

Использование функциональных языков и, в частности, Scheme в обучении будущих программистов весьма популярно в вузах Европы и Америки. К сожалению, у нас эта практика, так же как и использование учебными заведениями операционных систем семейства Unix, пока не прижилась. Посмотрите на список вузов, колледжей и средних школ, использующих Scheme в процессе обучения. Обратите внимание на то, сколько вузов […]

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

31 January, 2008 (21:11) | Решения упражнений | 1 comment

Определить reverse через свертки можно таким образом: (define (reverse sequence)   (fold-right (lambda (x y) (append y (list x))) nil sequence)) (define (reverse sequence)   (fold-left (lambda (x y) (cons y x)) nil sequence)) Определения получаются путем анализа процесса вычислений сверток. Хочу отметить, что использование для реверсирования последовательности левой свертки более видится более эффективным, поскольку […]

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

31 January, 2008 (20:41) | Решения упражнений | 3 comments

Результаты, получаемые каждой из функций свертки, приведены ниже. Сначала я показываю ответ, а затем ход его построения для наглядности: (fold-right / 1 (list 1 2 3)) 1½ (/ 1 (/ 2 (/ 3 1))) (fold-left / 1 (list 1 2 3)) 1/6 (/ (/ (/ 1 1) 2) 3) (fold-right list nil (list 1 2 […]

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

30 January, 2008 (22:32) | Решения упражнений | 7 comments

Это упражнение может показаться сложноватым тем, кто не знаком с матричной арифметикой. На самом деле в ней нет абсолютно ничего сложного, но в нее нужно “въехать”, для чего вручную на бумажке поперемножать матрицы на вектора и другие матрицы. Без этого не удастся прочувствовать формулы и они останутся сухими и безжизненными. Кроме того, неплохо было бы […]

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

30 January, 2008 (22:10) | Решения упражнений | 1 comment

Не устаю восхищаться удачным подбором упражнений в книге. Фактически упражнения – это логическое продолжение основного текста, которые дают дополнительную пищу для размышлений и позволяют увидеть скрытые нюансы. Обобщенная процедура накопления accumulate-n строится поразительно просто. Достаточно лишь взять в соответствующих местах все первые элементы набора последовательностей и все “хвосты” последовательностей, то есть задействовать всеми любимые car и […]

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

30 January, 2008 (21:38) | Решения упражнений | 3 comments

Чрезвычайно приятное упражнение. Определение count-leaves с помощью накопления выглядит следующим образом: (define (count-leaves t)     (accumulate +                 0                 (map (lambda (x) (if (pair? x)                                      (count-leaves x)                                      1))                      t))) Смысл определения заключается в том, что мы вычисляем число листьев в дереве, суммируя числа листьев в каждом из его поддеревьев. Количество листьев […]

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

30 January, 2008 (21:15) | Решения упражнений | No comments

Вычисляя значение многочлена от переменной x по схеме Горнера, мы действуем по следующему принципу: берем младший коэффициент и прибавляем к нему x, умноженный на значение многочлена, построенного по остальным коэффициентам. Например, если обозначить многочлен как p, то p(1, 3, 0, 5, 0, 1)(x) = 1 + x * p(3, 0, 5, 0, 1)(x). Тогда накапливающая функция […]

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

30 January, 2008 (20:41) | Решения упражнений | 3 comments

В этом упражнении мы видим, что накопление является очень обобщенным процессом, которым можно описать совершенно разные на первый взгляд процедуры. Чтобы оперделить map через accumulate, начнем накопление с пустого списка и будем на этапе аккумулирования соединять с помощью cons результат применения отображающей процедуры с остальными результатами: (define (map p sequence)     (accumulate (lambda (x y) […]