SICP по-русски

В этом упражнении мы отвлечемся от программирования и опять займемся математикой. Итак, трансформация Tpq переводит пару (a, b) в пару (bq+aq+ap, bp+aq), что можно записать как Tpq: (a, b) <- (bq+aq+ap, bp+aq) или Tpq(a, b) = (bq+aq+ap, bp+aq). Вычислим Tpq²: Tpq²(a, b) = Tpq(Tpq(a, b)) = Tpq(bq+aq+ap, bp+aq) = = ([bp+aq]q+[bq+aq+ap]q+[bq+aq+ap]p, [bp+aq]p+[bq+aq+ap]q) = = (b[2pq+q²]+a[2pq+q²]+a[p²+q²], b[p²+q²]+a[2pq+q²]) […]

Процедура, порождающая итеративный процесс для умножения, приведена ниже: (define (fast-* a b)   (fast-*-iter a b 0)) (define (fast-*-iter a b c)   (cond ((= b 0) c)         ((even? b) (fast-*-iter (double a) (halve b) c))         (else (fast-*-iter a (- b 1) (+ c a)))))   Инвариант здесь ab+c=const. В начале вычислений c=0 […]

В этом упражнении все просто. Ниже приведен код процедуры. (define (fast-* a b)   (cond ((= b 0) 0)         ((= b 1) a)         ((even? b) (double (fast-* a (halve b))))         (else (+ a (fast-* a (- b 1))))))

Как и указано в условии упражнения, инвариантом будет abn = const. В начале процесса a полагаем равным 1 и как следствие результат будет равен bn. Условием выхода из процесса является n=0, а стало быть abn = a. Код процедуры приведен ниже: (define (fast-expt b n)   (fast-expt-iter 1 b n)) (define (fast-expt-iter a b n)   […]

При вычислении sine процедура p вызывается с аргументом sine от угла деленного на три. Это повторяется до тех пор, пока угол не станет меньше 0.1 по модулю. То есть, если x – начальный угол, то количество вызовов процедуры p (обозначим его n) будет удовлетворять следующему двойному неравенству: x / 3n ≤ 0.1 ≤ x / 3n-1. […]

В этом упражнении нет никаких хитростей. Нужно просто быть внимательным и уметь рисовать бинарные деревья (это не так просто как кажется). Правильное дерево приведено на рисунке ниже. В качестве иллюстрации важности внимательности приведу решение Кена Дика. Найдите в нем ошибку в одном узле. Теперь перейдем к оценке порядка роста требуемой памяти и числа шагов при увеличении суммы […]

Долго не публиковал решений упражнений. Перерыв был вызван поездкой в Крым на праздники в небольшой пеший поход по горам. Прошли Большой каньон, затем поднялись на Ай-Петринскую яйлу и мимо Ат-Баша спустились к Симеизу, где немного постояли у моря. В этот раз маршрут был намеренно выбран легкий и неутомительный. Погода тоже была к нам благосклонна. Получилась […]

Итак, нам требуется доказать, что Fib(n) – это ближайшее целое число к φn/√5, где φ=(1+√5)/2. Для этого покажем две вещи: Fib(n) = (φn-ψn)/√5, где ψ=(1-√5)/2; (φn-ψn)/√5 – ближайшее целое число к φn/√5. Приступим к первой части доказательства. В первую очередь отметим, что φ² = ((1+√5)/2)² = (1+2√5+5)/4 = (3+√5)/2 = 1+(1+√5)/2 = 1+φ, ψ² = […]

Будем адресовать элементы треугольника Паскаля двумя числами: номером строки (строки нумеруются сверху вниз) и порядковым номером элемента в этой строке (число элементов растет с движением от более высоких строк к более низким и равно номеру строки). Нумеровать строки и элементы будем начиная с единицы. Запишем функцию, вычисляющую заданный элемент в заданной строке треугольника Паскаля: (define […]

Сначала запишем процедуру, вычисляющую f с помощью рекурсивного процесса. Это делается весьма прямолинейно: (define (f n) (if (< n 3) n (+ (f (- n 1)) (f (- n 2)) (f (- n 3))))) Теперь запишем решение с помощью итеративного процесса. Для этого будем использовать следующую трансформацию : a <- a + b + c […]