Category: Решения упражнений

Полгода в эфире

13 February, 2008 (23:05) | Разное, Решения упражнений | 2 comments

Вчера этому ресурсу незаметно (я чуть было не пропустил такое знаменательное событие) стукнуло полгода. Первая заметка датирована 12 августа 2007 года. На текущий момент статистика следующая: Написано 137 заметок (включая эту). К заметкам создано 57 комментариев. Решено 112 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и […]

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

13 February, 2008 (22:26) | Решения упражнений | No comments

Просто возьмем процедуру element-of-set? для множеств, представленных бинарными деревьями, и модернизируем ее для работы с записями с числовым ключом. Также учтем, что lookup не только проверяет присутствие записи с заданным ключом, но и возвращает саму эту запись в случае успешного поиска. Получим следующую процедуру: (define (lookup given-key set-of-records)   (cond ((null? set-of-records) false)         ((= […]

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

13 February, 2008 (22:04) | Решения упражнений | No comments

Процедуры tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам возможность свободно преобразовывать множества, представленные упорядоченными списками и (сбалансированными) бинарными деревьями, из одного представления в другое за линейное (Θ(n)) число операций. Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для […]

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

13 February, 2008 (21:29) | Решения упражнений | No comments

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом. Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом […]

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

13 February, 2008 (20:54) | Решения упражнений | 7 comments

Процедуры tree->list-1 и tree->list-2 создают отсортированный список элементов в дереве (фактически, они производят обход дерева в глубину слева направо и собирают значения entry каждого узла дерева в список). Таким образом они делают одно и то же. Разница между ними в том, что tree->list-1 записана в форме, порождающей рекурсивный процесс, а tree->list-2 порождает итеративный процесс. Поскольку все деревья […]

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

12 February, 2008 (21:41) | Решения упражнений | 1 comment

Идея реализации union-set за линейный проход абсолютно аналогична идее, положенной в основу intersection-set из книги. Мы движемся параллельно по двум спискам и сравниваем их текущие первые элементы. Если они равны, мы решаем задачу для хвостов списков и приписываем любой из двух равных головных элементов в начало. Если же один из элементов меньше другого, то его […]

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

12 February, 2008 (21:16) | Решения упражнений | 3 comments

Для того, чтобы получить уменьшение вдвое числа шагов, необходимого для добавления элемента во множество, представленное в виде неупорядоченного списка, нам недостаточно просто определить, есть ли элемент во множестве с помощью element-of-set?, а затем добавить его подобно тому, как мы делали для множеств, представленных неупорядоченными списками. В этом случае поиск и вставка потребуют в среднем по […]

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

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

Очень показательное упражнение, которое одновременно является достаточно простым. SICP продолжает радовать. Итак, как будут выглядеть операции проверки принадлежности множеству, добавления элемента, пересечения и объединения множеств в случае, если элементы в списке, представляющем множество, могут повторяться? Во-первых, я хочу заметить, что мы можем вообще ничего не менять: старые операции работают корректно и на новом представлении множеств. Но это […]

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

11 February, 2008 (20:43) | Решения упражнений | 2 comments

Для реализации операции объединения множеств мы можем применить рекурсивную стратегию, близкую по задумке к той, которая приводится при описании операции пересечения множеств в тексте книги. А именно, воспользуемся следующими тремя правилами при объединении множеств set1 и set2: Если set1 пусто, то объединение set1 и set2 есть set2. Если элемент x из set1 содержится в set2, то объединение set1 и set2 – это то же, что […]

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

10 February, 2008 (13:01) | Решения упражнений | 6 comments

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