Д. Кнут - Искусство программирования том 1 (1119450), страница 53
Текст из файла (страница 53)
Занести в область вывода пробелы. Взять следующий преобразованный символ. Сохранить его в поле (1: 1). Это "."? Если нет, взять другой символ. Сохранить его в поле (2: 2). Это "."? 1б ь ПЕРВАЯ СОПРОГРАММА 17 2Н 1МСА 30 18 ЛМР ООТ 10 1М1 8МР МЕХТСНАВ 20 ПЕСА 30 21 ЛАМ 2В 22 СМРА =10= 28 ЗОЕ 2В 24 ВТА я+1(0:2) 25 ЕМТ5 ь 25 ЗНР НЕХТСНАК 27 1МР ООТ 28 ОЕС5 1 20 15ММ ь-2 80 ЛМР 1М1 Это специальный символ? Найдена цифра и.
г15 +- я. Взять следующий символ. Отослать его в сопрограмму ООТ. Уменьшить и на 1. Повторить в случае необходимости. Начать новый цикл. ! гА = следующий символ ввода с соответствующим чис- лом повторений; содержимое г14 остается таким же, как при входе. содержимое гА, гХ, г15, г16 должно оставаться неиз- менным с момента последнего выхода. 3Е 9Р 1МР 1М ЯТА ООТРОТ+16,4(З:3) СМРА РЕК100 1Е 9Р 1ИС4 1 34М 1В ООТ 00ТРОТ(РОМСН) 3ВОЯ *(РОМОМ) 3МЕ ООТ1 Н1.Т АЬР мппо.
Если нет, взять следующий символ Сохранить его в поле (3 3) Это "."т Эта сопрограмма имеет следующие характеристики Последовательность вызова Состояние при выходе (при вызове 1М): 3МР ООТ. Содержимое регистров гА, гХ, г13, г16 остается неиз- менным с момента входа, значение в г11 может изме- ниться, предыдущий символ записывается в выходные данные Состояние при входе (при возврате). гА = следующий символ ввода с числом повторений; значение в г14 не меняется с момента последнего вы- хода.
Для завершения программы нужно обеспечить связь между сопрограммами (см. (1)) и должным образом выполнить инициализацию Инициализация сопрограмм — это довольно тонкое, хотя и несложное, дело 57 в ИНИЦИАЛИЗАЦИЯ И 56 ЯТАКТ ЕМТб О 56 ЕИТХ О 60 )МР ООТ1 61 ООТ ЯТ1 1МХ 66 ООТХ 3МР ООТ1 66 1И ЯТ) ООТХ 61 1МХ ЭМР 1М1 65 ЕИО ЯТАКТ СВЯЗЬ Инициализировать г1б для МЕХТСНАК Инициализировать гХ для МЕХТСВАК Начать с Опт (см упр 2) Связь сопрограмм Теперь программа полностью готова Читателю следует тщательно ее изучить, в особенности обращая внимание на то, как можно независимо написать каждую сопрограмму, считая, что другая сопрограмма — зто ее подпрограмма В приведенной выше программе состояния при входе и при выходе для сопрограмм 1М и СОТ идеально согласованы Но в более общем случае нам вряд ли так повезет и, чтобы связать сопрограммы, придется также включить команды загрузки и сохранения соответствующих регистров Например, если бы программа ООТ изменяла содержимое регистра А, то связь сопрограмм нужно было бы запро- 45 46 47 46 16 56 51 56 9Н 56 54 55 56 РЕК100 Перейти к следующему слову в буфере вывода Конец картыт Если да, перфорировать ее Ожидать завершения Вернуться за следующими символами, если не появилась "." Ввод Проход А Лента 1 Лента 1 Проход В Лента 2 Проход с Лента 3 Лента 2 Лента 3 Проход 0 Вывод (а) (Ь) Рис.
22. Проходы: (а) четырехпроходный алгоритм и (Ь) однопроходный алгоритм. граммировать следующим образом. ООТ ЯТ1 БТА ООТХ ЭИР 1М ЯТ3 ЖА 1МХ 3НР 1МХ НОЖА Сохранить А при выходе из 1М. ОПТ1 ООТХ НОЖА Восстановить А при выходе из ОВТ. 1М1 $ (4) Существует важная связь между сопрограммами и многопроходными алгоришмами. Например, описанный выше процесс преобразования можно выполнить за два отдельных прохода. Можно сначала выполнить только сопрограмму 1М, применяя ее ко всему вводу и записывая каждый символ с соответствующим числом повторений на магнитную ленту, а затем перемотать ленту в начало и выполнить только сопрограмму ООТ, выбирая символы с ленты группами по три. Такой процесс называется двухпроходным.
(На интуитивном уровне термин 'проход" воспринимается как полный просмотр входных данных. Это определение является неточным, и во многих алгоритмах совсем не очевидно, чему равно число выполненных проходов. Но, несмотря на некоторую неопределенность данного термина, полезно понять его на интуитивном уровне.) На рис. 22, (а) показан четырехпроходный процесс.
Во многих случаях будет оказываться, что такой же процесс можно выполнить только за один проход, как показано в части (Ь) рисунка, если заменить сопрограммами А, В, С, О соответствующие проходы А, В, С, О. Сопрограмма А вызывает В, после того как во время прохода А элемент выходных данных записан на ленту 1. Сопрограмма В вызывает А, после того как во время прохода В элемент входных данных считан с ленты 1. Сопрограмма В вызывает С, после того как во время прохода В элемент выходных данных записан на ленту 2 и т.
д. Пользователи ВМ1Хв узнают в этом "канал", который обозначается как ПроходА ~ ПроходВ ) ПроходС ~ Проходй. Программы, соответствующие проходам В, С и О, иногда называются фильтрами. И наоборот, процесс, выполняемый и сопрограммами, часто можно преобразовать в и-проходный процесс. Именно из-за этого соответствия имеет смысл провести сравнительный анализ многопроходных и однопроходных алгоритмов.
а) Психологическое отличие Для одной и той же задачи, как правило, проще создать и понять многопроходный алгоритм, чем однопроходный. Процесс, разделенный на ряд небольших шагов, выполняющихся один после другого, понять намного легче, чем запутанную процедуру, в которой множество преобразований выполняется одновременно.
Кроме того, если нужно написать большую серьезную программу, над которой будет совместно работать многочисленная группа разработчиков, то многопроходный алгоритм поможет естественным путем распределить работу мемду участниками проекта. Но такие преимущества многопроходного алгоритма присущи и сопрограммам, так как каждую из них можно написать, по существу, отдельно от других, а связь мех~ау сопрограммами превратит явно многопроходиый алгоритм в однопроходный процесс.
Ь) Разница ео времени выполнения. В однопроходном алгоритме не нужно тратить время на то, чтобы упаковать, записать, прочитать и распаковать промежуточные данные, которые передаются между проходами (например, информация на лентах на рис. 22). Поэтому однопроходный алгоритм выполняется быстрее.
с) Различие в обееме памлтш Для однопроходного алгоритма необходимо хранить в памяти все программы одновременно, в то время как для многопроходного алгоритма можно сохранять в памяти только по одной программе. Этот фактор может отразиться на скорости выполнения программы даже в большей степени, чем фактор, указанный в п, (Ь). Например, многие компьютеры имеют ограниченный объем "быстродействующей памяти" и большой объем "медленной памяти".
Если каждый проход поместится в быстрой памяти, то вся программа выполнится значительно быстрее, чем в случае использования сопрограмм в одном проходе (так как при использовании сопрограмм большинство программ, скорее всего, будут помещены в "медленную память" либо будут много раз загружаться и выгружаться из быстрой памяти).
Иногда возникает необходимость в разработке алгоритмов сразу для нескольких компьютерных конфигураций, одни из которых имеют больший объем памяти, чем другие. В таких случаях можно написать программу в виде набора сопрограмм и поставить число проходов в зависимость от размера памяти: загрузить сразу столько сопрограмм, сколько поместится, а подачу данных по недостающим связям обеспечить с помощью подпрограмм ввода или вывода. Несмотря на важность связи между сопрограммами и проходами, нужно иметь в виду, что программу, написанную в виде набора сопрограмм, не всегда можно представить в виде многопроходного алгоритма. Если сопрограмма В получает входные данные от А и отправляет обратно ключевую информацию сопрограмме А (как в приведенном выше примере программы игры в шахматы), то последовательность таких действий нельзя преобразовать в проход А, за которым следует проход В.
И наоборот, ясно, что некоторые многопроходные алгоритмы нельзя преобразовать в сопрограммы. Отдельные алгоритмы являются многопроходными по своей сути; например, для второго прохода может требоваться совокупная информация от первого прохода (скажем, общее число появлений некоторого слова во вводе). В этом отношении показательна следующая старая шутка. В автобусе. Маленькая старушка: "Мальчик, ты не подскажешь мне, когда нужно выходить, чтобы попасть на Пасадена-Стрит?".
Мальчик: "Просто следите за мной и выходите за две остановки перед тем, как выйду я". (Шутка заключается в том, что мальчик предлагает старуш(се двухпроходный алгоритм.) Вот пока и все, что касается многопроходных алгоритмов. С другими примерами сопрограмм мы будем встречаться в различных разделах книги, например они будут частью буферных схем в разделе 1.4.4. Сопрограммы играют также важную роль в моделировании дискретных систем (см. раздел 2.2.5).
Важная идея рспликацпонних сопрограмм обсуждается в главе 8, а некоторые интересные примеры применения этой идеи можно найти в главе 10. УПРАЖНЕНИЯ 1. [10] Объясните, почему автору трудно найти небольшие простые примеры сопрограмм. 2. [20) В программе, приведенной в тексте раздела, первой запускается сопрограмма ООТ. Что произойдет, если первой будет выполняться сопрограмма 1И, т. е. если в строке 60 поменять "1ИР ООТ1" на "1ИР 1И1"? 3. [20) Истинно ли утверждение "Все трн команды "СИРА РЕИ100" нз программы ООТ можно опустить, и программа по-прежнему будет работать" ? (Будьте внимательны.) 4. [20) Покажите, как связь между сопрограммами, аналогичную (1), можно реэлнзо.
вать на реальных компьютерах, которые вы хорошо знаете. 5. [1б) Предположим, для обеих сопрограмм 1И и ООТ нужно, чтобы в промежутке между входом и выходом содержимое регистра А оставалось неизменным. Другнмн словами, предположим, что в каждом случае появления команды "1иР 1И" внутри сопрограммы ООТ содержимое регистра А должно оставаться неизменным до возврата управления следующей строке. Аналогичное предположение делается по отношению к команде "1ИР ООТ" внутРи сопрограммы 1И.
Как в этом случае должна выглядеть связь между сопрограммами? (Ср. с (4).) 6. [02) Напишите команды связи между сопрограммами, аналогичные (1), для случая туся сопрограмм, А, В и С, каждая нэ которых может вызывать любую из двух других. (В каждом случае активизации сопрограммы выполнение начинается с того места, где оно закончилось в прошлый раз.) 7. [00) Напишите программу для И11, которая выполняет преобразование, обратное тому, которое осуществляет программа из текста раздела, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
