Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 27
Текст из файла (страница 27)
Из всего сказанного в этой главе можно сделать следующие выводы: !. Между алгоритмом и структурой данных существует тесная связь; структура данных оказывает большое влияние на вид программы. 2. При помощи усложнения программы можно значительно повысить ее эффективность, даже когда структура данных, с которой она работает, плохо соответствует поставленной задаче.
УПРАЖНЕНИЯ 2.!. Какие нз злгоритмов, представленных программами 2.! — 26, 2.8, 2.!О и 2.!3, являются методами устойчивой сортировка» 2.2. Будет ли программа 2.2 работать правильно, если в условии окончания цикла заменить 1 ~ г на 1 < г? Будет ли она по-прежкему правильной, если операторы г: = ш — 1 и 1: = лг + 1 упростить до г: = лг и 1; = гл? Если нет, найдите множества заачений а,...а„, при которых измененная программа будет работать неправильно. 2.3.
Запрограммируйте три метода простой сортировки н чзмерьте время их работы. Найдите веса, на которые нужно умножить козффвциенты С и М, чтобы получить оценки реального времени. 2мь Протестируйте программу пирамидальной сортпровки 2.8 с различными произвольными входными последовательностями и определите, сколько раз в среднем выполняется оператор Ио!о 13 Поскольку зто чксло сравнительно мало, интересен следуюшнй вопрос: имеется ли способ извлечь проверку х.йеу ) а [1[.йеу из цикла с предусловием? 2.5. Рассмотрнге следующую «очевидную» версию программы разделения 2.9: т:= 1,'у:= л; х:= а[[и+1) 6!т 2).кеу; терев! мйпе а[1[.кеу ц х бо г: = 1+1; ттййех < аЦ.1«ег боу:=у — !' гт:= аИ; а[«[:= аИ; аИ:= и вп!И1>у Найдите множества значений аю., а„, лля которых зта версия работает неправильно. 2.6. Напишите программу, которая комбинирует алгоритмы быстрой сортировки н сортировки методом пузырька следующим образом: используется быстрая сортировка для получения (неотсортированпых) 2.
Сортировка 148 подмассзвов длиной т(1 < т < л); затем для завершения задачи ис. пользуется сортировка методом пузырька. Отметим, что последняя теперь может проходить по всему массиву, мнннмизируи тем самым затраты на управление. Найдите значение т, минимизирующее общее время сортировки. Примечание. Ясно, что оптимальное значение т будет достаточно мало. Тогда, может быть, стоит позволить, чтобы сортировка методом пузырька проходила па всему массиву ровно т — 1 раз, вместо того чтобы определять последний проход, на котором не производилось никаких обменов. 2.7. Проведите тот же эксперимент, чта и в упр. 6 с сортировкой простым выбором вместо сортировки методом пузырька.
Конечно, сортировка простым выбором не может проходить по всему массиву, поэтому ожидаемый объем работы с индексами несколько больше. 2.8. Напишите рекурсивный алгоритм быстрой сортировки согласно указанию, что сортировку меньшего подмасснва следует выполнять раньше сортировки более длинного подмассива. Выполните первую задачу при помощи итеративного оператора, а последнюю — при помощи рекурсивного вызова. (Следовательно, ваша процедура сортировки будет содержать один рекурсивный вызов в отличие от программы 2.10, содержащей 2 вызова, и программы 2.11, не содержащей ни одного.) 2.9. Найдите перестановку ключей 1, 2, ..., л, для которой быстрая сортировка ведет себя наихудшим (наилучшим) образом (л = 5, 6, 8). 2.10.
Напишите программу естественного слияния, которан, подобно программе простого слияния 2.13, работает на массиве двойной длины с двух концов в середину. Сравните ее харантеристики с характеристи. нами программы 2.13. 2.11. Заметьте, что при двухпутевом естественном слиянии мы не просто слепо выбираем наименьшее значение иэ имеющихся ключей, Вместо этого, когда встречаетси конец серии, остаток другой серии просто переписывается в выходную последовательность. Например, слияние 2, 4, 5, 1, 2, 3, 6, 8, 9, 7, дает последовательность 2, 3, 4, 5, 6, 8, 9, 1, 2..., вместо последовательности 2, 3, 4, 5, 1, 2, 6, 8, 9, . которая кажется лучше упорядоченной. Почему принята такая стра- тегия? 2.12. Зачем нужна переменная 1а в программе 2.15? При наких условиях выполняется оператор Ьвй)пгеюг(1е()((и(тк) 1)! ° ° ° а при каких -- оператор Ьей)п 1х:= га(тх); ? ..? 2.13. Почему в программе многофазиай сортировки 2.16 требуется переменнаи 1аай а в программе 2.15 она не нужна? 2.И.
Существует метод сортировки, похожий на иногофззную сортвроаку: так называемое каскадное слияние (2 1, 2.9(. Он использует другой Литература 149' принцип слияния. Если, например, дэны шесть лент Т1,..., Тб, каскадное слияние, нач.п.ая также с «идеального распределенняз серий иа Т!, ..., Т5, выполняет пятнпутеиое слияние с Т1, ..., Т5 иа Тб, пока Т5 не станет пустой, затем (не затрагивая Тб) чегырехпутеаое слияние иа Т5, затем трехйутевое слияние на Т4, двухпутевое слияние на ТЗ и, наконец, перепись с Т1 на Т2.
Следующий проход работает такам же образом, начиная с пятнпутевого слияния на Т) н т. д, Хотя зта схема кажется хуже многофааиога слияния, поскольку временамн оставляет некоторые ленты без работы, а также выполняет операции простого копирования, оиа, к удивлению, оказывается лучше многофазной для очень больших файлов и для шести и более лент. Напишите хорошо структурированную программу каскадного слияния.
ЛИТЕРАТУРА 2.1. ВЕТХ В. К., СЛйТЕй,— АСМ )На!гола! Соп)«14, 1959, Рарег 14 2.2. РЬОТО й. Ъ'. Тгеезоп (А!бог!!пшз !13, 243), Сотт. АСМ, 5, Хо. 8, 1962, 434, Сотт. АСМ, 7. Хо. 12, !964, 701. 2.3, 61ЬЗТАП й. Ь. Ро!урпазе Мегйе Зогйпй — Ап Лдтапсед Тесйпщце.— Ргос. АГ!РБ Еазсег 7!. Сотр. Сопй 18, 1960, 143 — 148. 2,4. НОАйЕ С. А й. Ргоо( о1 Ргойгаш. Р)ХО.— Сотт. АСМ, 13, Хо, 1, 1970, 39 — 45. 2.5. НОАйЕ С. А.
й. Ргоо1 о1 йесцгзйе Ргобгаш: Г3ц!с)гзогг.— Сотр, 7., 14, Хо. 4, !971, 39! — 395. 2,6. НОАйЕ С, А. й. (3ц!с)гзаг!.— Сотр. Л, 5, Хо. 1, 1962, 1Π— 15 2.7. КХ1!ТН О, Е. Т)ге аг1 а1 Сошьет Ргобгаппп!пб, 3,— йеаб)пй, Маза.: Лбб)зоп-%ез!еу, 1973. (Имеется перевод: Кнут Д, Иснусство програм. мирования для ЭВМ, т. 3.-- Ми Мир, 1978.) 2.8. КХ!!ТН О. Е. Т)ге аг! о1 Согпрц1ег Ргобгашш1пй, 3, 86 — 95.
!Имеется перевод; Кнут Д. Искусство программирования для ЭВМ, т. 3. — Мл Мир, !978, с. 108 — 1!9.) 2.9. КХ6ТН О. Е. Т)ге аг1 о1 Сошрц1ег Ргойгашш!пй, 3, 289. (Имеется перевод: Кнут д. Искусство программирования для ЭВМ, т, 3. — Ми Мир, !978, с, 342.) 2.10. 1.0й1Х Н. Л Оц!бед В154юйгарйу 1о Зогйпб. — !ВМ Яуа!. 7., 10, Хо. 3, 1971, 244 — 254. .2.11. ЗНЕЬЬ П Ь. А Н!8)гзреед Богйпб Ргоседпге, — Соте. АСМ, 2, Хо. 7, 1959, 30 — 32. 2.12. 5)ХОЬЕТОХ й. С. Ап Е(!!с)еп! А18опйш 1ог Зогйпн тг!й М!пипа! «Могайе (Л18опйш 347). — Соте.
АСМ, 12, Хо. 3, 1969, !85. 2.!3. агап ЕМЕГЕХ М. Н, !псгеаз!пй йе ЕИ!с!енсу о1 Ошсйзогг (А)йог!!йш) 402). — Сотт, АСМ, 13, Хо. 9, 1970. 563 — 566, 693. О.М. %!ЬЬ!ЛМ5 Л. %. 1. Неараог( (А)бопйгп 232). — Сотт, АСМ, 7« Хо.
б, 1964, 347 — 348. РЕКУРСИВНЫЕ АЛГОРИТМЫ ЗЛ. ВВЕДЕНИИ Объект называется рекурсивным, если он содержит сам себя илн определен с помощью самого себя. Рекурсия встречается не только в математике, ио и в обыденной жизни. Кто не видел рекламной картинки, которая содержит свое собственное изображение? Рекурсия является особенно мощным средством в математических определениях. Известны примеры рекурсивных определений натуральных чисел, древовидных структур и некоторых функций; 1. Натуральные числа: (а) ! есть натуральное число; (Ь) целое число, следующее за натуральным, есть нату ральное число.
2. Древовидные структуры: (а) О есть дерево (называемое пустым деревом); (Ь) если 1~ н !з — деревья, то есть дерево (нарисованное сверху вниз), 3. Функция факториал и! для неотрицательных целых чисел~ (а) 01=1, (Ь) если л ) О, то л! = л. (л — 1)! Очевидно, что мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с по. мощью конечного высказывания. Точно так же бесконечные вычисления можно описать с помощью конечной рекурсивной программы, даже если эта программа не содержит явных циклов. Однако лучше всего использовать рекурсивные алгоритмы в тех случаях, когда решаемая задача, или вычисляемая функция, нли обрабатываемая структура данных определены с помощью рекурсии. В общем виде рекурсивную про~рамму Р можно изобразить как композицию У базовых 1б1 Ззь Введение операторов 5~ (не содержащих Р) и самой Р: Р— У(5ь Р).
(3.1) Необходимое и достаточное средство для рекурсивного представления программ †э описание процедур, или подпрограмм, так как оно позволяет присваивать какому-либо оператору имя, с помощью которого можно вызывать этот оператор. Если процедура Р содержит явное обращение к самой себе, то она называется прямо рекурсивной; если Р содержит обращение к процедуре Я, которая содержит (прямо ) ф ® о О! О 3116 Рис. 3.1. Рекурсивное изображение. или косвенно) обращение к Р, то Р называется косвенно рекурсивной.
Поэтому использование рекурсии не всегда сразу видно из текста программы. С процедурой принято связывать некоторое множество локальных объектов, т. е. переменных, констант, типов и процедур, которые определены локально в этой процедуре, а вие ее не существуют или не имеют смысла. Каждый раз, когда такая процедура рекурсивно вызывается, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предь1дущем обращении к этой же процедуре, их значения различны.
Следукзщпс правила области действия идентификаторов позволяют исключить какой-либо конфликт при использовании имен: идентификаторы всегда ссылаются на множество переменных, созданное последним. То же правило относится к параметрам процедуры. 3. Рекирсивнме авеоритны или Р— = У[5,, ИВ!ЬепР] (3.3) Основной способ доказать, что выполнение операторов цикла когда-либо заканчивается, — определить функцию !(к) (х — множество переменных программы), такую, что !(х) ='О удовлетворяет условию окончания цикла (с предусловием или с постусловием), и доказать, что при каждом повторении !(х) уменьшается. Точно так же можно доказать, что выполнение рекурсивной процедуры Р когда-либо завершится, показав, что каждое выполнение Р уменьшает )(х).
Наиболее надежный способ обеспечить окончание процедуры — связать с Р параметр (значение), скажем а, и рекурсивно вызывать Р со значением этого параметра и — 1. Тогда замена условия В на и > О гарантирует окончание работы. Это можно изобра.зить следующими схемами программ; Р(п) = Иа > О!пепУ(5о Р(п — 1)] Р(н)— = У]5ь Ип > О(ЬепР(н — !)] (3.4) (З.б) На практике нужно обязательно убедиться, что наибольшая глубина рекурсии не только конечна, но и достаточно мала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
