AOP_Tom1 (1021736), страница 47
Текст из файла (страница 47)
Учитывая тот факт, что каждое непустое слово в конце концов помечается, из строк 29, 35 и 67 находим, что (14) ,7=И вЂ” 2В, где У вЂ” число нспустых слов, содержащихся в перестановках ввода. Учитывая то, что каждый о|пличнмй от других элемент, содержащийся во входной перестановке, записывается в вывод только один раз, либо в строке 65, либо в строке 72, получаем (15) Р = Н + Я = количество различных элементов во вводе.
(См. соотношения (8).) Если немного поразмыслить, это очевидным образом сле- дует также из строки 80. И, наконец, из строки 85 видно, что Я = количество единичных циклов в выводе. (16) Очевидно. что величины В, С, Н, 7, Р и В, которые мы сейчас интерпретировали как независимые параметры, влияют на время выполнения программы А. Теперь остается проанализировать только неизвестные С и Т,. Для этого придется проявить немного больше изобретательности.
Просмотры входной информации, которые начинаются в строках 41 и 74, всегда заканчиваются либо в строке 47 (прошлый рвз), либо в строке 80. В течение каждого из этих Р+ 1 циклов команда "1МСЗ 1" выполняется В+ С раз. Это имеет место только в строках 44, 68 и 77, поэтому получаем нетривиальное соотношение (17) С+ 7+ 1, = (В+С) (Р+1), (112А|Л + 304Х вЂ” 2М вЂ” Г + 110 + 2à — 11) и. (18) В этой формуле были использованы новые обозначения для характеристик данных: Л" — количество 1' — количество ЛХ вЂ” количество А| — количество У вЂ” количество И вЂ” количество перфокарт ввода; непустых полей во вводе (исключая конечное "="'); циклов во вводе; (19) имен различных элементов во вводе; циклов в выводе (включая единичные циклы); единичных циклов в выводе.
связывающее неизвестные С и Т,. К счастью, время выполнения (7) — зто функция от С+1 (так как оно включает слагаемые" +ЗР+4С" +ЗК ч-4Ь+" =" +7С+ + 71 + "), поэтому нам не нужно больше пытаться анализировать величины С и Т,по отдельности. Просуммировав все эти результаты, находим, что общее время выполнения программы без учета времени, затрачиваемого на операции ввода-вывода, равно Таблица 2 ПЕРЕМНОЖЕНИЕ ПЕРЕСТАНОВОК ЗА ОДИН ПРОХОД (акУд)(Ьса)(аей)(владе)(ЬдУае) а -+ дааааааааааааддйддйееееееееаа Ь-+ ссссссссддддддддддддддддЬЬЬЬЬ с -+ ееедНд0аасссссссссссссссссссс 4 -> ддддддд)))Ид)))ЬЬЬЬЬИддддддаа е -+ ЬЬ6666ЬЬЬЬЬ6Ь6ааа))))Ь6)))))е 1 -+ 1111ееееееесееееееаааааааа111 д -+ а ) ) ) ) 1 у 1 .( у у у у 1 1 7 7 у 1 ~ 1 у у у 1 д д д д Следовательно, можно сделать вывод, что анализ такой программы, как А, во многих отношениях подобен решению занимательной головоломки. Ниже мы покажем,что если на выходе предполагается получить случайную перестаиовку, то средние величин (1 и Ь' будут равны НА и 1 соответственно.
Другой подход. Алгоритм А перемножает перестановки почти так же, как это обычно делают люди. Часто оказывается, что задачи, решаемые с помощью компьютера, очень похожи на те, с которыми люди постоянно сталкивались в течение долгих лет. Поэтому освященные веками методы решения, разработанные для простых смертных, таких, как мы с вами, подходят и для компьютерных алгоритмов. Но не менее часто приходится иметь дело с новыми методами, которые идеально подходят для компьютера, но совершенно непригодны для человека.
Главная причина этого состоит в том, что компьютер "думает" по-другому: тип его памяти, с помощью которой он запоминает информацию, отличается от типа памяти человека. Это различие можно проследить на примере нашей задачи перемножения перестановок. Используя приведенный ниже алгоритм, компьютер может выполнить умножение перестановок "одним махом", запоминая текущее состояние перестановки в целом по мере перемножения циклов. Предназначенный для человека алгоритм А просматривает формулу много раз, по одному для каждого элемента вывода, в то время как новый алгоритм делает все за один проход. Нагло эаргепэ на такое вряд ли способен.
Что представляет собой предназначенный для компьютера метод перемножения перестановоку Главная идея проиллюстрирована в табл. 2. В столбце, расположенном в этой таблице под каждым символом выражения, которое представлено в виде циклов, показано, какая перестановка выражена частичными циклами справа. Например, фрагмент формулы "... а е)(Ь д у а е)" представляет перестановку аЬспеуд которая появляется в таблице под крайним справа символом а. Внимательно изучив табл.
2, можно понять принцип ее построения, если начать с тождественной перестановки справа и двигаться назад справа налево Столбец, расположенный под символом х, отличается от столбца справа (в котором записано предь~дущее состояние) только строкой х; и новое значение в строке х — это значение, которое исчезло в результате предыдущего изменения. Короче говоря, имеем следующий алгоритм. Алгоритм В (Перел|нозсение перестановок, представленных в виде циклов). Этот алгоритм (рис. 21) дает, в сущности, тот же результат, что и алгоритм А. Предположим, что переставляемыми элементами являются хы хг,..., х„. Будем использовать вспомогательную таблицу Т[1],Т[2],...,Т[п]; по окончании работы алгоритма х; переходит в х в перестановке авода тогда и только тогда, когда Т[1] = 11 В1.
[Инициализация.] Присвоить 1 [1е] <- )е, где 1 < й < и. Подготовиться также к просмотру справа налево. В2. [Следующий элемент.] Рассмотреть следующий элемент ввода (справа налево). Если ввод исчерпан, то работа алгоритма заканчивается. Если рассматривается элемент ")", то присвоить Я е- О и повторить шаг В2; если это элемент а(", то перейти к шагу В4. В противном случае рассматривается элемент х; для некоторого 1; тогда перейти к шагу ВЗ. ВЗ.
[Замена Т[е].] Выполнить взаимный обмен Я ~ Т[1]. Если в результате полу- чится Т[1] = О, то присвоить у' е- 1. Вернуться к шагу В2. В4. [Замена Т[у].] Присвоить Т[1] е- Е (Здесь 1 — это строка, определяющая элемент ")" в обозначениях табл. 2, т. е. правую скобку, которая соответствует только что просмотренной левой скобке.) Вернуться к шагу В2. ! Рис. 21. Алгоритм Рл перемножение перестановок.
Разумеется, после выполнения этого алгоритма необходимо еще вывести содержимое таблицы Т в циклическом виде; как будет показано ниже, зто легко сделать методом "пометок". Теперь на основе нового алгоритма давайте напишем программу для Н1Х. Будем придерживаться тех же основных правил, что и в программе А, используя такой же формат ввода и вывода, как и раньше. Но тут возникает небольшая проблема: как можно реализовать алгоритм В, не зная наперед, чему равны элементы хе,хэ,...,х„? Неизвестно, чему равно и, а также будет ли элемент 6 равен хз нли хэ и т.
д. Существует простой способ решения данной проблемы — создать таблицу, внести в нее имена элементов, которые уже встречались, и каждый раз искать имя текущего элемента (см. строки 35-44 в программе ниже). Программа В 1Дает глот згсе результат, что о программа А). гХ = Е; г14 = г; г11 = Э'; г13 = п, количество различных просмотренных имен. 01 МАХЫОЯ Е00 08 Х ОК10 08 Т ОК10 04 РЕКИ ОК1С 05 АМЯ ЕЦ0 05 ООТБОР ОК10 07 САКОЯ ЕЦО Совпадают со строками 05-22 программы А. АМЯ ООМЕ Х,З БКТР Т,З БК1Р ЬРКЕМ Х,З Х,З 1 Я Т Т Открыть цикл. Пометить имя.
81 Н1.Т 85 1Н 1МС2 йб ЕМТЗ 87 К1СНТ ЕМТХ 28 ЯСАМ ОЕС2 УУ ЬОА ЭО ЭАХ 81 СИРА 88 ЭЕ ЭЭ СИРА 88 ЭЕ 85 ЕМТ4 Эб ЯТА 87 2Н ОЕС4 Э8 СИРА ЭУ ЭМЕ 10 54Р 1МСЗ 18 ЯТА 88 ЯТЗ 88 ЕМТ4 бб РООМО ЬОА бб ЯТХ 17 ЯКС 18 ЭАМХ 50 ЕМТ1 50 ЭНР 51 1.еГт ятх 58 СТСЬЕ 52Р 58 54 ОСТРОТ ЕМТ1 55 532 5б 1Н ЬОАМ 57 ЭАР 58 СМРЗ 5У ЭЕ бО МОУЕ б1 2Н МОЧЕ 58 ЯТА 1200 ь+НАХМОБ а+НАХМОБ а+МАХЫОЯ РЕНН *+24 ббб 13 1 0 1 РЕНН, 2 СТСЬЕ КРЕЕМ К1СНТ ЬРКЕМ ЬЕРТ 1,3 Х 1 1,4 2В РООМО 1 Х,З Т,З 0,3 Т,4 Т,4 Я ЯСАМ 0,4 ЯСАМ Т,1 БСАМ 1 1 А В В В С С В В Е Е Р Г Р б Н Н Н Н Э Э Э К К Р Максимальная длина ввода. Таблица имен. Вспомогательная таблица состояния.
Входная перестановка. Место для ответа. Место для печати. В этот момент г12 слов ввода находятся в РЕАМ, РЕКИ+ 1, ... и мы пока еще не видели ни одного имени. Присвоить Е +- О. ВЭ. Сле юл ий элемент. Пропустить пробелы. Следующим элементом является ")"? Это "("? Приготовиться к поиску, Сохранить в начале таблицы. Искать в таблице имен, Повторять до нахождения соответствия. Это имя появлялось ранее? Нет; увеличить размер таблицы. Вставить новое имя х„.
Присвоить Т~п] +- и, г +- п. ВЗ. Замена Т~~, Сохранить Е , г. Если Я было нулем, присвоить Э < — 1. В4. Замена У~Я, Вернуться к В2, есин работа еще не закончена. Весь ввод просмотрен. Таблицы х и Т содержат ответ. Теперь построим циклическую запись, Имя было помечена? Это единичный цикл? 84 ЕООАЕЯ АЬР 85 ЕМО ВЕО1М бЮ ЕВЗ 54 ЕРАМ б5 5АМ бб МОЧЕ 57 ВИ1Р ОЕСЗ б8 ЭЗР бб 70 РОМЕ СИР1 Т,З Х,З 2В КРЕЕМ 1 1В Т Найти элемент, в который переходит этот элемент. Т Т Он уже помечен? И' Да., цикл закрывается. Я Перейти к следующему имени. г Совпадают со строками 48 — 62 программы А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
