1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 17
Текст из файла (страница 17)
Не забывайте проверять, достиг ли указатель конца массива, зарезервированного для стека или очереди. 2.4. Напишите условия для проверки пустоты очереди. Допустим, что массив ИМЯ из разд. 2.1 имеет размер й. Сколько элементов можно хранить в соответствующей очереди? Сделайте рисунки, иллюстрирующие эту очередь и типичные положения указателей ПЕРЕДНИЙ и ЗАДНИЙ в случае, когда очередь (а) пуста, (б) содержит один элемент и (в) полна. 2.5. Напишите алгоритм для удаления первого ребра (о, ш) из списка смежностей для о в неориентированном графе. Считайте, что списки смежностей дважды связаны и что СВЯЗЬ помещает о в список смежнпстей узла ш, как описано в равд. 2.3 2.6.
Напишите алгоритм для построения списков смежностей для неориентированного графа. Каждое ребро (О, и) надо представить дважды: в списках смежностей для п и для ш. Оба экземпляра каждого ребра должны связываться между собой так, что если один из них вычеркивается, другой также можно легко вычеркнуть. чичхж и ч ми м *2.7. Толологичвская сортировка. Пусть 6=(1~, Е) — ориентиро- ванный ациклический граф. Йапишите алгоритм, который бы так приписывал целые числа узлам в 6, что если из узла с номером 1 в узел с номером / идет ориентированное ребро, то 1(/. Указание: Ациклический граф должен иметь узел, в который не входит ни од- но ребро. Почему? Одно из решений этой задачи таково: найти узел, в который не входят ребра; приписать ему наименьший номер и уда- лить его из графа вместе со всеми ребрами, выходящими из него.
Повторить этот процесс для графа, полученного в результате такого удаления, приписывая следующий наименьший номер, и т. д. Для того чтобы сделать этот алгоритм эффективным, т. е. чтобы его сложность была ОЩЕ~!+~~Уй), нужно, чтобы в поисках узла, в ко- торый не входит ни одно ребро, не приходилось просматривать каж- дый новый граф. *2.8. Пусть 6=(1г, Е) — ориентированный ациклический граф с двумя выделенными узлами — начальным и целевым. Напишите алгоритм для нахождения такого множества путей из начального узла в целевой, чтобы 1) ни один узел, кроме начального и целевого, не лежал на двух путях, 2) и нему нельзя было добавить ни одного нового пути, не нару- шив условия 1.
Заметим, что этим условиям удовлетворяет много множеств, Не обязательно находить множество с наибольшим числом путей, до- статочно какого-нибудь множества, удовлетворяющего приведен- ным выше условиям. Ваш алгоритм должен иметь временную слож- ность 0(йЕй+ягп). *2.9. Задача аб успюйчивом бракосочетании. Пусть  — множе- ство из л юношей, а 6 — множество из л девушек. Каждый юноша оценивает девушек числами от 1 до л, и каждая девушка оценивает юношей числами от 1 до л. Пароссчетанивм называется взаимно од- нозначное соответствие между юношами и девушками.
Паросочета- ние устойчиво, если для любых двух юношей Ь, и Ь, и соответствую. щих им в этом паросочетании девушек д, и а, выполняются следую- щие два условия; 1) либо Ь, оценивает д, выше, чем дм либо д, оценивает Ь, выше, чем Ьб 2) либо Ь, оценивает я, выше, чем дь либо д~ оценивает Ь, выше, чем Ь,. Докажите, что устойчивое паросочетание всегда существует, и напишите алгоритм для нахождения одного из таких паросочета- ний.
2.10. Рассмотрим двоичное дерево, узлам которого приписаны имена. Напишите алгоритм, печатающий эти имена в (а) прямом порядке, (б) обратном и (в) внутреннем. ГЛ. 2. РАЗРАВОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ Лнаыйемк Праамйсми 1 Рис. 2.17. Двоичное дерево. "2.11. Напишите алгоритм для вычисления значений арифметических выражений, содержащих операции + и х и представленных в (а) префиксной польской записи, (б) иифнксной записи и (в) постфиксной польской записи. "2.12.
Разработайте технику, которая позволяла бы полагать равными нулю те элементы матрицы, которые выбираются первый раз: таким способом устраняется работа по исходной записи матрицы смежностей, занимающая время 0(йрйе), указание: устанавливайте в каждом элементе в момент первого присваивания ему значения указатель на обратный указатель во вспомогательном стеке.
Всякий раз, когда выбирается какой-то элемент, проверяйте, чтобы он имел не случайное значение; для этого надо убедиться, что его указатель указывает в активную часть стека, а соответствующий обратный указатель — на выбираемый элемент. 2.13, Рассмотрите работу алгоритмов 2.1 и 2.2 на двоичном дереве рис. 2.17.
*2.14. Докажите, что алгоритм 2.2 корректен. "2.15. Ханойсяи башни. Имеются три стержня А, В и С и и дисков разных размеров. Вначале все диски нанизаны на стержень А в порядке убывания размеров, так что наибольший диск находится внизу. Надо так переместить диски со стержня А на стержень В, чтобы никакой больший диск ни разу не оказался над меньшим; за один шаг можно перемещать только один диск. Стержень С можно использовать для временного хранения дисков, Напишите рекурсивный алгоритм решения этой задачи.
Каково время работы вашего алгоритма в терминах числа перемещений дисков? *"2.16. Решите упр. 2.15 с помощью алгоритма без рекурсии. Какой из алгоритмов легче понять и корректность какого из иих легче доказать? *2.17. Докажите, что для решения упр. 2.15 необходимо и достаточно 2" — 1 перемещений.
УПРАЖНЕНИЯ 2.18. Напишите алгоритм порождения всех перестановок целых чисел от 1 до л. Указание: Множество перестановок целых чисел от 1 до л можно получить из множества перестановок целых чисел от! до л — 1, вставляя л во все возможные позиции в каждой перестановке. 2.19. Напишите алгоритм нахождения высоты двоичного дерева, представленного на рис. 2.7, б. 2.20. Напишите алгоритм подсчета числа потомков каждого узла дерева. **2.21. Рассмотрим двухпозиционный переключатель с двумя входами и двумя выходами„ показанный на рис.
2.18. В одной позиции входы 1 и 2 соединяются соответственно с выходами 1 и 2, в другой — с выходами 2 и 1. Используя зти переключатели, разработайте сеть с л входами и л выходами, на которой можно получить любую из л! возможных перестановок входов. В вашей сети должно быть не более 0(л 1оя л) переключателей. Указание: Примените прием "разделяй и властвуй". 2.22. Напишите РАСП-программу, которая выполняла бы работу следующей программы> вычисляющей (" ) 1 ргосебпге СОЧЕТ (л, тл): И т=О или л и 1Ьеп ге1пгп 1 е!зе ге1пгп (СОЧЕТ(л — 1, лт)+СОЧЕТ(л — 1, т — 1)) В стеке можно хранить текущие значения л и тл, а также адреса возврата и значения, когда происходят вызовы.
"2.23. В ряде ситуаций задачу размера л выгодно разбивать на )/л подзадач размера )Ул. В результате получается рекуррентное уравнение вида т ( —,", ) = т( )+ь ', где г — целое число, г-е!. Покажите, что решение этого рекуррентного уравнения есть 0(л(!од л)в!од 1ои л).
во~~ ~н ~! о ввв ' вне --- Соединения в 1-й позиции ....... Соединения оо 2-й оовиции Рпе. 2.18. двукпоекпкопкый переключатель. ГЛ, В РАЗРАБОТКА ВФФВКТИВИЫХ АЛГОРИТМОВ 2.24, Вычислите значения сумм: л (а) 1=1 (г) ~~',2А Ч*, (в) ~ (а~, с-~ (е) ~, 1(,". ). (б) ~.,а', () Е(/) *2.25. Решите следующие рекуррентные уравнения, считая, что Т(1)=1: (а) Т(и)=аТ(п — 1)+Ьп, (б) Т(п)=Т(п/2)+Ьп 1опп, (в) Т(п)=аТ(п — !)+Ьп', (г) Т(п)=ОТ(л/2)+Ьп'.
(б) Покажите, что решением этого рекуррентного уравнения служит функция Т(п)=л Г1оп и [ — 2Г"з "т+1. "2.26. Модифицируйте алгоритм 2.3 для нахождения наибольшего и наименьшего элементов множества, разрешив рекурсии идти до уровня [[Я=1. Какова асимптогическая скорость роста числа сравнений? *"2.27, Покажите, что для одновременного нахождения наибольшего и наименьшего элементов и-элементного множества необходимо и достаточно [ л/лп — 2 ) сравнений. "2.28. Модифицируйте алгоритм для умножения целых чисел с помощью разбиения каждого целого числа на (а) три и (б) четыре части. Какова сложность каждого из ваших алгоритмов? "'2.29. Пусть А — массив размера и, состоящий из положительных и отрицательных целых чисел, причем АШ» А[21»„...«А[п1. Напишите алгоритм нахождения числа 1, для которого А[/[=1 (если такое г' существует).
Каков порядок времени работы вашего алгоритма? Докажите, что Ос(!Ой п) — наилучший возможный порядок. *"2.30. Для и, не янляющегося степенью числа 2, также можно получить из алгоритма 2.4 корректный алгоритм сортировки слиянием, если заменить оператор т»-(1+/ — 1)/2 на рис, 2.14 оператором т [ (/+/)/2 [. Пусть Т(п) — число сравнений, требуемых для сортировки этим методом и элементов. (а) Покажите, что Т(1)=0, Т(л)= Т([ и/2 ~)+Т([ и/2 ))+п — 1. УПРАЖНЕНИЯ *2.31. Покажите, что решением рекуррентного уравнения Х (1) = 1.
ь-1 Х (и) = ~',, Х (1) Х (и — 1) при и )1 служит Х(п+1) =, ( ") . Х(п) — это число способов правильной расстановки скобок в цепочке из и символов. Числа Х (и) называются числами Каталаиа. Покажите, что Х(п))2" -". 2.32. Модифицируйте алгоритм 2,3 так, чтобы он выдавал порядок, в котором следует умножать матрицы, чтобы минимизировать число умножений их элементов.
2.33. Напишите эффективный алгоритм для определения порядка, в котором следует вычислять произведение матриц М1хМ,х х... хМ„, чтобы минимизировать число умножений элементов в случае, когда каждая матрица М; имеет один из размеров 1~с!, 1мй, йос1 или с(:сс( при некотором фиксированном й. Определение. Бесконтекстной грамматикой С в нормальной форме Хамского называется четверка (Л1, Х, Р, 5), где (1) 1У вЂ” конечное множество нетерминальных символов, (2) 2 — конечное множество терминальных символов, (3) Р— конечное множество пар, называемых продукциями, вида А - ВС или А -ь- а (А, В, С— символы из й1, а а — из Х) и (4) 5 — выделенный символ из Л1.
й(ы будем писать аАу ~ а(12, если а, р, у — цепочки, состоящие из терминальных и нетерминальных символов, и А -э- () принадлежит Р. Языком Б(С), порождаемым грамматикой С, называется множество (п1~5 ~" и1) цепочек терминальных символов, где =>' обозначает рефлексивное и транзитивное замыкание отношения ~. *2.34. Напишите алгоритм сложности 0(п'), который определял бы принадлежность данной цепочки и1=а,аь ..а„языку 1 (С), где С=(Л1, Х, Р, 5) — бесконтекстная грамматика в нормальной форме Хамского. Указание: Пусть тм — — (А~А ЕЛ1 и А =>* а1а1+,...а1). Слово сс принадлежит языку Ь (С) тогда и только тогда, когда 5 Е рт,„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
