Главная Промышленная автоматика.

С указателями) и позволяют сосредоточиться на общей структуре самого алгоритма. Кроме того, мы увидели, как мощная техника рекурсии и динамического программирования часто приводит к элегантным и естественным алгоритмам. Мы познакомились также с некоторыми общими приемами, такими, как "разделяй и властвуй" и балансировка.

Эти методы, разумеется, не являются единственно доступными, но они принадлежат к числу важнейших. Далее в этой книге мы изложим и другие примеры. Они будут относиться к различным задачам - от выбора подходящего представления до нахождения разумного порядка выполнения операций. Возможно, важнейшим принципом хорошего разработчика алгоритмов должно быть чувство неудовлетворенности. Разработчику следует изучать задачу с разных точек зрения, пока он не убедится, что получил алгоритм, наиболее подходящий для его целей.

УПРАЖНЕНИЯ

2.1. Выберите реализацию для дважды связанного списка. Напишите алгоритм на Упрощенном Алголе для вставки и удаления элемента. Убедитесь, что ваши программы работают, когда надо удалить первый и (или) последний элементы и когда список пуст.

2.2. Напишите алгоритм для обращения порядка элементов в списке. Докажите, что он работает правильно.

2.3. Напишите алгоритмы, реализующие операции ЗАТОЛКНУТЬ, ВЫТОЛКНУТЬ, ВПИСАТЬ и ВЫПИСАТЬ, упомянутые в разд. 2.1. Не забывайте проверять, достиг ли указатель конца массива, зарезервированного для стека или очереди.

2.4. Напишите условия для проверки пустоты очереди. Допустим, что массив ИМЯ из разд. 2.1 имеет размер k. Сколько элементов можно хранить в соответствующей очереди? Сделайте рисунки, иллюстрирующие эту очередь и типичные положения указателей ПЕРЕДНИЙ и ЗАДНИЙ в случае, когда очередь (а) пуста, (б) содержит один элемент и (в) полна.

2.5. Напишите алгоритм для удаления первого ребра (у, w) из списка смежностей для v в неориентированном графе. Считайте, что списки смежностей дважды связаны и что СВЯЗЬ помещает v в список смежнбстей узла w, как описано в разд. 2.3

2.6. Напишите алгоритм для построения списков смежностей для неориентированного графа. Каждое ребро (у, w) надо представить дважды: в списках смежностей для у и для w. Оба экземпляра каждого ребра должны связываться между собой так, что если один из них вычеркивается, другой также можно легко вычеркнуть.



*2.7. Топологическая сортировка. Пусть G={V, Е) - ориентированный ациклический граф. Напишите алгоритм, который бы так приписывал целые числа узлам в G, что если из узла с номером i в узел с номером / идет ориентированное ребро, то i<ij. Указание: Ациклический граф должен иметь узел, в который не входит ни одно ребро. Почему? Одно из решений этой задачи таково: найти узел, в который не входят ребра; приписать ему наименьший номер и удалить его из графа вместе со всеми ребрами, выходящими из него. Повторить этот процесс для графа, полученного в результате такого удаления, приписывая следующий наименьший номер, и т. д. Для того чтобы сделать этот алгоритм эффективным, т. е. чтобы его сложность была 0(£+V), нужно, чтобы в поисках узла, в который не входит ни одно ребро, не приходилось просматривать каждый новый граф.

*2.8. Пусть G={V, Е) - ориентированный ациклический граф с двумя выделенными узлами - начальным и целевым. Напишите алгоритм для нахождения такого множества путей из начального узла в целевой, чтобы

1) ни один узел, кроме начального и целевого, не лежал на двух путях,

2) к нему нельзя было добавить ни одного нового пути, не нарушив условия 1.

Заметим, что этим условиям удовлетворяет много множеств. Не обязательно находить множество с наибольшим числом путей, достаточно какого-нибудь множества, удовлетворяющего приведенным выше условиям. Ваш алгоритм должен иметь временную слож-ность 0(£ii+V).

*2.9. Задача об устойчивом бракосочетании. Пусть В - множество из п юношей, а G - множество из п девушек. Каждый юноша оценивает девушек числами от 1 до п, и каждая девушка оценивает юношей числами от 1 до п. Паросочепшнием называется взаимно однозначное соответствие между юношами и девушками. Паросочета-ние устойчиво, если для любых двух юношей ЬиЬч соответствующих им в этом паросочетании девушек gi и g выполняются следующие два условия:

1) либо bi оценивает gi выше, чем g, либо gi оценивает Ь выше, чем bi,

2) либо 2 оценивает g выше, чем gu либо gt оценивает bi выше, чем &2-

Докажите, что устойчивое паросочетание всегда существует, и напишите алгоритм для нахождения одного из таких паросочетании.

2.10. Рассмотрим двоичное дерево, узлам которого приписаны имена. Напишите алгоритм, печатающий эти имена в (а) прямом порядке, (б) обратном и (в) внутреннем.




ЛЕВЫЯСШ ПРАВЫЙСЫН 1 2 3 4 5 6

Рис. 2.17. Двоичное дерево.

*2.11. Напишите алгоритм для вычисления значений арифметических выражений, содержащих операции + и X и представленных в (а) префиксной польской записи, (б) инфиксной записи и (в) постфиксной польской записи.

*2.12. Разработайте технику, которая позволяла бы полагать равными нулю те элементы матрицы, которые выбираются первый раз: таким способом устраняется работа по исходной записи матрицы смежностей, занимающая время 0(1111"). Указание: Устанавливайте в каждом элементе в момент первого присваивания ему значения указатель на обратный указатель во вспомогательном стеке. Всякий раз, когда выбирается какой-то элемент, проверяйте, чтобы он имел не случайное значение; для этого надо убедиться, что его указатель указывает в активную часть стека, а соответствующий обратный указатель - на выбираемый элемент.

2.13. Рассмотрите работу алгоритмов 2.1 и 2.2 на двоичном дереве рис. 2.17.

*2.14. Докажите, что алгоритм 2.2 корректен.

*2.15. Ханойские башни. Имеются три стержня А, В и С и л дисков разных размеров. Вначале все диски нанизаны на стержень А в порядке убывания размеров, так что наибольший диск находится внизу. Надо так переместить диски со стержня А на стержень В, чтобы никакой больший диск ни разу не оказался над меньшим; за один шаг можно перемещать только один диск. Стержень С можно использовать для временного хранения дисков. Напишите рекурсивный алгоритм решения этой задачи. Каково время работы вашего алгоритма в терминах числа перемещений дисков?

**2.16. Решите упр. 2.15 с помощью алгоритма без рекурсии. Какой из алгоритмов легче понять и корректность какого из них легче доказать?

*2.17. Докажите, что для решения упр. 2.15 необходимо и достаточно 2"-1 перемещений.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [25] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0038