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