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²]) =
= (bq’+aq’+ap’, bp’+aq’) = Tp’q’(a, b),

где […]

Процедура, порождающая итеративный процесс для умножения, приведена ниже:
(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 и следовательно вычисляется произведение ab. Условием выхода является […]

В этом упражнении все просто. Ниже приведен код процедуры.
(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)
  (if (= n 0)
      a
      (if […]

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

В этом упражнении нет никаких хитростей. Нужно просто быть внимательным и уметь рисовать бинарные деревья (это не так просто как кажется). Правильное дерево приведено на рисунке ниже.

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

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

В этот раз маршрут был намеренно выбран легкий и неутомительный. Погода тоже была к нам благосклонна. Получилась отличная […]

Итак, нам требуется доказать, что 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+φ,
ψ² = ((1-√5)/2)² = (1-2√5+5)/4 = (3-√5)/2 = 1+(1-√5)/2 […]

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

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