AOP_Tom1 (1021736), страница 51
Текст из файла (страница 51)
[Так как это значение лежит между (т — 1)/т и 1, перестановка Иосифа имеет немного меньше фиксированных элементов,чем случайные перестановки.] 32. [МЙ5] (а) Докажите, что для любой перестановки я = к~ кг... яг +г вида к = (2 3)" (4 5)"... (2т 2тп+1)" (1 2)" (3 4)"... (2т — 1 2т)" где каждое еь — либо О, либо 1, имеет место ]яь — Ц < 2 для 1 < Ь < 2т+ 1.
(Ь) Для любой заданной перестановки р элементов (1, 2,..., и] постройте перестановку я указанного вида, такую, чтобы произведение ря давало единственный цикл. Таким образом, каждая перестановка "близка" к циклу. 33. [МЭЭ] Пусть гп = 2, а п = 2м+'. Покажите, как построить последовательность перестановок (аю, аг,..., а,; Нд,бгг...,.,бг ) длЯ 0 < 1 < т, имеющих следУющее свойство "ортогональности" (12345), если г = 1; а!Ныа 2Аг ° а Ал = () если г -,г 1. Каждое агг н /)гь должно быть перестановкой чисел (1, 2,3,4,5).
ь 34. ]МЯЛ] (Транспаииррюигис блоки данных.) Одной из самых распространенных перестановок, использующихся на Йрактике, является переход от а)1 к ра, где а и р' — это подстроки массива. Другими слрвами, если хохю ..х 1 = а и х х +~...х + ~ =)3, то нужно заменить массив хох~ ..х +„~ = аб массивом х х +ю ..х +„1хех1...х ))а. Это перестановка на множестве (О, 1,..., т+ п — 1), которая переводит к в (й+ т) шод (т+ и), Покажите, что каждая такая перестановка "с циклическим сдвигом" имеет простую циклическую структуру, и используйте эту структуру для разработки простого алгоритма получения нужной перестановки. 35.
]МЗО] В продолжение предыдущего упражнения положмм хсхю ..хьь + 1 = а~уу, где а, р' и у — строки длины 1, т и и соответственно, и предположим, что нужно заменить аДу на у)уа. Покажите, что соответствующая перестановка имеет подходящую циклическую структуру, которая позволяет получить эффективный алгоритм. (Упр. 34 рассматривалось как частный случай прм т = 0.] Указание.
Рассмотрите замену (а)г)( 03) на ( у)1)(а)1). 36. ]27] Напишите для МХХ подпрограмму, реализующую алгоритм, который приведен в ответе к упр. 35, и проанализируйте время его выполнения. Сравните этот алгормтм с более простым методом, в котором осуществляется переход от абч к (аду) = ч Д а я я я л и к Г)3а, где ел обозначает полное обращенме строки е, т. е, строка чмтается в обратном порядке. 1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ 1.4.1. Подпрограммы КОГДА НЕКОТОРую задачу нужно выполнить в нескольких различных местах про- граммы, то, как правило, нежелательно каждый раз повторять ее код. Чтобы избежать этого, данный код (нэзываемый подпрограммой) можно поместить только в одном месте и добавить несколько дополнительных команд, чтобы после завер- шения работы подпрограммы должным образом возобновить выполнение внешней программы. Передача управления между подпрограммами и основной программой называется сазиью с подпрограммами.
Каждый компьютер имеет свои специфические способы установления эффек- тивной связи с подпрограммами, которые обычно подразумевают применение специ- альных команд. В И1Х для этой цели используется регистр Л. Рассматривая данную тему, будем ориентироваться на машинный язык И1Х, но аналогичные рассуждения применимы и к вопросам связи с подпрограммами для других компьютеров. Подпрограммы используются с целью экономии места в программе, но их при- менение не приводит непосредственно к зкономии времени.
Это происходит неявно вследствие того, что программа занимает меньше места в памяти, например меньше времени тратится на загрузку программы, уменьшается количество проходов в про- грамме либо более эффективно используется высокоскоростная память на машинах с несколькими уровнями памяти. Дополнительным временем, которое тратится на вход в подпрограмму и выход из нее, обычно можно пренебречь. Подпрограммы имеют и другие преимущества.
Благодаря им структура боль- ших и сложных программ становится более наглядной. Они разбивают всю задачу на логические сегменты, что обычно облегчает отладку программы. Многие под- программы имеют дополнительную ценность, поскольку ими могут воспользоваться не только авторы,но и другие пользователи, Большинство компьютерных средств разработки имеют обширные встроенные библиотеки полезных подпрограмм, что значительно облегчает программирование стандартных прикладных задач.
Но программист не должен думать, что подпро- граммы предназначены только для какой-то одной цели. Не следует всегда рассма- тривать подпрограммы только как программы общего назначения, которыми все могут пользоваться. Не менее важны и подпрограммы специального назначения, даже если они используются только в одной программе. В разделе 1.4.3.1 рассма- триваются типичные примеры подпрограмм. Простейшими являются подпрограммы, которые имеют только один вход и один выход, как, например, подпрограмма МАХ1МОМЗ рассмотренная выше (см. раз- дел 1.3.2, программа М). Еще раз приведем текст этой программы, изменив ее таким образом, чтобы поиск максимума велся по фиксированному числу ячеек, равному 100. м ИАХ1И0И ОР Х(1..100) ИАХ100 ЗТЗ ЕХ1Т Связь сподпрограммой.
ЗНЗЗ 1 З ~М. И ЗМР 2Р 1Н 1НРЗ З,З МЗ. В ЭОЕ В+3 2Н ЕМТ2 0,3 М4. Замена т. 1РА Х,З Найден новый максилзум. 0ЕСЗ 1 АЗРЗР. Уменьшение А. ЗЗР 1В 111. В ЕХП ЗИР * Вернуться к основной программе. 1 В большой программе, содержащей этот код в качестве подпрограммы, с помощью единственной команды "ЛИР ИАХ100" можно занести в регистр А значение текущего максимума для ячеек сч) + 1 по Х+ 100 и поместить информацию о положении максимума в г12. Связь с подпрограммой в этом случае достигается с помощью команд "ИАХ100 ЕТЗ ЕХ1Т" и позднее в "ЕХ1Т ЭИР *". Регистр Л работает таким образом, что команда выхода затем перейдет в ячейку, следующую за той, из которой было сделано первоначальное обращение к ИАХ100.
Ф В более новых модификациях компьютеров, таких как машина ММТХ, которой суждено заменить МХХ, предусмотрены более эффективные способы запоминания адресов возврата. Главное отличие состоит в том, что команды программы больше не модифицируются в памяти; необходимая информация сохраняется в регистрах или в специальном массиве, а не в самой программе (см. упр.
7). В гледуюшем издании данной книги будет применен современный подход к этим вопросам, а пока будем по-прежнему использовать старый самомодифиццруюшийся код. Нетрудно получить количественные характеристики степени экономичности кода и потери времени при использовании подпрограмм. Предположим, некоторый фрагмент кода занимает А ячеек и встречается в тп местах программы. Чтобы оформить этот фрагмент в качестве подпрограммы, понадобится дополнительная команда ЯТЗ, строка для команды выхода из подпрограммы плюс по одной команде ХИР в каждом из т мест, откуда будет вызываться подпрограмма.
В целом, необходимо т + А + 2 ячеек, а не гпй, поэтому экономия составляет (2) (т — 1) (Й вЂ” 1) — 3 ячеек. Если А равно 1 либо т равно 1, то, очевидно, мы не сможем сэкономить место в памяти за счет использования подпрограмм. Если А равно 2, то для получения выигрыша т должно быть больше 4, и т. д. Время теряется из-за применения дополнительных команд ЛИР, ЕТХ и ЛИР, которые не присутствуют в программе, если подпрограмма не используется. Поэтому, если во время выполнения основной программы подпрограмма применяется 1 раз, потребуется 41 дополнительных тактов. К этим оценкам следует подходить с определенной долей скепсиса, так как они делались в расчете на идеальную ситуацию.
Многие подпрограммы нельзя вызвать просто с помощью единственной команды ЗИР. Более того, если фрагмент кода повторяется во многих частях программы и он не оформляется в виде подпрограммы, то для каждой части данный код можно модифицировать так, чтобы получать преимущества от особых характеристик конкретной части программы, в которой он находится. С другой стороны, если принято решение использовать подпрограмму, то ее код нужно писать для наиболее общего, а не частного, случая, и обычно это требует добавления нескольких дополнительных команд. Если подпрограмма написана для общего случая, то она, как правило, зависит от параметрое. Параметры — это величины, которые управляют работой подпрограммы; они могут изменяться от одного вызова подпрограммы к другому.
Фрагмент кода внешней программы, который передает управление подпрограмме и должным образом запускает ее, называется последовательностью вызова. Конкретные значения параметров, которые передаются прн вызове подпрограммы, называются аргументами. В нашей подпрограмме ИАХ100 вызывающая последова- тельность — это просто команда «ЛИР ИАХ100".
Но в случае, когда необходимо передать аргументы, обычно необходима более длинная вызывающая последовательность. Например, программа 1.3.2М вЂ” зто обобщенный вариант ИАХ100; она находит максимум среди первых и элементов таблицы. Параметр п появляется в индексном регистре 1, и его последовательность вызова ЕР1 п ЕМТ1 и ЛИР ИАХ1ИОИ ЛИР ИАХ1ИЯИ включает два шага. Если последовательность вызова занимает с ячеек памяти, то формула (2) вычисления объема сэкономленного места принимает вид (3) (пз — 1)(/с — с) — сопэгапг, а время, которое тратится на связь с подпрограммой, немного увеличивается. Может возникнуть необходимость внесения дальнейших корректив в приведенные формулы, если потребуется сохранить и восстановить некоторые регистры. Например, работая с подпрограммой ИАХ100, следует помнить, что, записывая "ЛМР КАХ100", мы не только заносим максимальное значение в регистр А, а его позицию— в регистр 12, ио и обнуляем регистр 13.
Нужно иметь в виду, что подпрограмма может испортить содержимое регистров. Чтобы предотвратить изменение подпрограммой ИАХ100 содержимого г13, необходимо включить дополнительные команды. Самый короткий и самый быстрый способ сделать зто на М1Х состоит в том, чтобы вставить команду "ЯТЗ ЗР(0: 2)' сразу после ИАХ100 и команду "ЗН ЕМТЗ в"— непосредственно перед ЕХ1Т.
В итоге это выльется в две дополнительные строки кода плюс три машинных такта для каждого вызова подпрограммы. Подпрограмму можно рассматривать как расширение машинного языка компьютера. Внеся в память машины подпрограмму ИАХ100, получим единственную команду (а именно — "ЛМР ИАХ100" ), которая находит максимум. Важно определить результат работы каждой подпрограммы так же тщательно, как были определены сами операторы машинного языка. Поэтому программист обязательно должен записать характеристики каждой подпрограммы, даже если больше никто не будет пользоваться этой программой или ее спецификацией. Например, подпрограмма ИАХ1ИЯИ, приведенная в разделе 1.3.2, имеет следующие характеристики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
