При этом установлены следующие временные интервалы.

Зеленый свет для транспорта на Дель-Мар > 30 с, желтый - 8 с. Зеленый свет Для транспорта на Беркли - 20 с, желтый - 5 с.

Когда в одном направлении для транспорта горит зеленый или желтый сигнал светофора, в другом направлении горит красный свет. Когда транспорту дан зеленый свет, то включен соответствующий сигнал стойте, только перед переключением зеленого света на желтый сигнал стойте мигает в течение 12 с по следующей схеме циклов:

стойте i с1

, > повторяется 8 раз;

Отключен i с J

стойте 4 с (и остается во время циклов желтого и красного света).

Если флаг переполнения включился, когда на Беркли горит зеленый сигнал, то машина или пешеход пройдет в этом же цикле, но если это случилось во время цикла желтого или красного света, то придется ждать следующего цикла, который наступит после того, как проедет поток машин по Дель-Мар.

Пусть единица времени для mix составляет 10 fisec. Напишите полную программу для mix, которая управляет сигналами светофора с помощью гХ, в зависимости от того, что подано на вход флага переполнения. Необходимо неукоснительно придерживаться установленных промежутков времени; исключение может быть сделано только для тех случаев, когда это невозможно. Замечание. Значение в гХ меняется точно в момент завершения выполнения команды ldx или incx.

21. [28] Магический квадрат порядка п - это такое расположение в квадрате чисел от 1 до п, при котором сумма элементов и по вертикали, и по горизонтали равна п(п-fl)/2; такой же результат дает сумма элементов двух главных диагоналей. На рис. 16 показан магический квадрат порядка 7. Для его составления используется следующее правило. Начните с 1, вставив ее в клетку, расположенную прямо под "центральной" клеткой (см. рис. 16), затем двигайтесь вниз и вправо по диагонали (при выходе за границу квадрата представляйте себе, что вся плоскость выложена подобными квадратами), пока не достигнете заполненной клетки; затем опуститесь вниз на две клетки от последней заполненной клетки и продолжайте движение по диагонали вниз и вправо. Этот метод подходит для любого нечетного п.

Используя тот же принцип распределения памяти, что и в упр. 10, напишите полную программу для mix, которая генерирует магический квадрат размера 23 х 23 описанным выше методом и печатает результат. [Этот алгоритм принадлежит Мануэлю Мосхопулосу (Manuel Moschopoulos), который жил в Константинополе приблизительно в 1300 году. Другие многочисленные и не менее интересные методы построения магических квадратов, которые представляют собой хорошие упражнения по программированию, можно найти в книге W. W. Rouse Ball, Mathematical Hecreations and Essays, revised by H. S. M. Coxeter (New York: Macmillan, 1939), Chapter 7.)

22. [31] (Задача Иосифа.) Пусть n человек стоят по кругу. Начиная с некоторой позиции, они ведут отсчет по кругу и предают жестокой казни каждого m-ro человека; после каждой казни круг смыкается. Например (рис. 17), при п = 8 и m = 4 казнить будут в следующем порядке; 54613872. Первого человека казнят пятым, второго - четвертым и т. д. Напишите полную программу для mix, которая распечатывает порядок выполнения казней для п = 24, m = 11. Постарайтесь придумать эффективный алгоритм, который быстро работает при больших пит (однажды это может спасти вам жизнь). [Ссылки. W. Ahrens, Mathematische Unterhaltungen und Spiele 2 (Leipzig; Teubner, 1918), Chapter 15.)

Рис. 16. Магический квадрат. Рис. 17. Задача Иосифа, п = 8, m = 4.

23. [37] Цель этого упражнения - помочь читателю получить опыт применения компьютеров в сфере, где выходные данные должны быть отображены графически, а не в традиционном табличном виде. В данном случае необходимо "нарисовать" схему кроссворда.

Входными данными является матрица, состоящая из нулей и единиц. Нуль соответствует белому квадратику, а единица-черному. В качестве выходных данных нужно получить схему кроссворда, в котором соответствующие квадратики с номерами обозначают слова, расположенные по вертикали и по горизонтали.

Например, для матрицы

Рис. 18. Схема кроссворда, соответствующая матрице из упр. 23.

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

Для печати окончательной схемы на АЦПУ следует использовать следующий метод. Каждый квадратик кроссворда должен отображаться на печатной странице с помощью 5 столбцов и 3 строк, причем эти 15 позиций заполняются следующим образом.

Непронумерованные uuuu+ Номер Ш1 ппии+ Черные

белые квадраты:

белого квадрата: uuuu+

+++++ квадраты: +++++ +++++

+++++ +++++

Квадраты с -1 в зависимости от того, справа или снизу находятся - 1:

t lut it 1+ t it lui 1+ i 11 ii ii ii i

+++++

uuuuu +++++

uuuuu uuuuu uuuu"*"

uuuuu uuuuu uuuuu

Схема, изображенная на рис. 18, будет напечатана, как показано на рис: 19.

Ширины строки принтера - 120 символов - достаточно для того, чтобы печатать кроссворды, содержащие до 23 столбцов. В качестве входных данных должна быть предоставлена матрица размера 23 X 23, состоящая из нулей и единиц, все строки которой перфорируются в столбцах 1-23 входной перфокарты. Например, карта, соответствующая первой строке приведенной выше матрицы, будет перфорирована следующим образом: "10000111111111111111111". Схема кроссворда необязательно будет симметричной, и у нее могут оказаться длинные ленты черных квадратиков, присоединенные к наружным сторонам кроссворда самым экзотическим образом.

+++++++++++++++++++++ +01 + +02 +03 + + + + + + +++++++++++++++++++++++++++++++ +04 + ++++++05 + +06 + + + ++++++ + + + +++++++++++++++++++++++++++++++ +07 + +08 + ++++++ + + + + + ++++++ + +++++++++++++++++++++++++++++++ + ++++++09 + +10 + + + ++++++ + + + + +++++++++++++++++++++++++++++++ +11 +12 + ++++++13 + + + + + ++++++ + +

+14 + + + + + + + + + +++++++++++++++++++++

Рис. 19. Распечатка на АЦПУ кроссворда, показанного на рис. 18.

1.3.3. Применение к перестановкам

В данном разделе мы приведем еще несколько примеров программ для MIX и наряду с этим познакомимся с некоторыми важными свойствами перестановок. Эти исследования позволят также выявить интересные аспекты компьютерного программирования в целом.

Перестановки уже обсуждались в разделе 1.2.5; в нем перестановка cdfbea рассматривалась как некоторое расположение шести объектов а, Ь, с, d, е, f в ряд. Но возможна и другая точка зрения. Перестановку можно рассматривать как переупорядочение или переименование объектов. При такой интерпретации* обычно используют двухстрочную запись, например

а b с d е с d f b в а

Это означает, что "а переходит вс, b переходит в d, с переходит в f, d переходит вЬ, е переходит в е, / переходит в а". С точки зрения переупорядочения это означает, что объект с переходит на место, которое ранее занимал объект а. А если рассматривать это как переименование, то можно считать, что объект а переименован в с. При использовании двухстрочной записи изменение порядка столбцов в перестановке никакой роли не играет. Например, перестановку (1) можно записать в виде

с d f b а J b а d с е)

а также еще 718 способами.

В связи с описанной интерпретацией часто используют циклическую запись. Перестановку (1) можно записать и в виде

{acf){bd),

* В русскоязычной математической литературе в этом случае часто используют термин "подстановка" . - Прим. перев.