► 34. [М25] (Транспонирующие блоки данных.) Одной из самых распространенных перестановок, использующихся на йрактике, является переход от q/3 к /За, где а и /3 - это подстроки массива. Другими слрвами, если xoxi ... Xm-i = а и XmXm+i Xm+n-i = то

нужно заменить массив XoXl . . . Xm+n-l - ар массивом ХтХт+\ Xm+n-\XoXl . . . Хт-1 =

/За. Это перестановка на множестве {О, 1,..., m + п - 1}, которая переводит к в {к + т) mod {т + п). Покажите, что каждая такая перестановка "с циклическим сдвигом" имеет простую циклическую структуру, и используйте эту структуру для разработки простого алгоритма получения нужной перестановки.

35. [МЗО] В продолжение предыдущего упражнения положим xoxi ...i(+m+„ i = 0,87, где а, /3 и 7 - строки длины I, т и п соответственно, и предположим, что нужно заменить q/37 на 7/3q. Покажите, что соответствующая перестановка имеет подходящую циклическую структуру, которая позволяет получить эффективный алгоритм. [Упр. 34 рассматривалось как частный случай при m = 0.] Указание. Рассмотрите замену (q/3)(7/3) на (7/3)(а/3).

36. [27] Напишите для MIX подпрограмму, реализующую алгоритм, который приведен в ответе к упр. 35, и проанализируйте время его выполнения. Сравните этот алгоритм с более простым методом, в котором осуществляется переход от а/Зу к (а/Зу) = ура и к 7/3q, где а обозначает полное обращение строки <т, т. е. строка читается в обратном порядке.

1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ 1.4.1. Подпрограммы

Когда некоторую задачу нужно выполнить в нескольких различных местах программы, то, как правило, нежелательно каждый раз повторять ее код. Чтобы избежать этого, данный код (называемый подпрограммой) можно поместить только в одном месте и добавить несколько дополнительных команд, чтобы после завершения работы подпрограммы должным образом возобновить выполнение внешней программы. Передача управления между подпрограммами и основной программой называется связью с подпрограммами.

Каждый компьютер имеет свои специфические способы установления эффективной связи с подпрограммами, которые обычно подразумевают применение специальных команд. В MIX для этой цели используется регистр J. Рассматривая данную тему, будем ориентироваться на машинный язык MIX, но аналогичные рассуждения применимы и к вопросам связи с подпрограммами для других компьютеров.

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

Подпрограммы имеют и другие преимущества. Благодаря им структура больших и сложных программ становится более наглядной. Они разбивают всю задачу на логические сегменты, что обычно облегчает отладку программы. Многие подпрограммы имеют дополнительную ценность, поскольку ими могут воспользоваться не только авторы, но и другие пользователи.

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

Простейшими являются подпрограммы, которые имеют только один вход и один выход, как, например, подпрограмма MAXIMUM, рассмотренная выше (см. раздел 1.3.2, программа М). Еще раз приведем текст этой программы, изменив ее таким образом, чтобы поиск максимума велся по фиксированному числу ячеек, равному 100.

♦ MAXIMUM OF Х[1..100]

МАХ100 STJ EXIT Связь с подпрограммой. ENT3 100 Ml. Инициализация. JMP 2F

1Н СМРА Х,3 МЗ. Сравнение.

JGE *+3 (1)

2Н ENT2 0,3 М4. Замена т.

LDA Х,3 Найден новый максимум.

DEC3 1 М5. Уменьшение к.

J3P IB М2. Все проверено? ЕХП JMP * Вернуться к основной программе.

в большой программе, содержащей этот код в качестве подпрограммы, с помощью единственной команды "JMP МАХ100" можно занести в регистр А значение текущего максимума для ячеек с- + 1 по X + 100 и поместить информацию о положении максимума в г12. Связь с подпрограммой в этом случае достигается с помощью команд "МАХ100 STJ EXIT" и позднее-"EXIT JMP Регистр J работает таким образом, что команда выхода затем перейдет в ячейку, следующую за той, из которой было сделано первоначальное обращение к МАХ100.

В более новых модификациях компьютеров, таких как машина MMIX, которой суждено заменить MIX, предусмотрены более эффективные способы запоминания адресов возврата. Главное отличие состоит в том, что команды программы больше не модифицируются в памяти; необходимая информация сохраняется в регистрах или в специальном массиве, а не в самой программе (см. упр. 7). В следующем издании данной книги будет применен современный подход к этим вопросам, а пока будем по-прежнему использовать старый самомодифпцирующийся код.

Нетрудно получить количественные характеристики степени экономичности кода и потери времени при использовании подпрограмм. Предположим, некоторый фрагмент кода занимает к ячеек и встречается в тп местах программы. Чтобы оформить этот фрагмент в качестве подпрограммы, понадобится дополнительная команда STJ, строка для команды выхода из подпрограммы плюс по одной команде JMP в каждом из т мест, откуда будет вызываться подпрограмма. В целом, необходимо т -\- к 2 ячеек, а не тк, поэтому экономия составляет

(m-l)(fc-l)-3 (2)

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

Время теряется из-за применения дополнительных команд JMP, STJ и JMP, которые не присутствуют в программе, если подпрограмма не используется. Поэтому, если во время выполнения основной программы подпрограмма применяется t раз, потребуется At дополнительных тактов.

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

Если подпрограмма написана для общего случая, то она, как правило, зависит от параметров. Параметры - это величины, которые управляют работой подпрограммы; они могут изменяться от одного вызова подпрограммы к другому.

Фрагмент кода внешней программы, который передает управление подпрограмме и должным образом запускает ее, называется последовательностью вызова. Конкретные значения параметров, которые передаются при вызове подпрограммы, называются аргументами. В нашей подпрограмме МАХ100 вызывающая последова-