Д. Кнут - Искусство программирования том 1 (1119450), страница 45
Текст из файла (страница 45)
[Установка С1ЖВЕМТ.] Установить СМВВЕМТ равным следующему элементу формулы. А4. [Просмотр формулы.] Продвигаться вправо, пока не будет либо достигнут конец формулы, либо найден элемент, равный СМВВЕМТ; в последнем случае пометить его и вернуться к шагу АЗ. А5. [С1ЖВЕМТ = ЯТАВТ?] Если ССВВЕМТ ф ЗТАВТ, вывести ССВВЕМТ и вернуться к шагу А4, снова начав с левого края формулы (продолжая тем самым вывод искомого цикла). А6.
[Закрытие.] (Полный искомый цикл выведен.) Вывести правую скобку и вернуться к шагу А2. 1 Например, рассмотрим формулу (6). В табл. 1 показаны последовательные этапы ее обработки. В первой строке таблицы приведена формула после замены правых скобок начальными элементами соответствующих циклов. В последующих строках показан процесс обработки формулы по мере пометки все большего числа элементов. Курсор указывает на текущий элемент, подлежащий обработке. В результате будет выведено следующее выражение: "(аг(д)(сеЬ)(/)". Обратите внимание, что в выводе присутствует единичный цикл.
Программа для И1Х. Чтобы реализовать этот алгоритм для М1Х, "пометки" можно делать с помощью знака слова. Предположим, что входная формула перфорирована на картах в следующем формате: состоящая из 80 колонок карта разделена на 16 полей по 5 символов. Каждое поле представляет собой один из следующих вариантов: (а) "„„оо(", что обозначает левую скобку начала цикла; (Ь) ")оооо", Таблица 1 ПРИМЕНЕНИЕ АЛГОРИТМА А К ВЪ(РАЖЕНИЮ (б) После шага ЯТАВТ СРВВЕИТ А1 Вывод )(аед) аед (а лед лед аед ае ае ае ае ) (с е Ь ) (У) Здесь | обозначает положение курсора сразу эа только чта провереииыч элементом помечеииые элементы выделены «вез чв серым цветом что обозначает прав) ю скобку конца цикла, (с) "ыоыыы", т е все пробелы, которые можно вставить в любом месте, чтобы заполнить пространство, (()) любой символ, обозначающий элемент, который нужно переставить Последняя карта входных данных определяется по тому, что в ее колонках 76 — 80 содержится "ы„ыымч Например, (6) можно перфорировать на двух картах следующим образом ( а с е с ) ( В С Р ) ( А Е Р ) Г А Р Е ) ( в с г А е ) В выводе нашей программы будет содержаться точная копия ввода с последующим ответом в таком же, в сущности, формате Программа А (Перемнвз(сение перестановок, представленных в виде циклов) В этой программе реализован алгоритм А, а также предусмотрены процедуры ввода, вывода и )даления единичных циклов 01 ВАЖОЯ ЕОО 02 РЕВИ ОВ10 03 АИЯ ОВ10 04 ООТВОР ОВ10 05 САВОЯ ЕОО 00 РВТИТЕВ ЕОО 07 ВЕ01И 1И 1200 в+ИАХИОЯ ч+ИАХИОЯ «+24 16 18 РЕВИ (САВОЯ) Максимальная длина ввода Вводная перестановка Место для ответа Место дли печати Номер устройства чтения перфокарт Номер АЦПУ Читать первую карту А2 АЗ А4 А4 А4 А5 А5 А5 Аб А2 А5 А5 Аб Аб ( а с г" д ) асуд (с(у с ~д с10 с(у суд суд сУу су су У Х 1 (Ьсд Ьсд Ьсд Ьсд 6 14 6 д Ь Ь д Ь Ь Ь Ь Ь Ь (Уаде Г" а ч( е уаде зад 1аде Тоде Х Хд де ,( де д У д У д )(Ьдуае) Ьд/ае Ь д,( а е Ьу/ае Ьдуае 601ае Ьузае Ьдуае А уз" 1 д ае~ д ае д ае е 1 д 1 ООМЕ СМР1 =АИЯ 5ИЕ «+2 МОЧЕ ЬРВЕИ(г) МОЧЕ =0= МОЧЕ -1,1(22) ЕМТЗ 0 ООТ АМЯ,З(РВ1ИТЕК) 1МСЗ 24 ЬОХ АМЯ,З 1ХМЕ «-3 48 50 51 53 58 54 55 55 57 08 00 10 11 18 18 11 15 15 17 18 10 80 81 38 88 84 85 Уб 87 88 88 80 81 80 88 81 85 8б 87 88 80 40 41 40 48 44 85 бб 17 1Н 1Н 2Н 1Н ОРЕМ 1Н ЕМТ2 0 ЬРА ЕЦОАЬЯ )ВОЯ «(САНИЯ) СИРА РЕВИ+16,2 5Е *+2 1И РЕКМ+16,2(САКОВ) ЕИТ1 ОБТЕР 1ВУЯ «(РК1МТЕК) МОЧЕ РЕКИ,2(16) СОТ ООТВОР(РВ1МТЕВ) ЛЕ 1Р 1МС2 16 СМР2 МАХИРЯ-16-" ЛЬЕ 1В НЬТ ббб 1ИС2 16 ЯТ2 31ЕЕ ЕИТЗ О ЬОАМ РЕЕМ,З СИРА ЬРВЕИ(1:б) ЯМЕ 1Р ЯТА РЕКИ,З 1МСЗ 1 ЬОХИ РЕВИ,З 1ХЕ «-2 СМРА КРВЕИ(1:б) ЛИЕ «+2 ЯТХ РЕВИ,З 1МСЗ 1 СМРЗ Я1ЕЕ ЛЬ 2В ЬОА ЬРВЕМ ЕИТ1 АМЯ ЕИТЗ О ЬОХМ РЕКИ,З ЛХМ ОО 1ИСЗ 1 СМРЗ 31ЕЕ ЗЬ 1В Ожидать окончания цикла Это последняя перфокартат Нет, читать следующую.
Напечатать копию введенной перфокарты. Повторять до окончания ввода. Слишком много входной информации! В данный момент г12 введенных слов находятся в ячейках РЕКИ, РЕВИ + 1, ~3,Д«~~««я« Взять следующий элемент ввода. Это "("7 Если да, пометить ее. Поместить следующий непустой символ ввода в гХ Заменить ")" помеченным элементом из гХ. Все элементы обработаны? Подготовиться к главной программе.
Н1 — место сохранения следующего ответа. Й2. Искать непомеченный элемент Все элементы помечены. Выполняется вывод Ответ является тождественной перестановкойу Если да, заменить на "О" Поместить 23 слова пробелов после ответа. Напечатать столько строк, сколько необходимо. НЕТ АЕР ( АЬР ) АЕР 5В 5У е бО ЫжМ 51 КРЕЕМ бв ЕООА13 бв 54 ао б5 бб 57 ЯОСС бв бУ 70 71 78 ЬН 78 74 75 4Н 7б 77 1Н 7В 7У во 81 88 С|ОЯЕ 88 84 Вб 8б 87 МОЧЕ ЕРКЕМ МОУЕ РЕКИ,З ЯТХ ЯТАКТ ЯТХ РЕЕМ,З 1МСЗ 1 15)ХИ РЕКИ,З(1:6) ЛХИ 1Р 5МР е"3 ЯТХ 0,1 1МС1 1 ЕМТЗ 0 СМРХ РЕЕМ,311:6) ЛЕ ЯОСС 1МСЗ 1 СМРЗ 31ХЕ ЛЕ 4В СМРХ ЯТАКТ(1:6) ЛМЕ ЯВ МО7Е КРЕЕМ СМРА -3,1 ЗИЕ ОРЕМ 1МС1 -3 ЛМР ОРЕИ ЕМВ ВЕ01М Константы, используемые в программе.
Н Открыть цикл в выводе. Н Н 5 Пометить элемент. У Сделать один шаг вправо. 5 АЗ. Установить СШШВУТ (а именно — гХ). 5 Пропустить пробелы. 0 г) Вывести СОККЕИТ. Ю Снова просмотреть формулу. К А4. Н осмот о и лы. К Элемент = СОККЕМТ? Х Продвинуться вправо. Е Конец формулы'> Ь Р А5. СОИВЕУТ БТАКТ? Р г А6.3 Н Заметить: гА = "С'. Н 5 Удалить единичные циклы. 5 Эта программа, содержащая примерно 75 команд, значительно длиннее программ из предыдущего раздела, да и большинства программ, с которыми мы встретимся в этой книге.
Но ее длина не должна внушать вам страх, так как она делится на несколько маленьких частей, которые достаточно независимы одна от другой. В строках 07 — 22 происходит считывание входных перфокарт и печать копии каждой карты; в строках 23-38 выполняется шаг А1 алгоритма, т. е. предварительная обработка входных данных; в строках 39 — 46 и 64 — 86 выполняется основная часть алгоритма А, а в строках 48 — 57 выводится ответ.
Читателю полезно изучить как можно больше программ для МТХ, приведенных в данной книге, поскольку чрезвычайно важно приобрести опыт чтения программ, написанных другими. Но, к сожалению, подобной формой обучения пренебрегали на многих компьютерных курсах, что привело к крайне неэффективному использованию компьютерной техники. Время выполнения. Те части программы А, которые не связаны с операциями ввода-вывода, снабжены счетчиками частоты, указывающими, сколько раз они выполняются (как в программе 1.3.2М); таким образом, предполагается, что строка 30 выполняется В раз. Для удобства считается, что во входной информации пустые слова могут находиться только у правого края; при этом условии никогда не выполняется строка 71 и никогда пе происходит переход в строке 32.
Выполняя простые операции сложения, получаем, что общее время выполнения программы равно (7+ 5А+ БВ+ 7С+ 2Р+ Е+ ЗГ+ 4С+ 8Н+ Бд + ЗК + 4Ь + ЗР + 4Я + 6Л + 25) и (7) плюс время, затрачиваемое на ввод и вывод. Чтобы понять смысл формулы (7), нужно рассмотреть пятнадцать неизвестных .4, В, С, Р, Е, Р, О, Н, Х, К, Ь, Р, Я, Л, о' и связать их с соответствующими характеристиками входных данных.
Проиллюстрируем общие принципы решения проблем подобного рода. Сначала применим первый закон Кирхгофа теории электрических цепей: команда должна выполняться столько раз, сколько раз осуществляется переход к ней. Это, казалось бы, очевидное правило часто приводит к неочевидным соотношениям между несколькими величинами. Анализируя ход выполнения программы А, получаем следующие уравнения, Лэ стпрок Выведено Ие все уравнения, полученные с помощью закона Кирхгофа, будут линейно независимыми, например в данном случае мы видим, что первое и второе уравнения явно эквивалентны. Более того, последнее уравнение можно вывести из остальных, так как из третьего, четвертого и питого следует, что Н = Л.
Таким образом, шестое означает, что К = Ь вЂ” Л. Во всяком случае мы уже исключили шесть из пятнадцати неизвестных: А=С, Е=Л+1, Г=Л+С, Н=Л, К=А — Л, ~=Р— Л. (8) Первый закон Кирхгофа — это очень эффективное средство; более подробно мы рассмотрим его в разделе 2.3.4.1. Следующий шаг состоит в том, чтобы попытаться сопоставить переменные с важными характеристиками данных. Из строк 24, 25, 30 и 36 находим, что (9) В + С = количество слов ввода = 16Х вЂ” 1„ где Л вЂ” число перфокарт с входной информацией.
Из строки 28 получаем, что В = количество "(" во вводе = количество циклов во вводе. Аналогично из строки 34 получаем Р = количество ")" во вводе = количество циклов во вводе. (10) 26, 38 33, 28 41, 84, 86 42, 46 64, 43 67, 70, 76 75, 79 82, 72 А = 1+(С вЂ” 1) С = В + (А — В) Е=1+Л Р = Е + (С вЂ” 1) Н=Р— С д = Н+ (К- (Ь вЂ” д)) К= Я+(Ь вЂ” Р) Л=Р— ц А теперь из (10) и (11) получаем то, что нельзя вывести из закона Кирхгофа: В = В. (12) Из строки 64 получаем Н = количество циклов в выводе (включая единичные циклы). (13) Из строки 82 следует, что Н равно этой же величине; в данном случае соотношение Н = Н можно бьло вывести из закона Кирхгофа, так как оно уже содержится в (8). Учитывая тот факт, что каждое непустое слово в конце концов помечается, из строк 29, 35 и 67 находим, что (14) ,7 = 1' — 2В, где У вЂ” число непустых слов, содержащихся в перестановках ввода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
