Д. Кнут - Искусство программирования том 1 (1119450), страница 44
Текст из файла (страница 44)
18. Квадратик нумеруется, если он белый н либо (а) под ним расположен белый квадратик н прямо над ннм нет белого квадратика, либо (Ь) справа находится белый квадрат и непосредственно слева нет белого квадрата. Если черный квадратик оказался у края, то его нужно удалить из схемы. Это проиллюстрировано на рнс. 18, где черные квадратики по углам были удалены.
Существует простой способ достижения втой цели — "искусственно" вставить строки и столбцы, содержание — 1 сверху, снизу и по боковым сторонам заданной входной матрицы, а затем поменять каждую +1, которая соседствует с -1, иа — 1, пока рядом с любой -1 не останется ни одной +1. Для печати окончательной схемм на АЦПУ следует использовать следующий метод. Каждый квадратик кроссворда должен отображаться на печатной странице с помощью 5 столбцов н 3 строк, причем зти 15 позиций заполняются следующим образом. Рнс. 19.
Распечатка на АЦПУ кроссворда, показанного нв рис. 18. 1.3.3. Применение к перестановкам В данном разделе мы приведем еще несколько примеров программ для М1Х и наряду г этим познакомимся с некоторыми важными свойствами перестановок. Эти исследования позволят также выявить интересные аспекты компьютерного программирования в целом. Перестановки уже обсуждались в разделе 1.2.5; в нем перестановка сагЬеа рассматривалась как некоторое расположение шести объектов а, Ь, с, д, е, у в ряд. Но возможна и другая точка зрения.
Перестановку можно рассматривать как яередпорядочение или переименование объектов. При такой интерпретации' обычно используют двухстрочную запись, например еду Ьеа Это означает, что ва переходит в с, Ь переходит в д, с переходит в у, д переходит в Ь, е переходит в е, 1 переходит в а".
С точки зрения переупорядочения зто означает, что объект с переходит на место, которое ранее занимал объект а. А если рассматривать зто как переименование, то можно считать, что объект а переименован в с. При использовании двухстрочной записи изменение порядка столбцов в перестановке никакой роли не играет. Например, перестановку (1) можно записать в виде с а 7 Ь а е а также еще 718 способами. В связи с описанной интерпретацией часто используют циклическую запись, Перестановку (1) можно записать н в виде (2) (а с () (Ь д), в В русскоязычной математической литературе в этом случае часто используют термин "иолставовка".
— Прим. перев. Схема, изображенная на рис. 18, будет напечатана, как показано на рис,' 19. Ширины строки принтера — 120 символов— достаточно для того, чтобы печатать кроссворды, содержащие до 23 столбцов. В качестве входных данных должна быть предоставлена матрица размера 23 х 23, состоящая из нулей и единиц, все строки которой перфорируются в столбцах 1-23 входной перфокарты. Например, карта, соответствующая первой строке приведенной выше матрицы, будет перфорирована следующим образом: "10000111111111111111111". Схема кроссворда необязательно будет симметричной, и у нее могут оказаться длинные ленты черных квадратиков, присоединенные к наружным сторонам кроссворда самым экзотическим образом.
+ в в+++++ нн+ н++++н +01 в Ю2 +ОЗ + + + + + + '+нн++++++н++ннм-мм++н++ +Ов + +ннЮБ + +ОВ ++++++ + н++++нн++++++н++н+++н+н+ +07 + +ов + нн++ + + + +++ н+ н+++++ннн++++++++нн++нн + Н++нОВ + +10 + ++нн + в + + нн+нн++нн++и++нн+нвв+ +11 +12 + н++н13 + + + н++++ + + +++++ ннт++++н+++ннн+нв++ +14 + + + + н+ н+++++ н+ н++ н++ что, опять же, означает "а переходит в с, с переходит в у, г' переходит в а, Ь переходит в »1, »1 переходит в Ь".
Цикл (хзхз ... х„) означает "х1 переходит в хз. .., х„ 1 переходит-.р хьч х„ переходит в хз". Так как элемент е является в перестановке фиксированным (т. е. переходит не в какой-либо другой элемент, а в самого себя), он не появляется в циклической записи. Таким образом. единичные циклы типа "(е)" записывать не принято. Если в перестановке фиксированными являются все элементы. так что присутствуют только единичные циклы, то она называется пзождестоенной псресгииноокой и обозначается "()".
Запись перестановки в виде цикла не является единственной. Например, (6 Ы) (о с,(). (с ( а) (6»(), (»1 6) (( а с) и т. д. эквивалентны (2). Но запись "(ау с) (Ьс()" уже не будет им эквивалентна, так как она означает, что а переходит в 1. Легко видеть, почему перестановку всегда можно представить в виде цикла. Начиная с элемента хы перестановка переводит, скажем, хз в хз, хз в хз и т. д., пока наконец (поскольку количество элементов ограничено) мы не придем к некоему элементу х„».ы который уже встречался среди хы..., х„.
Этот элемент х„».з должен быть равен хм Предположим, он равен хз. Но это невозможно, так как известно, что хз переходит в хз, а по предположению в х„эз переходит х„ф х . Поэтому хк.ы = хз и получаем цикл (хз хз . х„), являющийся частью перестановки для некоторого п > 1.
Если этим циклом вся перестановка не исчерпывается. то существует элемент уы такой, что у» ф х, для всех з, для которого аналогичным образом получим еще один цикл (уз уз... у ). Ни один у, не может равняться любому х„так как из х, = у, следует, что хс.ы — — у,».з и т. д, В конце концов для некоторого Й получим хь = уы что противоречит предположению о выборе уь Действуя подобным образом, можно найти все циклы, содержащиеся в перестановке. В программировании эти понятия применяются каждый раз, когда некоторый набор из и объектов нужно расположить в другом порядке.
Чтобы переупорядочить объекты, не перемещая их в какое-либо другое место, необходимо, в сущности, придерживаться циклической структуры. Например, чтобы переупорядочить (1), т. е, присвоить (а. Ь, с, И. е, у) +- (с, »1, )', Ь, е, а), будем следовать циклической структуре (2) и последовательно присваивать 1» — а, ໠— с, с» — (. ~» — й 1+-6, 6» — Ы, »1»-1. Но нужно отдавать себе отчет в том, что любое подобное преобразование можно осуществлять в непересекающихся циклах. Произведения перестановок.
Две перестановки можно перемножить в том смысле, что их произведение означает применение одной перестановки вслед за другой. Например, если за перестановкой (1) следует перестановка аЬсде ( то получим, что а переходит в с, которое затем переходит в с; Ь переходит в й, которое затем переходит в а и т.
дл с й / Ь е а Ь й с а у е а Ь с й е у с й у Ь е а а Ь с й е у (4) Вполне очевидно, что произведение перестановок не обладает свойством коммутативности; другими словами, х, х кз необязательно равно хз х ям где к1 и хз — перестановки. Читатель может убедиться в том, что, если поменять местами сомножители, произведение в (4) даст другой результат (см. упр. 3). Кое-кто перемножает перестановки справа налево, вместо того чтобы делать это более естественным образом слева направо, как показано в (4).
Фактически математики разделились на два лагеря: одни считают, что результат последовательного применения преобразований Т1 и Тз следует обозначать через Т1 Тз, а другие— через ТтТы Здесь мы будем использовать обозначение Т1Тз. Пользуясь циклической записью, запишем равенство (4) следующим образом: (ас() (Ьй) (аЬй) (е() = (асеу Ь). Обратите внимание на то, что знак умножения "х" принято опускать; это не противоречит циклической записи, так как легко видеть, что перестановка (асу)(Ьй) на самом деле является произведением перестановок (асу) и (Ьй). Произведение перестановок можно выполнять непосредственно с помощью циклической записи.
Например, вычислив произведение перестановок (6) (осу д) (Ьсй) (а ей) (у аде)(Ьд ( ае), находим (двигаясь слева направо), что "а переходит в с, с переходит в й, й переходит в а, а переходит в й и й остается без изменений". Таким образом, конечным результатом (6) является то, что а переходит в й, и мы запишем "(а й" в качестве частичного ответа. Теперь выясним, что происходит с й: "й переходит в Ь, которое затем переходит в д"; следовательно, имеем частичный результат "(а йд".
Рассмотрев, что происходит с д, находим, что "д переходит в а, затем в е, в у и в а"; таким образом, первый цикл замыкается: "(айд)". Теперь выберем новый элемент, который еще не встречался, например с. Находим, что с переходит в е, и читатель может проверить, что окончательным ответом для (6) будет "(айд)(се Ь)". А теперь попробуем выполнить эту процедуру с помощью компьютера. Следующий алгоритм формализует описанный выше метод таким образом, чтобы его можно было выполнить с помощью компьютера. Алгоритм А (Перемножение пересгпановок, представленных в виде циклов). Этот алгоритм (рис.
20) берет произведение циклов, такое как (6), и вычисляет получающуюся в результате перестановку в виде произведения непересекающихся циклов. Для простоты здесь не приводится описание процедуры удаления единичных циклов; это было бы лишь незначительным обобщением алгоритма. По мере выпол- Рис. 20. Алгоритм А (неремножение перестановок). пения алгоритма последовательно "помечаем" элементы исходной <)юрмулы, т. е, те символы, которые уже "обработаны".
А1. [Первый проход.] Отметить все левые скобки и заменить все правые скобки помеченной копией входного символа, который следует за соответствующей левой скобкой (см. пример в табл. 1). А2. [Раскрытие скобок.] Выполнив поиск слева направо, найти первый непомеченный элемент входной формулы. (Если все элементы помечены, то работа алгоритма заканчивается.) Установить СТАЕТ равным этому элементу; вывести левую скобку; вывести элемент и пометить его. АЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
