Month: October, 2007

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

18 October, 2007 (21:11) | Решения упражнений | 7 comments

Упражнение по написанию процедуры, вычисляющей произведение полезное, но несложное, так как аналогии с суммированием просматриваются очень легко. Все понимают, что роль операции + из суммирования в умножении выполняет операция *. Роль нуля выполняет единица. Те, кто изучал линейную алгебру, вообще особой разницы между сложением и умножением не видят Итак, процедуру product можно записать так (порождается […]

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

16 October, 2007 (20:36) | Решения упражнений | No comments

Это тот случай, когда любые пояснения будут лишними. (define (sum term a next b)     (define (iter a result)       (if (> a b)           result           (iter (next a) (+ result (term a)))))     (iter a 0)) Если что-то непонятно, комментируйте.

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

16 October, 2007 (20:14) | Решения упражнений | 6 comments

Итак, мы переходим к упражнениям раздела 1.3, в котором речь идет о процедурах высших порядков. Поддержка процедур высших порядков и вообще работа с процедурами как с данными является очень мощным средством построения абстракций. В упражнениях мы как раз этими абстракциями и займемся. Реализация формулы Симпсона для вычисления определенного интеграла выглядит следующим образом: (define (simpson f a […]

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

15 October, 2007 (20:14) | Решения упражнений | 10 comments

Это упражнение немного заковыристо сформулировано, но сложным не является. Вот код модифицированной процедуры expmod, которая сигнализирует о нахождении нетривиального квадратного корня из 1, возвращая 0 (как и рекомендовано в условии). (define (square x)   (* x x)) (define (apply-trivial-check k m r)   (if (and (not (= k 1))            (not (= k (- m […]

SICP Wiki

13 October, 2007 (12:32) | Материалы | No comments

Совершенно случайно наткнулся на новый сайт, посвященный решению упражнений из SICP и обсуждению книги. Сайт называется SICP Wiki и появился в сентябре этого года (совсем свеженький). На данный момент доступны решения большинства упражнений из первой главы и части упражнений из второй. Мне очень понравилось внутреннее устройство сайта, то, что он построен на базе вики и […]

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

12 October, 2007 (20:41) | Решения упражнений | 1 comment

Код процедуры проверки приведен ниже. Процедура называется (test-all) и принимает один параметр – число для проверки на простоту. (define (square x)   (* x x)) (define (expmod base exp m)   (cond ((= exp 0) 1)         ((even? exp)          (remainder (square (expmod base (/ exp 2) m))                     m))         (else          (remainder (* […]

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

12 October, 2007 (20:00) | Решения упражнений | No comments

Отличие реализации Хьюго в том, что на каждом шаге (expmod) для четного показателя степени вызывает себя с вдвое меньшим показателем не один раз, а два. Пусть C(n) – число операций, необходимых для вычисления (expmod n exp m). Покажем, что для реализации Хьюго C(n) растет как линейная функция, а не логарифм. Про алгоритм Хюго можно записать: C(2n) […]

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

11 October, 2007 (23:27) | Решения упражнений | 3 comments

Идея Алисы проста и понятна. Более того, ее вариант процедуры (expmod) выдает те же результаты, что и исходный. Но в нем есть проблема, имя которой – эффективность. Количество операций, производимых при вычислении по обеим процедурам, будет примерно одинаковым (иметь один порядок роста) только в том случае, если элементарные функции, такие как * и remainder, выполняются […]

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

11 October, 2007 (19:42) | Решения упражнений | No comments

Это упражнение также базируется на упражнении 22, так что изучите его до того, как переходить к этому. Для замеров времени в этом упражнении я применю несколько другую технику. Если в упражнении 22 я выбрал большие числа, то в данном случае достаточно будет просто задать в (fast-prime?) достаточно большое число прогонов теста Ферма и работать с числами […]

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

10 October, 2007 (22:17) | Решения упражнений | No comments

Это упражнение является логическим продолжением предыдущего упражнения 22, поэтому ознакомьтесь с его решением прежде, чем продолжать. Итак, измененный код процедуры (find-divisor) будет выглядеть так: (define (next n)   (if (= n 2)       3       (+ n 2))) (define (find-divisor n test-divisor)   (cond ((> (square test-divisor) n) n)         ((divides? test-divisor n) test-divisor)         […]