AOP_Tom1 (1021736), страница 45

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 45)

[Ссылки. %. АЬгепе, МагЛетапзсЛе Улгегйа)гипбел оп6 Бр1е!е 2 (Ье~рлй: ТеиЬпег, 1918), СЬареег 15.[ Рис. 17. Задача Иосифа, п = 8, гп = 4. Рис. 18. Магический квадрат. 23. [Я7] Цель этого упражнения — помочь читателю получить опыт применении компьютеров в сфере, где выходные данные должны быть отображены графически, а не в традиционном табличном виде. В данном случае необходимо "нарисовать" схему кроссворда. Входными данными является матрица, состоящая нз нулей и единиц. Нуль соответствует белому квадратику, а единица — черному.

В качестве выходных данных нужно получить схему кроссворда, в котором соответствующие квадратики с номерами обозначают слова, расположенные по вертикали н по горизонтали. Например, для матрицы 1 0 0 0 О 1 0 0 1 0 0 0 0 0 0 0 1 0 О 1 О О О О 0 0 0 1 0 0 1 0 0 0 0 1 Рис. 18. Схема кроссворда, соответствующая матрице из упр. 23. Черные +++++ квадраты: +++++ +++++ Номер вв ванн+ белого квадрата: инни+ +++++ Непронумерованные белые квадраты: инни+ нинн+ +++++ находятся -1: нинин НОНОО НОННО Квадраты с -1 нонн+ ниии+ +++++ в зависимости от того, справа или снизу ниии+ иннин нинин ниии+ нинин ниии+ +++++ нинин инин+ соответствующая схема кроссворда должна выглядеть, как показано на рис. 18.

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

18, где черные квадратики по углам были удалены. Существует простой способ достижения этой цели — "искусственно" вставить строки и столбцы, содержащие -1 сверху, снизу и по боковым сторонам заданной входной матрицы, а затем поменять каждую +1, которая соседствует с -1, на -1, пока рядом с любой — 1 не останется ни одной +1. Для печати окончательной схемы на АЦПУ следует использовать следующий метод. Каждый квадратик кроссворда должен отображаться на печатной странице с помощью 5 столбцов и 3 строк, причем эти 15 позиций заполняются следующим образом. Рис. 19. Распечатка на АЦПУ кроссворда, показанного на рис.

18. 1.3.3. Применение к перестановкам В данном разделе мы приведем еще несколько примеров программ для М1Х и наряду г этим познакомимся с некоторыми важными свойствами перестановок. Эти исследования позволят также выявить интересные аспекты компьютерного программирования в целом. Перестановки уже обсуждались в разделе 1.2.3; в нем перестановка сдуЬеп рассматривалась как некоторое распололесение шести объектов а, Ь, с, д, е, у в ряд. Но возможна и другая точка зрения.

Перестановку люжно рассматривать как передпорядочение или переименование объектов. При такой интерпретации» обычно используют двухстрочную запись, например аЬсдет Это означает, что ва переходит в с, Ь переходит в д, с переходит в у, е( переходит в Ь, е переходит в е, у переходит в а". С точки зрения переупорядочения зто означает, что объект с переходит на место, которое ранее занимал объект а. А если рассматривать это как переименование, то можно считать, что объект а переименован в с. При использовании двухстрочной записи изменение порядка столбцов в перестановке никакой роли не играет.

Например, перестановку (1) можно записать в виде 7' Ь а П с е а также еще 718 способами. В связи с описанной интерпретацией часто используют циклическую запись. Перестановку (1) можно записать и в виде (2) (а с у) (Ь д), ' В русскоязычной математической литературе в этом случае часто используют термин "пол- стаповкГ. — Прим.

перев. Схема, изображенная на рис. 18, будет напечатана, как показано на рис.' 19. Ширины строки принтера — 120 символов— достаточно для того, чтобы печатать кроссворды, содержащие до 23 столбцов. В качестве входных данных должна быть предоставлена матрица размера 23 х 23, состоящая из нулей и единиц, все строки которой перфорируются в столбцах 1-23 входной перфокарты.

Например, карта, соответствующая первой строке приведенной выше матрицы, будет перфорирована следующим образом: "10000111111111111111111". Схема кроссворда необязательно будет симметричной, и у нее могут оказаться длинные ленты черных квадратиков, присоединенные к наружным сторонам кроссворда самым экзотическим образом. +н+н+н+н+н++нн +01 + Юз воз + + + э + ' вн +вава в+++++н+нвнн+++нн +ОФ + нинов + +06 + + +нв в+ в + +в+вв++н+внвв++в+ннвв++++вв +07 + +08 + ++вн+ + в вн+++ + ++нннн+++++ н+++++++++нн+ ++++++00 в +10 + н++ в+ ++вв++в+в+++внвннчв+н+ввв++ +11 +]2 + ннн13 в+++ н +в++н+нч+++++'н+н+н+н+++н +14 + + в + + + + в+++н+н+н+эн++и+ что, опять же.

означает "а переходит в с, с переходит в (, 1 переходит в а, Ь переходит в д, Н переходит в Ь". Цикл (я~ яз,., я„) означает "х, переходит в ят, ..., х„, переходит;р х„, х„переходит в х~". Так как элемент е является в перестановке фиксированным (т. е, переходит не в какой-либо другой элемент, а в самого себя), он не появляется в циклической записи.

Таким образом. единичные циклы типа "(е)" записывать не принято, Если в перестановке фиксированными являются все элементы. так что присутствуют только единичные циклы, то она называется тпозсдссглвеиной перестпановкой и обозначается "()". Запись перестановки в виде цикла не является единственной. Например, (Ьс() (а сг). (с.г а) (Ь И), (п Ь) (1 а с) и т. д. эквивалентны (2). Но запись "(а г" с) (ЬИ)" уже не будет им эквивалентна, так как она означает,что а переходит в 1. Легко видеть, почему перестановку всегда можно представить в виде цикла.

Начиная с элемента х,, перестановка переводит, скажем, х~ в хз, хт в хз и т. д., пока наконец (поскольку количество элементов ограничено) мы не придем к некоему элементу х„.ы, который уже встречался среди хы ... х„. Этот элемент х„.ы должен быть равен хъ Предположим, он равен хз. Но это невозможно, так как известно, что хт переходит в хз, а по предположению в х„е, переходит х„ф. х . Поэтому х„.ь~ = х~ и получаем цикл (я~хз., х„), являющийся частью перестановки для некоторого и > 1.

Если этим циклом вся перестановка не исчерпывается. то существует элемент у,, такой, что д, ф х, для всех г, для которого аналогичным образом получим еще один цикл (у, рз... у ). Ни один у, не может равняться любому х„так как нз я, = у следует, что х,~, = у +~ и т. д. В конце концов для некоторого Й получим яь = 1п, что противоречит предположению о выборе уъ Действуя подобным образом, можно найти все циклы, содержащиеся в перестановке. В программировании эти понятия применяются каждый рэз, когда некоторый набор из и объектов нужно расположить в другом порядке. Чтобы переупорядочить объекты, не перемещая их в какое-либо другое место, необходимо, в сущности, придерживаться циклической структуры.

Например, чтобы переупорядочнть (1), т. е. присвоить (а.Ь,с,д.е,у)< — (с,Ы, (,Ь,с,а), будем следовать циклической структуре (2) и последовательно присваивать 1+-а, а+-с, с< — (. (<-й 1+-Ь, Ь+-д, Н<-б Но нужно отдавать себе отчет в том, что любое подобное преобразование можно осуществлять в непересекающихся циклах. Произведения перестановок. Две перестановки можно перемножить в том смысле, что их произведение означает применение одной перестановки вслед за другой. Например, если за перестановкой (1) следует перестановка а Ь еде 1 то получим, что а переходит в с, которое затем переходит в с; Ь переходит в д, которое затем переходит в а и т. дс аЬсае г аЬсдег аЬсдеу сауЬеа саед г Ь (4) Вполне очевидно, что произведение перестановок не обладает свойством коммутативности; другими словами, я1 х кт необязательно равно лт х хм где л| и яз †перестанов.

Читатель может убедиться в том, что, если поменять местами сомножители, произведение в (4) даст другой результат (см. упр. 3). Кое-кто перемножает перестановки справа налево, вместо того чтобы делать зто более естественным образом слева направо, как показано в (4). Фактически математики разделились на два лагеря: одни считают, что результат последовательного применения преобразований Те и Тз следует обозначать через Т1 Тт, а другие— через ТтТм Здесь мы будем использовать обозначение Т1 Тз. Пользуясь циклической записью, запишем равенство (4) следующим образом: (ас1) (Ьд) (аЬд) (е1) = (асе~Ь). (5) Обратите внимание на то, что знак умножения "х" принято опускать; это не противоречит циклической записи, так как легко видеть, что перестановка (асУ)(Ьа) на самом деле является произведением перестановок (ас г) и (Ьд).

Произведение перестановок можно выполнять непосредственно с помощью циклической записи. Например, вычислив произведение перестановок (6) (а с ~ д) (Ь с д) (а е а) (Я а с( е) (Ь д ( а е), Алгоритм А (Перемножение перестановок, предсгпавленнмх в виде циклов). Этот алгоритм (рис. 20) берет произведение циклов, такое как (6), и вычисляет получающуюся в результате перестановку в виде произведения непересекающихся циклов.

Для простоты здесь не приводится описание процедуры удаления единичных циклов; зто было бы лишь незначительным обобщением алгоритма. По мере выпол- находим (двигаясь слева направо), что "а переходит в с, с переходит в И, «( переходит в а, а переходит в И и д остается без изменений". Таким образом, конечным результатом (6) является то, что а переходит в д, и мы запишем "(а И" в качестве частичного ответа.

Теперь выясним, что происходит с д: "д переходит в Ь, которое затем переходит в д"; следовательно, имеем частичный результат "(адд". Рассмотрев, что происходит с д, находим, что "д переходит в а, затем в е, в ( и в а"; таким образом, первый цикл замыкается: "(а дд)". Теперь выберем новый злемент, который еще не встречался, например с. Находим, что с переходит в е, и читатель может проверить, что окончательным ответом для (6) будет "(а дд)(се 5)".

А теперь попробуем выполнить эту процедуру с помощью компьютера. Следующий алгоритм формализует описанный выше метод таким образом, чтобы его можно было выполнить с помощью компьютера. Рис. 20. Алгоритм А (перемножение перестановок). пения алгоритма последовательно "помечаем" элементы исходной формулы, т. е. те символы, которые уже "обработаны". А1. [Первый проход.] Отметить все левые скобки и заменить все правые скобки помеченной копией входного символа, который следует за соответствующей левой скобкой (см. пример в табл. 1), А2.

[Раскрытие скобок.] Выполнив поиск слева направо, найти первый непомеченный элемент входной формулы. (Если все элементы помечены, то работа алгоритма заканчивается.) Установить ЯТАНТ равным этому элементу; вывести левую скобку; вывести элемент и пометить его. АЗ. [Установка С11ННЕМТ.] Установить СоННЕИТ равным следующему элементу формулы.

Характеристики

Список файлов книги