Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 37
Текст из файла (страница 37)
5. Постройте самый неблагоприятный вариант последовательности для осуществления каждой из перечисленных ниже сортировок: а) сортировка выбором; б) пузырьковая сортировка; в) быстрая сортировка; г) сортировка слиянием; д) сортировка вставками, 6. Покажите, что для слияния двух уже рассортированных списков длины п требуется не более п — 1 операций сравнения. 7. Напишите компьютерную реализацию алгоритма сортировки выбором.
8. Напишите компьютерную реализацию алгоритма пузырьковой сортировки. 9. Напишите компьютерную реализацию алгоритма быстрой сортировки. 10. Напишите компьютерную реализацию алгоритма сортировки слиянием. 11. Напишите компьютерную реализацию алгоритма сортировки вставками. 12. Покажите, что Я„= Аи — Р удовлетворяет рекурсивному соотношению Я„=29;+Р.
13. Покажите, что Я„= Рн(1об н+ А) удовлетворяет рекурсивному соотношению Я„= 20 + Рги 14. Покажите, что Я„= Апгоа + (з' ) и для С > 2 удовлетворяет рекурсивному соотношению Я„= СЯ- + Рп. 214 ГЛАВА б. Алгоритмы и рекурсия 15. Восстановив пропущенные выкладки, докажите, что Я„= Апыг' + — п является решением Я„= СЯ- + Рп для С > 2, если А выбрано так, что Яг = А+ з . Мы предполагаем, что п = 2 Яз- С /9з-- ~ — — -~+Р= 2т =2~2 г) = ®"'--: "(-') '" = + + + 2 91+ 1+2+ 2 + + — Р- + 1 (г) + 1 гс) + (2) р + 1 гс) С!оаг и п п!Огг с Яг Р(Спыа~ с — 1) 16.
Получите решение вида Я„= для рекурсивного соотношения Я„= СЯ +Р, когда С ф 1. 5.5. ПРЕФИКСНАЯ И СУФФИКСНАЯ ЗАПИСИ В арифметике, как и в логике, существуют определенные правила, касающиеся приоритета выполнения операций над целыми числами, что дает возможность, не приводя к путанице, сокращать число используемых в выражении скобок, Некоторые свойства целых чисел также позволяют уменьшить потребность в скобках. Например, известно, что благодаря закону ассоциативности сложения выражение 3+ 5 + 7 не требует скобок, т.к.
(3 + 5) + 7 = 3+ (5+ 7). Понятно также, что операции возведения в степень должны быть выполнены первыми, за ними следуют умножение и деление и, наконец, сложение и вычитание. Но даже при таком соглашении необходимо использовать скобки. Например, нельзя выразить 1а+Ь)з(4+5Ь), не используя скобок. Исключить скобки можно, применив префиксную или суффиксную форму записи. Чтобы подчеркнуть их отличие от обычной РЯЗДЕП 5.5 Лрефьксная и суффиксная запаса 215 для арифметики формы записи, в которой знак бинарной операции записывается между операндами, назовем обычную форму записи инфиксной. Например, выражения 3+ 4 и 6 —: 3 записаны в инфиксной форме. ОПРЕДЕЛЕНИЕ 5.30.
Выражение находится в лрефиксной (польской) записи, если в нем знак операции непосредственно предшествует операндам, на которые она действует. Выражение находится в суффиксной (постфиксной, или обратной польской записи), если в нем знак операции следует непосредственно за операндами, на которые она действует. Выражение находится в инфиксной записи, если в нем знак операции находится между операндами, на которые она действует. Например, инфиксное выражение а + Ь в префиксной записи имело бы вид +а6, а в постфиксной записи, соответственно, вид аЬ+. Инфиксное выражение ах (6+с) имело бы в префиксной записи вид ха+Ьс, а в постфиксной, соответственно, вид аЬс+ х. Обратите внимание, что постфиксную запись следует "читать" слева направо, а "читать" префиксную запись необходимо справа налево.
Операцию возведения в степень для удобства будем обозначать символом . Таким образом, аз будет записываться как а 5. Выражение (а+Ь) х (с+а) "3 в префиксной записи имеет вид х+аЬ +са3, а в постфиксной записи, соответственно, вид аЬ+са+3 х. В данном разделе рассмотрены алгоритмы перехода от инфиксной записи к постфиксной и от постфиксной — к инфиксной. Подобные алгоритмы для перехода от инфиксной записи к префиксной и наоборот могут быть построены аналогичным образом.
ОПРЕДЕЛЕНИЕ 5.31. Арифметическое выражение находится в полной скобочной записи, если каждому оператору в нем соответствует пара скобок, в которые заключены оператор и те операнды, на которые он действует. Упрощенно можно сказать, что арифметическое выражение — полноскобочное, если скобки в нем присутствуют всюду, где зто возможно по смыслу. Например, (ах (Ь+с)) и ((а+Ь) х ((с+а) "з)) являются полноскобочными выражениями, а выражения а+ (Ь х с) и (а —: Ь) с полноскобочными не являются. Переход от инфиксного выражения к постфиксному может быть осуществлен посредством следующей процедуры; 1. Добавлять скобки в выражение, пока оно не станет полноскобочным. 2. Начиная с самых внутренних скобок, удалить пару скобок и поместить находящийся внутри скобок оператор на место соответствовавшей ему правой скобки.
При наличии более одной самой внутренней пары скобок начинать нужно с левой пары. 3. Перейти к следующей паре скобок, удалить ее и поместить оператор, находившийся внутри скобок, на место соответствовавшей ему правой скобки. 4. Продолжать шаг (3), пока все скобки не будут удалены. 216 ГЛАВА 5. Алгоритмы и рекурсия ПРИМЕР 5.32.
Пусть дано инфиксное выражение (а+Ь) х (с+0) х. Добавляем скобки, пока выражение не станет полноскобочным. Получаем выражение ((а+ Ь) х ((с+4) х)). Выполнив шаг (2), получим (аЬ+ х (сЫ+ х)). Выполнив шаг (3), получим (а6+ х сН+ х"). Повторяя шаг (3), приходим к записи а6+сд+ х х. П ПРИМЕР 6.33. Пусть дано инфиксное выражение а х Ь+с х Н. Добавляем скобки, пока не получим полноскобочное выражение, т.е, выражение ((а х Ь) + (с х Н)). Выполнив шаг (2), получим (аЬ х + сйх). Повторяя шаг (3), получаем а6 х Ы х +. П Неформально стек определяется как область памяти, из которой данные извлекаются в порядке, обратном порядку их ввода. Такой способ организации памяти часто называют 1)ЕО.' Добавление в стек и удаление из него элемента обычно называют операциями вталкивания и выталкивания, соответственно.
Постфиксное выражение может быть заменено инфиксным посредством следующей процедуры: 1. Начинать считывание выражения слева направо. 2. Если считанный символ не является символом операции, то поместить его в стек и продолжать чтение.
3. Если считанный символ является символом операции, то; а) вытолкнуть из стека два верхних элемента; б) поместить символ операции между вторым и первым элементом из стека и поставить скобки; в) поместить выражение, полученное на шаге (б), обратно в стек. 4. Продолжать чтение слева направо и выполнять шаги (2) н (3) до завершения. ПРИМЕР 5.34. Пусть дано выражение аЬсх+. Вначале считываем а и, поскольку это не символ операции, помешаем этот элемент в стек, как показано на рис. 5.4. Затем считываем Ь и, т.к. это не символ операции, помешаем его в стек, как показано на рис.
5.5. вЬсх+ 9 Рис. 5.5 Рис. 5.4 Далее считываем с и, т.к. это не символ операции, помешаем его в стек, как показано на рис. 5.6. Затем считываем х и, поскольку это символ операции, выталкиваем из стека (удаляем) с (верхний элемент) и Ь (следующий элемент), помешаем х между Ь и с, как показано на рис. 5.7. гОт англ. 1ввьнпейгвьощ — "последним вошел, первым вышел". — Прим. перев.
РАЗДЕЛ 5.5. Прафиксная и суффиксная записи 217 1" Рис. б.б Рис. 5.7 Помещаем (Ь х с) в стек, как показано на рис. 5.8. Далее считываем + н, поскольку это символ операции, выталкиваем из стека (удаляем) (Ь х с) и а (следующий элемент). Помещаем + между а и (Ь х с), как показано на рис. 5.9. ~ — ~~бх ф н (6 х с) а Рис. 5.8 Рис. с.9 Помещаем (а+ (Ь х с)) в стек, как показано на рис. 5.10.
Получаем искомое выражение. Очевидно, лишние скобки можно удалить. ПРИМЕР 5.35. Пусть дано выражение аЬ+ ссай+3" х. Сначала считываем а и, т.к. это не символ операции, помещаем его в стек. Следующим считываем Ь и, т.к. это не символ операции, помещаем его в стек. Далее считываем + и, поскольку это символ операции, выталкиваем из стека (удаляем) Ь (верхний элемент) и а (следующий элемент) и помешаем + между а и Ь. Переносим (а + Ь) в стек.
Далее считываем с. Поскольку с не является символом операции, то помешаем его в стек. Далее считываем б и, поскольку это не символ операции, переносим его в стек. Затем считываем + и, поскольку это символ операции, выталкиваем из стека (удаляем) б (верхний элемент) и с (следующий элемент), помешаем + между с и б. Переносим (с+ б) в стек. Далее считываем 3 и, поскольку это не символ операции, помещаем 3 в стек.
Затем считываем символ " и, поскольку это символ операции, выталкиваем из стека 3 (верхний элемент) и (с+И) (следующий элемент), после чего помешаем символ " между (с+ 0) и 3. Переносим ((с+ И) "3) в стек. Считываем х и, т.к. это символ операции, выталкиваем ((с+4) "3) и (а+6) из стека. Помешаем х между (а+ Ь) и ((с+ Н) 3), образуя (а + Ь) х ((с+ Н) 3). Переносим ((а+Ь) х ((с+0) 3)) в стек. Это и есть искомый результат. Очевидно, лишние скобки можно удалить.
П 21В ГПАВА о. Алгоритмы и рекурсия ° УПРАЖНЕНИЯ Замените следующие инфиксные выражения постфиксными: а) а 2+Ь2; б) а 3+3 а 2+7; в) (а" 2+ Ь)(с+ сГ2); г) (а 2 + Ь 3) 4; д) а 2(Ь + с). Замените следующие инфиксные выражения постфиксными; а) (с+ с() — (а+ Ь)" 2; б) ((а+ Ь) — с) 3; в) (а+ 6) "2 — (с+ с~) 2; г) (а — Ь)(а+ Ь); д) а — Ь (с+а). Замените следующие постфиксные выражения инфиксными: а) аЬ+ сг~ — +; б) а62" +сг)2 + х; в) ЗаЬ х х4сН2 х х+; г) аЬ+ "2сН" + +; д) а2 Ь+сд2 + х. Замените следующие постфиксные выражения инфиксными: а) аЬс++3; б) аЬ + 2" с+ сН2 +; в) ЗаЬ х х4сг(2 х х+; г) а6+ 2сй + —:; д) а2 "Ь+ с+ сН2" + +.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
