Автор: Брудно А.Л. Каплан Л.И.
Теги: вычислительная математика численный анализ математика программирование информатика
Год: 1985
Текст
ВНИМАНИЕ!
Просим внести в текст исправления опечаток
Страница । Строка । Напечатано । Следует читать
3 20 сн. 20—20 дней 10—20 дней
3 16—17 сн. програмированию программированию
3 7 сн. потепенной постепенной
4 6 сн. вычисительных вычислительных
41 15 сн. N.LT К N.LT.K
43 13 сн. вычислен вычислен
53 10 св. JEQ.1 J.EQ.1
53 22 св. A(I,J) A(I,J) = К
56 21 св. DO 4 I- DO 4 I = 6,Ml
64 12 сн. X\i]:=X[i] + 1 X[<] :=%[/] 4-1;
65 2 сн. VSJO VSJO:
71 5 св. Z[j]] z[jl
75 4 св. [F\E\) (Fl,El)
81 16 сн. убвания убывания
85 14 сн. 6 * k.-т- 10 **44-/. 6 * kp-10 ** 44-1.
86 2 сн. гадалда гадалка
А. Л. БРУДНО, Л. И. КАПЛАН
ОЛИМПИАДЫ
ПО ПРОГРАММИРОВАНИЮ
ДЛЯ школьников
„ Под редакцией
академика Б, Ht Наумова
МОСКВА «НАУКА* '
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1985
ББК 22.18
Б 89
УДК 519.6
Брудно А. Л., Каплан Л. И. Олимпиады по программирова-
нию для школьников/Под ред. Б. Н. Наумова.—М.: Наука. Главная
редакция физико-математической литературы, 1985.— 96 с.
В книге приведены все задачи, предложенные школьникам на
олимпиадах по программированию в 1980—84 г. (в Учебно-производ-
ственном центре вычислительной техники Октябрьского района
г. Москвы), а также алгоритмы решения’этих задач и программы на
алголе и фортране. Специальные параграфы посвящены программи-
рованию перебора и занимательным задачам кибернетики.
Кроме того, книга содержит сведения об организации этих олим-
пиад, обучении программированию на базе шефского предприятия
и перспективам обучения в дисплейном классе.
Рецензент
кандидат физико-математических наук И. Г» Фараджев
Александр Львович Брудно, Лев Исаакович Каплан
ОЛИМПИАДЫ ПО ПРОГРАММИРОВАНИЮ для школьников
Редактор Л. Г. Силкова
Техн, редактор С. Я. Шкляр Корректоры В. П. Сорокина, И. А. Шагас
ИБ № 12722
Сдано в набор 10.09.84. Подписано к печати 12.03.85. Т-07531. Формат 84хЮ8,/з2.1
Бумага тип. Xs 2. Гарнитура литературная. Высокая печать. Усл. печ. л. 5.04.;
Усл. кр.-отт. 5,25. Уч.-изд. л. 4,87, Тираж 220 000 экз. Заказ № 302. Цена 15 коп.
Ордена Трудового Красного Знамени издательство «Наука»
Главная редакция физико-математической литературы
117071 Москва В-71, Ленинский проспект, 15
Набрано в Ленинградской типографии Xs 2 головного предприятия ордена Тру-
дового Красного Знамени Ленинградского объединения «Техническая книга»
нм. Евгении Соколовой Союзполиграфпрома при Государственном Комитете
СССР по делам издательств, полиграфии и книжной торговли. 198052 Ленин-
град Л-52, Измайловский проспект, 29.
Отпечатано с матриц во 2-й типографии изд-ва «Наука»
121099 Москва Г-99, Шубинский пер., 6
Зак. Хе 1673
1702070000—051 г
Б 053(02)^85 45'85
© Издательство «Наука», .
Главная редакция
физико-математической
литературы, 1985
ПРЕДИСЛОВИЕ АВТОРОВ
В 1972 году в Октябрьском районе г. Москвы был
открыт Учебно-производственный центр вычислитель-
ной техники (УПЦ-ВТ) на базе Института электронных
управляющих машин (ИНЭУМ) Министерства приборо-
строения. В Центре занимаются ученики девятых и деся- _
тых классов близлежащих школ (по одному дню в не-
делю) . От трети до половины учащихся специализируют-.
ся по программированию и получают квалификацию про-
граммист-лаборант.
Начиная с 1980 года один раз в год в этом Центре
проводятся олимпиады по программированию. В них
могут участвовать все ученики Центра, и всегда уча-.
ствуют в организованном порядке учащиеся других
школ Москвы. Число участников колеблется от 100 до
300. Школьники получают задания и пишут программы
на любых языках программирования. Через 20—20 дней
проводится итоговая конференция с разбором задач и
демонстрацией хороших решений. Кроме того, на кон-
ференции некоторые ученики делают доклады по про- ’
гримированию. В заключение объявляются и награж-
даются Победители олимпиады.
В Ьтой книге приведены все задачи пяти олимпиад
• 1980—1984 годов, алгоритмы их решений и программы
с решениями на алголе и фортране. Задачи сформулиро-
ваны с теми дополнительными условиями и в том по-
; |рядке, как они предлагались на олимпиадах. Алгоритмы
; решений мы приводим главным образом для того, чтобы
облегчить разбор программ. Для отдельных задач изла-
гаются различные способы решения, с потепенной «до-
водкой» программы. Указываются распространенные
ошибки.
Алгольные программы ближе к алгоритмам решений
на «человеческих» языках и по существу, и по графи-
ческому оформлению. Поэтому они компактнее н легче
читаются. Фортрацные программы длиннее. Но фортран
- - - —• 5
шире распространен. Поэтому мы приводим решения
па обоих языках. Языки более высокого уровня в на-'
ших небольших задачах дают мало преимуществ, а за-
мечательно краткий язык си пока мало распространен.
Да и написанное на нем читается с большим трудом.
Отдельный параграф посвящен построению програм-
мы перебора. Она лежит в основе всех программ «ис-
кусственного интеллекта» и не сводится к циклам язы-
ков программирования.
Два параграфа посвящены описанию учебного про-
цесса в Центре и перспективам преподавания с исполь-
зованием более современного оборудования, когда уче-
ник работает с дисплеем (индивидуальным телевизион-
ным пультом). Часть классов нашего Центра уже пере-
- шла на это оборудование.
Мы получили возможность написать эту книгу бла-
годаря сотрудникам Центра и Института, принимавшим
участие в работе Центра — от его организации и обуче-
ния школьников до ежегодных проверок олимпиадных
работ. Всем этим лицам мы, естественно, благодарны.
Воспользуемся случаем перечислить тех, кто внес боль-
ший вклад в наши олимпиады. Это — директор Институ-
та Б. Н. Наумов, обеспечивший Центр вычислительной
техникой и квалифицированными преподавателями; ди-
ректор Центра В. Д. Горский, по инициативе которого
были начаты эти олимпиады. В 1984 году директором
МНЭУМ стал Н. Л. Прохоров, а директором Центра —
]Т. П. Кравчук, которые активно продолжили руководство
Центром. Кроме того, Институт проблем информатики
(АН СССР, который возглавил Б. Н. Наумов, стал вто-
рым базовым предприятием Центра; для этого образова-
на лаборатория (заведующий — А. В. Гиглавый). Далее,
нам приятно назвать М, К. Антонову — сотрудницу Ин-
ститута, все эти годы преподававшую программирование.
Ее квалификация сделала ее ведущим преподавателем, на
уроки которого ходят другие учителя, а педагогический
талант вызывает у учеников энтузиазм в программирова-
нии. Благодарны мы также П. Ш. Янкелевичу, началь-
нику отдела вычисительных работ, где каждую неделю
выполняются программы школьников. Специальную бла-
годарность вызывает машинистка Н. А. Реброва, печа-
тавшая рукопись с карандаша.
Параграфы 1 и 2 написаны нами совместно, пара-
граф 4 — Л. И. .Капланом, остальные — А. Л. Брудно^
§ 1. ОЛИМПИАДНЫЕ ЗАДАЧИ
На пяти олимпиадах 1980—1984 гг. школьникам пред-
лагались наборы из некоторого количества задач для
программирования. Число задач было в разные годы
разным, от 5 до 11. Но задачи всегда были различной
ценности, шли в порядке убывания трудности, и в зачет
принимались только три лучших решения. Участники
олимпиад обо всем этом предупреждались. Первые по
порядку задачи могли быть довольно трудны, а послед-
ние носили явно «утешительный» характер. На олим-
пиаду отводилось 4 часа. Решения можно было писать
на любых языках программирования. Ошибки и описки
в программе снижали ее оценку, а эффективность алго-
ритма и экономность программы повышали ее.
ОЛИМПИАДА 80 *
Участникам было предложено одиннадцать задач,
разбитых на 3 группы. Группы располагались в порядке
убывания трудности, внутри одной группы задачи счита-
лись равноценными. Из каждой группы в зачет шло не
более одной задачи.
80.1.% . Напечатать все простые числа, не превосхо-
дящие заданное число М.
80.1.2. Задан массив А(А1) из М попарно различных
целых чисел. Напечатать все перестановки этих чисел.
80.1.3. Ввести вещественное число А и натуральное k.
Вычислить и напечатать Ак с выполнением следующих
условий: операцией возведения в степень пользоваться
нельзя; k может оказаться настолько большим, что не-
допустимо выполнять k умножений.
80.1.4. В написанном выражении ((((1 ?2) ?3) ?4) ?5) ?6
вместо каждого знака ? вставить знак одной из четы-
рех арифметических операций +, —, X» /. так> чтобы
5
результат вычислений равнялся 35 (при делении дроб-
ная часть в частном отбрасывается). Достаточно найти
одно решение.
80.2.1. Дан двумерный целочисленный массив
Л (2,15). Известно, что среди его элементов два и толь-
ко два равны между собой. Напечатать их индексы.
80.2.2. Можно ли заданное натуральное число М
представить в виде суммы двух квадратов натуральных
чисел? Написать программу решения этой задачи.
80.2.3. Даны натуральное число М и целочисленный
массив Л(Л1). Сосчитать и напечатать, сколько различ-
ных чисел в этом массиве. Например, в массиве 5, 7,
5 различных чисел два (5 и 7).
80.3.1. Составить программу вывода всех трехзнач-
ных десятичных чисел, сумма цифр которых равна дан-
ному целому числу.
80.3.2. Целое неотрицательное число М задано мас-
сивом своих двоичных цифр ао, ai, .... a„_i:
М = an_12"~1 + ал-22л_2 + ... + ^12 + «о,
где at = O или az=l (i = 0, ..., n— 1). Напечатать
массив двоичных цифр числа М + 1.
80.3.3. В массиве Х(М, N) все числа различны.
В каждой строке выбирается минимальный элемент, за-
тем среди этих чисел выбирается максимальное. Напе-
чатать номер строки массива X, в которой расположено
выбранное число.
80.3.4. В массиве X(N) каждый элемент равен 0, Г
или 2. Переставить элементы массива так, чтобы снача-
ла располагались все нули, затем все единицы и, нако-
нец, все двойки (дополнительного массива не заводить).
ОЛИМПИАДА 81
Участникам было предложено пять задач, располо-
женных в порядке убывания трудности. В оценку шли
только, три задачи.
81.1. Функция f(n) для целых неотрицательных п
определена так:
f(0)=0, f(l)=l,
f(2n)=f(n), f(2«+l)=f(n)+f(n+l).
Для данного W найти и напечатать f(N). Обязательное
условие: N столь велико, что недопустимо заводить
6
массив'из W чисел (равно как и массив, длина которого
растет с ростом числа N).
81.2. Найти минимальное число,
ется суммой четырех квадратов
натуральных чисел не единствен-
ным образом.
81.3. Ввести число п и запол-
нить двумерный массив размером
п X п натуральными числами от
1 до п2 по спирали (рис. 1.1).
81.4. Напечатать все четырех-
значные натуральные числа, в де-
сятичной записи которых нет двух
одинаковых цифр. Обобщить эту
которое представля-
задачу на n-значные числа.
81.5. Заданы число N и целочисленный массив A(N).
Найти длину самой длинной последовательности подряд
идущих элементов массива, равных нулю.
Рис. 1.2
ОЛИМПИАДА 82
Участникам было предложено шесть задач, идущих
в порядке убывания трудности. В оценку шли только
три задачи.
82.1. На квадратном клетчатом листе бумаги (раз-
мера 100ХЮ0 клеток) нарисовано несколько прямо-
угольников. Каждый прямоугольник состоит из целых
клеток, различные прямо-
угольники не накладывают-
ся друг на друга и не сопри-
касаются (см. пример на
рис. 1.2).
Задан массив размером
100 X 100, в котором элемент
0,7=1, если клетка (/,/)_
принадлежит какому-либо
прямоугольнику, и ац = 0
в противном случае. Напи-
сать программу, которая со-
считает и напечатает число
пря моугол ьников.
82.2. Напечатать в по-
рядке возрастания все про-
стые несократимые дроби, заключенные между 0 и 1,
знаменатели которых не превышают 7.
7
82.3. Даны целочисленный массив А (Л7) и > число М.
Найти такое множество элементов Д(й), A(i2), •••
Л(»л) (l^n< ... что Д(ii)+4(i2)+ ...
... 4-Д (ik) ~М. Предполагается, что такое множество
заведомо существует.
82.4. Дан одномерный массив. Все его элементы, не
равные нулю, переписать (сохраняя их порядок) в на-
чало массива, а нулевые элементы — в конец массива
,(новый массив не заводить).
82.5. Даны числа М, N и двумерный массив размером
M~XN. Некоторый элемент этого массива назовем сед-
ловой точкой, если он является одновременно наимень-
шим в своей строке и наибольшим в своем столбце. На-
печатать номера строки и столбца какой-нибудь седло-
вой точки и напечатать число 0, если такой точки нет.
82.6. Даны числа N, К и два целочисленных массива
X(N) и У (К). Можно ли в первом из них выбрать та-
кие К. идущих подряд элементов Хг+],Х;+2, ... ,' Xi+k,
чтобы Х(+1=У1, Х(+2=У2, ..., Xi+k=Yk? Написать про-
грамму, которая решает эту задачу и печатает ответ
ДА или НЕТ.
ОЛИМПИАДА 83
Участникам было предложено пять задач, следующих
в порядке убывания трудности. В оценку шли только
три задачи.
83.1. Бит-реверс. Целое положительное число М
записывается в двоичной, системе счисления и разряды
(в этой записи) переставляются в обратном порядке.
Получившееся число принимается за значение функ-
ции В(М). Напечатать значения В(М) для А4=512, 513,
514, ..., 1023.
Вот, для ясности, Цйчало этой распечатки: 1, 513,
257, ...
83.2. Треугольник и точка. Заданы .прямоуголь-
ные координаты х>,уг, х2,у2\ х3,уз вершин треугольника
и координаты х, у точки. Определить и напечатать, на-
ходится ли точка в треугольнике. Погрешностями вычис-
лений пренебречь.
83.3. Лабиринт. Может ли путник выйти из лаби-
ринта? Если может, то напечатать путь о.т выхода до
начального положения путника.
Лабиринт задан массивом А размером 40X40, в ко-
тором:
8
Лкм=О, если клетка (К, М) «проходима»;
Акм=1, если клетка (К, М). «не проходима».
Начальное положение путника задается в проходи-
мой клетке (/, J). Путник может перемещаться из одной
проходимой клетки в другую,, если они имеют общую
сторону. Путник выходит из лабиринта, когда попадает
в граничную клетку (то есть клетку (К,М), где К. илиЛ1
равны 1 или 40).
83.4. Пила. Задан массив X (М). Найти длину К
самой длинной «пилообразной (зубьями вверх)» после-
довательности идущих подряд чисел:
Xp+1<Zp+2>Xp+3< ••• >Xp+k.
83.5. Сократить дробь. Даны натуральные чис-
ла М и N. Найти такие'натуральные числа ЛИ и ЛИ, не
имеющие общих делителей, что Ml/N\ = M/N.
ОЛИМПИАДА 84
Участникам было предложено семь задач, следую-
щих в порядке убывания трудности. В оценку шли
только три-задачи.
84.1. Инверсия. Пусть P=(pi, .... ря) является
перестановкой чисел 1,2, ..., п. Таблицей инверсий пе-
рестановки Р называют последовательность ...
..., tn), в которой it равно числу элементов переста-
новки Р, стоящих (в Р) левее числа i и больших чи-
сла I. Например, для перестановки Р=(5, 9, 1,8, 2, 6, 4,
7, 3) чисел (1,2, .... 9) таблица инверсий будет Т =
= (2, 3, 6, 4, 0, 2, 2, 1, 0):
Написать программу, которая по заданной таблице
инверсий восстанавливает перестановку.
84.2. Дорога. Даны натуральные числа Л^2 и М
п ' вещественный массив А(М, M,N—1). Найти мини-
мальное значение суммы.
Р=Л (ii, г2, 1) -f-Л (i2,1’з> 2) + ... +Л (tN-i, In, N—1)
для всевозможных наборов целых чисел 1^ 1’1,12,...
D.S,
Пояснение. Числа М, N — величины порядка не-
скольких десятков. Поэтому неприемлемо решение с
числом действий порядка MN.
84.3. Совершенные числа. Натуральное число
называется совершенным, если оно равно сумме всех
9
своих собственных делителей, включая 1. Напечатать
все совершенные числа, меньшие, чем заданное М.
84.4. Период дроби. Ввести натуральные числа
М и N и напечатать период десятичной дроби M/N.
Например, для дроби 1/7 периодом будет (142857),
а если дробь конечная, то ее период состоит из одной
цифры 0.
84.5. Слияние массивов. Даны два числа М,N
и два упорядоченных массива Я1^я2^ ... и
... ^bN. Образовать из этих элементов упо-
рядоченный массив ••• ^См+н.
Указание: обратить внимание на число действий
программы при больших М и N.
84.6. Календарь. Заданы три числа А, В, С, ко-
торые обозначают число, месяц и год. Найти номер N
этого дня с начала года.
Указание: високосные годы — это те, у которых
номер делится на 400, и те, у которых номер делится
на 4, но не делится на 100.
84.7. Квадратики. Дан массив А(М,М), каждый
элемент которого равен 0, 1, 5 или 11. Подсчитать в нем
количество четверок A(i, j), A (i-j-l,/), A(i, /4-1),
^(t’4-1,/4-1), в каждой из которых все элементы раз-
личны.
§ 2. АЛГОРИТМЫ РЕШЕНИИ
В этом параграфе приводятся алгоритмы решений.
Иногда это будет законченное рассуждение, которое
остается переписать на языке программирования, ино-
гда лишь идея решения, а иногда комментарий, пояс-
няющий программу. Но во всех случаях мы стремились
облегчить чтение программы, изложить прием програМ"
мирования, которым стоит овладеть, и готовы были
ограничиться этим. Число действий мы, как правило,
указываем с точностью до постоянного множителя.
ОЛИМПИАДА 80
80.1.1. Чтобы ускорить вычисления, полезно завести
таблицу для уже найденных простых чисел и проверять
делимость очередного кандидата только на числа из
этой таблицы. Четные числа, естественно, не рассмат«
ривать.
10
Таблица понадобится менее чем на <\/М /2 чисел. По-
этому таблицы на 1000 чисел хватит для печати простых
чисел до 4 000 000.
Алгоритм и программу можно улучшить так, чтобы
не рассматривались числа i, кратные числу 3.
80.1.2. Специфика этой задачи в том, что нужно по-
лучить все перестановки. Это отличает ее от общей
задачи перебора и значительно облегчает решение.
И все же его описание длиннее программы.
Представим себе все перестановки чисел 1,2, .... т.
Упорядочим их (мысленно) в словарном порядке и на-
учимся (в действительности) по заданной перестановке
строить непосредственно следующую. И тогда, отправ-
ляясь от первой перестановки (1,2, ..., т), мы после-
довательно построим все перестановки этих чисел. По-
путно для каждой перестановки P=(pi,p2, •••> Рт) чи-
сел 1,2, ..., т напечатаем такую же перестановку
(А(Р1), ..., А(рт)) заданных чисел А.
Чтобы по данной перестановке P=(pi,p2...........рт)
чисел 1,2, ..., т построить непосредственно следую-
щую, мы будем просматривать числа pi,p2, •••, рт с
конца. И остановимся, когда впервые попадется член р„
меньший стоящего правее него (pi<Zpt+i). Если такого
члена нет, то перестановка Р имеет вид (т, т—1, ..., 1),
то есть является последней. Ясно, что члены
>рг+2> ... >рт образуют убывающую последова-
тельность. Найдем среди них первый (если их рассмат-
ривать с конца) член р/, уже больший чем р,, и поме-
няем их местами.
Остается переставить члены p,+i,pt+2, рт в по-
рядке возрастания, и искомая перестановка (назовем ее
Q=(?b Чт)) будет получена (рис. 2.1).
Действительно, Р < Q, ибо первые i — 1 членов у них совпа-
дают, a pi< qi (так как по самому выбору члена qi = Pi>pi).
Далее, при своих заданных первых i членах Р является максималь-
ной, a Q — минимальной перестановками, ибо в Р остальные члены
идут в убывающем порядке, а в Q — в возрастающем. Наконец,
если перестановка R лежит между Р и Q, то первые i—1 членов
У нее совпадают с первыми членами Р и Q, а член ri равен pi или
q,, так как при уже занятых первых i — 1 членах нет чисел, распо-
ложенных между pi и qi. Если р, = г, и Р R, то Р = R (так как
Р максимальна при заданных pi, р2.р>), а если О = ?<> т0 ана-
логично R = Q.
В программе это реализовано так. Мы заводим мас-
сив Р. для текущей перестановки, заполняем его первой
перестановкой Р=(1,2, ..., т) и печатаем (в разделе
11
перестановка Р
О перестановка Q
Рис. 2.1
80.1.3. При обычном
с меткой Т) соответствующую перестановку членов за-
данного массива А. Пусть очередная перестановка Р по-
лучена и соответствующая ей перестановка А отпеча-
тана. В разделе с меткой Q отыскивается элемент
pi<.pi+i с максимальным номером i. Если его нет, то
перестановка Р была последней. Иначе в разделе Р
ищется наибольший но-
мер / > I, для которого /
Pi < pf. В разделе S эле-
менты pi и pj перестав-
ляются, после чего в по-
следовательности pi+i,
Pi+2, Pm порядок ме-
няется на обратный: для
этого меняют местами p»+i
и рт, затем р/+2 и pm-i
и т. д.
На этом заканчивает-
- ся получение следующей
; перестановки,и в разделе
*• Т печатается соответст-
вующая перестановка
массива А.
На фортране вместо
меток Т, Q, Р, S исполь-
зуются метки 8, 2, 4, 6.
[ислении ak заводят пере-
менную Ь, вначале равную единице, и многократно вы-
полняют операторы:
k'.—k—1; b:—b*a
Когда переменная k станет равной нулю (это потребует
k циклов), b станет равно искомой величине а*.
Идея сокращения вычислений в следующем. Вначале
положим &:=1. Если k нечетно, по-прежнему выполняем
операторы
k:—k—1; b-.=b*a
Но если k четно, то, воспользовавшись тождеством
а*=(а2)*/2>
сделаем замены:
&:=fe/2; a-.—ata
Теперь, когда переменная k, наконец, станет равной
нулю, переменная b станет равна искомой величине.
12
Для доказательства обозначим искомую величину ak через w и
положим b : — 1. Тогда
ak*b = w. (*)
Если k нечетно, то, выполнив замены
k : — k — 1; b := b * а
мы не нарушим равенства («). Если же k четно, то замены
k Z?/2; а :== а * а
тоже его не нарушают. Когда k станет равным нулю, то равенство
(*) перейдет в равенство
а° * Ь, = ш, то есть b = ш,
п, значит, b будет равно искомой величине.
80.1.4. Эта задача — тоже на образование всех пе-
рестановок, только с повторениями. Запишем заданное
выражение в виде
w— ((((1 аг2) йзЗ) а$) as5) а6в.
Здесь элементы массива а [2:6] изображают знаки
арифметических действий. Условимся, что знаки +, —,
», -г- изображаются значениями 1, 2, 3, 4.
Поскольку вариантов может оказаться много (4s >]
|>1000), постараемся организовать вычисления эко-
номно. Для этого, вычисляя w, будем запоминать про-
межуточные результаты в элементах массива В [116],
полагая
Bi'. = 1; В2'. = В1Ог2; ... j Be'. = BeCieQ
и w—Be. Далее, перебирая варианты, будем сначала
менять йв=1, 2, 3, 4. При каждом таком изменении
пересчитывать понадобится лишь Be. Потом увеличим
а$:—ае+1, пересчитаем Be и снова рассмотрим ае— >
1= 1; 2, 3, 4 и т. д. q
Этот алгоритм и реализован в программе 80.1.4. Да-'
дим к ней некоторые пояснения. Переменными тип
обозначены числа 35 и 6. Первые строки программы (до
метки 7?) сначала лучше пропустить. Они подготавли-
вают такое «доначальное» положение, чтобы операторы,
начинающиеся с метки R и рассчитанные на выработку,
«очередного» варианта, сначала образовали первый ва-;
риант.
Рассмотрим программу, начиная с метки R. Здесь1
отыскивается первый член сц в последовательности
an,an-i, .... аг, не равный 4. Он увеличивается на 1,
а все предыдущие полагаются равными 1. Теперь вы-
13
числяется Bi по Bf_i, а затем псе остальные члены:
В(+1,Вг+2, Вп. Последнее несложно, так как соот-
ветствующие а/ равны 1, то есть обозначают сложение.
Если Вп=£т, то значение w оказалось не заданным и
программа переходит на метку R для рассмотрения
следующего варианта. Если же Вп—т, то программа
также переходит на R, но предварительно печатает най-
денный вариант.
В программе на фортране обозначения несколько
отличаются.
80.2.1. Для удовлетворительного решения этой за-
дачи надо не брать для сравнения одну и ту же пару
элементов (A [i, /], А [р, </]) дважды и не запутаться в
случаях, когда i=p и j—q.
В программе на фортране эти трудности обходятся
переходом к одномерному массиву с помощью опера-
тора EQUIVALENCE.
80.2.2. Программа читается просто.
80.2.3. Программа читается просто. Но ее можно
ускорить, сравнивая испытуемый элемент не с предше-
ствующими, а с последующими, до первого повторения.
От этого число сравнений упадет с т*т до m*k, где
т — число всех чисел, a k — число различных чисел в
заданном массиве. Это сделано в программе 80.2.3—2.
80.3.1. Можно, разумеется, написать тройной цикл
по цифрам искомого числа:
по I от 0 до 9, по j от 0 до 9, по k от 1 до 9.
В нем подсчитать сумму i-f-f+fe и, если она окажется
равной заданному числу, напечатать трехзначное число:
М=г4-10/4-100^.
Но это плохое p-ешение. В нем 900 циклов вместо' воз-
можных 100.
11риемлемое решение содержит двойной цикл по I
и по /, a k вычисляется по заданной сумме п:
k:=n—i—j
Добавив проверку 1^/г^9, мы придем к програм-
ме 80.3.1.
Читатель может усовершенствовать программу, на-
чав ее с проверки условия п^27 и введя другие уско-
рения счета в случае п<_18.
80.3.2. Будем просматривать числа «о, «1.заме-
няя единицы на нули, до первого нуля — его заменим
14
единицей и на этом прекратим замену чисел. Надо
только учесть, что ответ может содержать п+1 чисел,
а не п, как в условии.
80.3.3. Программа 80.3.3 читается достаточно просто.
Но в ней отдельно рассматривается первая строка и
каждый первый элемент строки^ Да и обработка оче-
редной строки продолжается до конца, даже если она
уже стала не нужна.
Программа 80.3.3—2 свободна от этих недостатков.
80.3.4. При решении этой задачи ничего не нужно
переставлять. Нужно сосчитать, сколько в массиве ну-
лей, единиц и двоек, и заполнить массив требуемым
образом.
ОЛИМПИАДА 81
81.1. Задача может показаться неразрешимой, по-
скольку формулу для f(n) угадать трудно, а на каждом
шаге уменьшения аргумента п число функций, подле-
жащих рассмотрению; как будто увеличивается. Дей-
ствительно, отправляясь от одной функции f(2n+l), мы
получим две функции:
f(2n+l)=f(n)+f(n+l).
Из двух аргументов п и п+1 один нечетный. На сле-
дующем шаге он породит две функции и т. д. Однако,
выполнив этот второй шаг, мы замечаем, что функций
остается по-прежнему две (а не три) и всегда будет
оставаться две.
Для доказательства этого обстоятельства — попутно
дающего программу — наряду с заданной функцией
f (п) одного аргумента п введем функцию
g (п, i, j) =if (n) + jf («+1)
трех аргументов n, /, /. Для нее легко проверяются ре-
куррентные формулы:
g(2n, i, j) = g(n, i + j, j),
g (2n + 1, i, j) = g (n, i, i + /).
Теперь искомое значение f(n) можно записать в виде
f.(n}=g(n, 1,0),
7s
а многократным применением рекуррентных формул сде-
лать первый аргумент функции g равным нулю и по-
лучить
f(n)=g(n, 1,0)= ... =g(O,i,/)=j.
Остается выполнить формальности, требуемые языком,
на котором пишется программа.
81.2. Эта задача содержит небольшую ловушку, так
как вместо минимального числа с нужными свойствами
можно получить первое число, которое встретится при
определенной организации перебора слагаемых. Работу
программы, приведенной на алголе, читатель может
ускорить, заметив, что у искомого числа два представ-
ления (в виде суммы квадратов) должны отличаться
наибольшим слагаемым. Это учтено в программе на фор-
тране.
81.3. Обозначим через р=1,2, ... номер витка спи-
рали и разделим виток на четыре прямолинейных участ-
ка: горизонтальный слева направо, вертикальный сверху
вниз, горизонтальный справа налево и вертикальный
снизу вверх. Если написать внешний цикл по р и по от-
дельному циклу для каждого прямолинейного участка,
то получится примерно программа 81.3. Нужно только
обязательно проверить, что она останется верной для
матрицы первого порядка (п=1) и что при нечетном
порядке (достаточно рассмотреть п=3) не будет про-
пущена центральная клетка.
Та же программа, но без циклов и использующая
«скатывание» одного участка на другой, приведена в
81.3—2. Здесь окончание проверяется по занесению по-
следнего числа k=n*n.
81.4. Программа 81.4 достаточно ясна. Программа
81.4—2 работает быстрее, но тоже легко читается.
Программа на фортране загружена из-за отсутствия
удобных операторов печати (читатель может найти в
литературе сколько угодно противоположных утвержде-
ний) без перехода на новую строку.
Что касается обобщения на «-значные числа, то нам
будет удобнее рассмотреть его в § 5.
81.5. Программа 81.5 проста, а 81.5—2 заканчивает
вычисления, когда не имеет шансов набрать последова-
тельность нулей более длинную, чем уже встретив-
шиеся. Выгоды от этого немного.
16
ОЛИМПИАДА 82
(
82.1. Эта задача решается в «одно соображение»:
прямоугольников столько, сколько их северо-западных
углов (иначе говоря — верхних левых). Остается только
не запутаться в случае, когда угол стоит у границы.
Так, например, выражение 1>1&Д[г—1,/]=0 окажется
синтаксической ошибкой при 1—1, если массив А начи-
нается с индекса t=l. По-разному это затруднение пре-
одолевается в программах 82.1 и 82.1—2.
82.2. Дроби будем располагать в порядке возраста-
ния, занося их числители и знаменатели в два массива.
Каждую новую дробь будем сравнивать с уже имеющи-
мися. Стоит заметить, что сравнивать лучше не частные
(которые представляются в машине приближенно), а
произведения:'
не m/n^p/q, но m*q^n*p.
Но можно обойтись и без вспомогательного массива
(см. программу 82.2—2). Для этого заведем и отпеча-
таем дробь т/п для zn=0, п=1. Теперь среди всех
дробей а/b, больших, чем т/п, и таких, что b Р (по
условию Р=7), выберем минимальную. Пусть это бу-
дет i/j. Если окажется, что то заменим дробь
т/п дробью i/j и продолжим процесс.
Кстати, для заданного знаменателя Ь=2,3, ... чис-
литель а не подбирается, а вычисляется по формуле
а\ — т*Ь 4- «4-1
Можно заметить, что в алгольной програм-
ме 82.2—2 не печатается граничная дробь 1/1 = 1.
82.3. Это — задача на перечисление всех подмно-
жеств. Внешне она похожа на перебор вариантов, но
гораздо проще него. Пусть b — натуральное число, и
bi~ его двоичные разряды (bi—Q или Ь<=1):
b = Ь\ 4- 2&2 + ... 4- 2п~'Ьп.
Когда Ь пробегает последовательность значений Ь=
= 1,2, ...» 2”—1, то наборы индексов i элементов
равных единице, пробегают все (не пустые) подмноже-
ства множества {1,2, ..., п}. Поэтому в программе за-
веден массив В, с элементами которого мы обращаемся
как с двоичными разрядами числа Ь.
82.4. Задача легко решается с использованием двух
Циклов: первый переписывает ненулевые элементы в
17,
начало массива, а второй заполняет остаток нулями.
Так это и сделано на фортране. Но можно эти циклы
и совместить, как это сделано на алголе.
82.5. Если mi — минимум элементов ац в строке г,
a Mj— максимум элементов ац в столбце /, то
тл^.ац^.М].
Это позволяет сделать несколько замечаний:
а) минимум в любой строке не более максимума
в любом столбце, то есть всегда
mi^Mj;
б) если для каких-нибудь i и j будет выполнено ра-
венство mi—Mj, то максимальный минимум совпадает
с минимальным максимумом, а на пересечении строки i
со столбцом j будет стоять седловая точка:
mi = ац = Mj', (*)]
в) если точка ац седловая, то для нее выполня-
ется (*), и, следовательно, максимальный минимум ра-
вен минимальному максимуму.
Остается реализовать это в программе. В каждой
строке мы ищем минимум mi, среди этих минимумов
выбираем максимум Ма. и запоминаем строку iO, где
он находится. Поиск минимума в строке следует прекра-
щать, если ясно, что он заведомо окажется меньше те-
кущего значения Ма.
Затем ищется столбец, в котором максимальный эле-
мент равен найденному значению Ма; если такого, столб-
ца нет, то нет и седловой точки. Фактически в про-
грамме мы пользуемся тем, что если в столбце нет эле-
ментов, больших Ма, то столбец будет искомым в силу
пункта а).
Следует заметить, что программа, не использующая
изложенных здесь соображений, работала бы не намного
медленнее.
82.6. Программа читается просто.
ОЛИМПИАДА 83
83.1. Бит-.реверс. Выпишем, для ясности, несколь-
ко значений т и В (т) в десятичной и двоичной систе-
мах счисления.
Заметим, что старший двоичный разряд числа т
изображает величину 512 и ему соответствует тиладший
Л8
Система . 10 2 2 1Э
512 1000000000 0000000001 1
513 1000000001 1000000001 513
Значения т и В (т) 514 1000000010 0100000001 257
515 1000000011 1100000001 769
516 1000000100 0010000001 129
1023 1111111111 . 1111111111 1023
разряд числа В (/и), изображающий величину 1. Для
следующих разрядов это будут величины 256 и 2 и т. д.
Единица старшего разряда у числа т всегда есть, так
как т^512. Удалим ее, заменив т на т—512, и зане-
сем единицу в число В(т). В следующем разряде еди-
ница у числа т будет, если новое значение т^256.
Если она есть, удалим ее и добавим к В(т) число 2.
Проверим наличие следующей единицы и т. д. Это при-
ведет к программе 83.1, нужно только прекратить ра-
боту при обнулении числа т. ;
Предыдущая программа тратит на свои вычисления
512X10 циклов. Быстрее будет работать программа, ко-
торая по числу В(т) строит число Глядя на
двоичную запись значений В(т), можно сообразить^ что
при построении B(m-f-l) нужно двигаться по двоичной
записи числа В(т) слева направо, заменяя единицы
нулями (то есть вычитая из В(т) числа 512, 256, ...),
-до первого нуля — его нужно заменить единицей, и число
'ТЗ(т-Н) будет получено. Эта программа истратит на
:вычисление половины чисел по одному циклу, на вычис-
ление четверти — по два цикла, одной восьмой — по три
и т. д. Всего уйдет менее 512X2 циклов. Так и построена
программа 83.1—2. ,
83.2. Треугольник иточка. Заметим следующее,
Пусть точка (х, у) лежит на прямой L, проходящей че-
рез точки (х1,«/1) и (х2, у2). Тогда из подобия треуголь-
ников получаем
‘ у — у1 у2 —у1
х — х\ х2 — xl
Обходя ловушку, связанную с делением на число
х—xl, которое может оказаться нулем, перепишем это
уравйёйие в виде
Р(х, у) =s (х—xl) (у2—1/1).— (х2—xl)। у\) =0.
19
Теперь ясно, что выражение F обращается в нуль тогда
и только тогда, когда точка (х, у) лежит на прямой L;
оно имеет различные знаки для точек (х, у) ', лежащих
по разные стороны прямой L. Следовательно, величина
vne=F(х, у) *F (хЗ, уЗ)
будет меньше нуля, когда точки (х, у) и (хЗ, уЗ) лежат
по разные стороны прямой ((xl,у\), (х2,у2)). И по-
следнее: если точка (х, у) лежит вне треугольника, то
найдется, такая его вершина v, что точки (х, у) и v бу-
дут лежать по разные стороны от прямой, проходящей
' через две другие вершины треугольника.
Другое решение этой задачи "основывается на сравне-
нии площадей. Обозначим через S площадь данного
треугольника, а через Si,S2 и 5з— площади треуголь-
ников, которые получаются, если соединить заданную
точку с двумя вершинами данного треугольника. Если
£=514-32+5з, то точка находится внутри треугольника,
иначе — вне его. Это решение приведено в программе
на фортране. Площадь треугольника вычисляется по
формуле Герона. Точка считается лежащей вне треуголь-
ника, если Si+S2-h$3> 1.000001*5. Множитель 1.000001?
должен учесть погрешность вычислений.
83.3. Лабиринт. Эта хорошо известная задача у
нас слегка изменена. Решение распадается на две части:
поиск пути для выхода и печать «обратного» пути — от
выхода до начального положения путника.
Простейшее решение первой части представляется та-
ким. Запишем в клетку Д [i, /], где вначале находится
путник, число 2 и положим k =2. Просмотрим все клет-
ки А лабиринта. Для каждой из них, если в ней. запи-
сан 0, прочтем четырех ее соседей. Если хоть в одной из
соседних клеток записано число k (сейчас еще рав-
ное 2), то в рассматриваемую клетку А впишем число
Теперь увеличим й:=й-Н и снова рассмотрим все
* клетки А. Этот процесс закончится, когда либо число
будет вписано в граничную клетку (выход найден),
либо за весь просмотр клеток А оно не будет вписано
пи в одну новую клетку (выхода нет). Просмотров всего
массива будет столько, сколько клеток окажется в крат-
чайшей дорожке..
Предыдущий алгоритм легко улучшить. На каждом
шаге будем по-прежнему рассматривать все клетки Д'
лабиринта. Если в клетке’записан 0, а в какой-либо
20
соседней находится число Л>2, то впишем в. клетку А
число A-J-1. Ясно, что это тоже решение первой части
задачи. Но если повезет, то здесь решение найдется
быстрее.
Заведомо эффективнее будет программа, которая,
начиная с исходной клетки (куда вначале записывается
число 2), ищет первого же свободного (т. е. с числом 0)
соседа. Вписывает в него число 3 и ищет его свободного
соседа, чтобы вписать в него 4, и т. д. Процесс оборвется
либо при достижении границы (выход найден), либо
оттого, что свободных соседей не будет (тупик). Если
тупик возникает в исходной клетке (где записано чис-
ло 2), то выхода нет. Если же тупиковая клетка иная
и в нее вписано число k >2, то следует вписать в нее
число 1 (сделать ее не проходимой) и перейти к ее со-
седней клетке с числом k—1. Такая клетка есть и един-
ственна. Это решение и приведено в нашей програм-
ме 83.3. В ней легко узнать общую схему перебора ва-
риантов.
Программу для решения задачи о лабиринте можно
сильно сократить, если написать ее рекурсивно. Мы это
сделали в 83.3—2. Но такую программу легче написать,
чем прочесть. Предупредим все же читателя, что она
верна.
Приведенные алгоритмы (кроме первого) могут да-
вать и не кратчайший путь. Для экономного поиска
кратчайшего пути в лабиринте можно завести специаль-
ные массивы X и У для списка координат (х, у) клеток,
которые следует рассмотреть. Такой прием называется
поиском в ширину.
Вначале в X, У заносятся координаты исходной клет-
ки путника. На каждом шаге из массивов X, Y извле-
каются для рассмотрения координаты очередной клетки
(с номером Ь), а ее свободные соседи в любом порядке
дописываются в продолжение списка X, У (с номера е).
Таким образом, список обрабатывается с начала и удли-
няется с конца.
Поиск заканчивается либо при достижении свобод-
ной клетки на границе лабиринта, либо при исчерпании
списка X, У (когда выхода нет). Этот алгоритм реализо-
ван в программе 83.3—3.
Поиск и печать обратного пути в нерекурсивных про-
граммах выполняется одинаково, а в рекурсивной про-
исходит автоматически.
83.4. Пила. Не требует пояснений.
21
83.5. Сократить дробь т/п. Можно запрограм-
мировать алгоритм Евклида, найти наибольший общий
делитель иод (т, п) чисел т, п и сократить на него. Это
приводит к программе 83.5.
Опишем суть алгоритма Евклида. Пусть ml^m2.
Любой общий делитель пары (ml, m2) является общим
делителем пары (m2, ml—m2), а значит, и пары
(m2, m3), где
m3;—ml—(т 14-m2) «m2
является остатком от деления ml на m2, так что заве^
домо m3 Cm2. Верно и обратное: всякий общий дели-
тель пары (m2, m3) является общим делителем пары
[(ml, m2). Поэтому
нод(т1, m2)—иод (m2, m3).
Последовательно заменяя больший аргумент у функ-
ции нод(т1,т2) его остатком от деления на меньший,
мы получим последовательность
нод(т1, т2)=нод(т2, тЗ) = ... =нод(тК,0)=тЛ,
в которой т1^т2> ... >т/(>0 и тК. будет наиболь-
шим общим делителем исходных чисел ml, m2.
Впрочем, если число п не велико, то можно прямо
подобрать дробь 1Ц—т/п с минимальным знаменателем
j — она, разумеется, будет несократимой. Нужно только
проверять равенство дробей не по равенству отношений,
а по равенству произведений:
i*n=j*m.
Это приведет к программе 83.5—2.
Заметим все же, что 83.5—2 может потребовать
п действий, в то время как 83.5 всегда уложится в
log2п действий.
ОЛИМПИАДА 84
84.1. Инверсия. Очистим массив Р нулями. Возь-
мем очередное i=l,2, ..., п и число Tt. Пройдем по
элементам Pi, Р2, .. . до тех пор, пока не встретится
7)4-1 нулевых элементов, и впишем в последний из них
число i.
84.2. Дорога. Все варианты выбора чисел /1,1'2, ...
..., in перебрать невозможно — их т". Но есть другой
путь решения задачи — индукцией по &=1,2, п— I,
22
При фиксированных числах k и ощ положим
В\k, i\+i] =min(A [ib i2t 1 ]-}- ... -f-A [i*, i\+i, A]),
где min берется по всевозможным наборам ii, 1г, .., ’
,.., ik. Тогда, как легко видеть,
B[l, 4] — min (A [q, /2, 1]} по всем 1{,
В[2, Z3] = min(B[l, г2Л-А[г2, /3, 2]) по всем /2,
В[п — 1, in] = min (В [п — 2, /„.J -f- А п — 1])
по всем i„_i.
И искомое
/?=minB[n—1, in]j ' по всем in.
Таким образом, для вычисления одного B[fe, i\+i] будет
рассматриваться лишь т вариантов (выбора /*). Для
фиксированного k и всех В [A, ift+i] будет рассмотрено
т2 вариантов, а вся задача потребует рассмотрения ме-
нее т2п вариантов.
84.3. Совершенные числа. Целое число i де-
лится на целое число j без остатка, когда
'(t-?-/) */=/.
В фортране это же проверяется равенством
[(«'//) */=»'•
Чтобы решить, будет ли i совершенным, можно просмот-
реть все числа j=l,2.....i—1, определить, какие из
них являются делителями числа i, и сложить эти дели-
тели. Таким образом, возникает программа 84.3.
Можно ускорить эту программу, просматривая «кан-
дидатов в делители» не до i—1, а до • Для этого най-
дем и если / (/^&) окажется делителем числа/,
то учтем не только /, но и k. Нужно лишь позаботиться,
чтобы один делитель не был взят дважды (при j—k).
Этот алгоритм реализован в программе 84.3—2.
84.4. Период дроби. Решение сильно зависит от
дополнительных требований, не упомянутых в условии.
При делении натурального числа М на натураль-
ное N получается целая часть частного и остаток:
i-==M+N;
Для решения задачи сначала удалим из дроби M/N
23 •
целую часть, заменив числитель М остатком: < .
М;=М—M+N*N.
Теперь мы можем последовательно получать цифры
частного i и остатки М получившейся дроби:
/:===10*Л14-Л/; Л4: = 10*Л4—i*N и т. д.
Каждый остаток не превосходит N. Следовательно, раз-
личных остатков будет не более чем Л/, и они начнут
повторяться. А когда повторится остаток, то начнут
повторяться частные и начнется период. Чтобы уловить
повторение, проще всего завести массив D [1:7V], вписы-
вать в него остатки в порядке получения и каждый но-
вый, остаток сравнивать со всеми предыдущими.
Описанное решение верное, но плохое. На обработку
&-го по счету остатка уйдет k сравнений, а на все остатки
может уйти N2/2 сравнений. Между тем на современ-
ных машинах легко взять целые М и N порядка 108, но
на выполнение 1016 действий уйдут годы. Поэтому, раз
мы уже решили завести массив D на N чисел, очистим
его и будем отмечать появление очередного остатка М
в элементе D [Л4]. Тогда проверка «новизны» /г-го остат-
ка займет одно сравнение. Описанный алгоритм реали-
зован в программе 84.4.
Но и это решение обладает серьезным недостатком.
Число N может быть столь велико, что N действий мы
еще сможем сделать, но завести в оперативной памяти
массив на N элементов уже не сумеем. Попробуем
отыскать период, не заводя массива для остатков (!).
Сначала, как и раньше, выделим из М часть, крат-
ную 2V. Затем пропустим N цифр частного. И теперь,
когда период заведомо начался, запомним один един-
ственный остаток и будем печатать цифры частного,
пока он не повторится. Это реализовано в программе
84.4—2. Любопытно, что она короче предыдущей.
Еще сложнее становится решение, если мы захотим,
чтобы период печатался, начиная с первой его цифры.
Для этого мы сначала (как и в предыдущем решении),
продвинемся до TV-го знака дроби, когда уже заведомо
начнется период. Затем определим длину р этого периода
(как и раньше,, но не печатая цифр частного). И найдем
первое число q — kp, кратное р и большее, чем N.
Теперь дойдем до q-й цифры дроби и будем син-
хронно получать остатки, нужные для вычисления
1-й, 2-й, ... и (?+1)-й, (?+2)-й, ..в
цифр дроби. Когда эти остатки впервые совпадут, Тогда
и начнется период дроби М/N. Этот алгоритм реализо-
ван в программе 84.4—3. Она адресована не всем чита-
телям, а тем, кого специально заинтересует эта задача.
84.5. Слияние массивов. Эта важная задача
принципиально должна быть выполнена за т-\-п дей-
ствий. Возьмем из А и В по первому элементу. Меньший
из них занесем в С и заменим следующим из его же
массива. Снова выберем меньший из двух, занесем в С
и т. д. После каждого сравнения в С добавляется эле-
мент— значит, сравнений будет меньше, чем m-f-n.
Нужно только позаботиться о том, чтобы программа ра-
ботала верно и при исчерпании одного из массивов.
84.6. Календарь. Удобно образовать таблицу
М [ 1 :11 ] с числом дней в месяцах (не високосного)
года. Удобно ввести и процедуру-функцию D(x), пока-
зывающую, что номер года делится на х. В фортране
вместо функции D(x) используется функция MOD(m,n),
дающая остаток от деления т/п.
84.7. Квадратики. Заметим, что сумма 04-1+5+
+ 11 — 17 получается лишь тогда, когда все числа, стоя-
щие в углах квадратика, различны. Это упростит про-
грамму,
§ 3. РЕШЕНИЯ НА АЛГОЛЕ
1. Приведенные здесь программы написаны на офи-
циальном алголе 60 *) и могут читаться усвоившим этот
язык по любому руководству. Заведомо достаточно про-
честь книжку одного из авторов**). Для придирчивого
читателя перечислим встречающиеся у нас отклонения
от официального стандарта.
1.1. В алголе-60 нет процедур ввода-вывода (на наш
взгляд, это его самый крупный недостаток), они сде-
ланы (ц названы) по-разному в разных трансляторах.
' Тому, кто захочет пропустить наши программы у себя,
придется заменить операторы ввода-вывода.
Мы ограничились (минимальным) набором из трех-
процедур:
print (а, Ь, ...), NSP, read(x,y, ...).
"♦) Алгоритмический язык алгол-60: Пересмотренное -сообще-
ние/Пер. с англ, под ред. А. П. Ершова, С. С. Лаврова, М. Р. Шура-
Бура.—М.: Мир, 1965.
**) Брудно А. Л. Алгол. — М.: Наука, 1971.
25
Оператор print печатает подряд «значения» своих Ж
аргументов, которые могут быть числовыми выражения- ж
ми (т. е. арифметическими и булевскими), именами мае- -i
сивов и строками. Целые печатаются в формате целых, >
реальные — в экспоненциальной форме, булевские— |
false и true, а строки — своими символами. j
Процедура NSP переводит печать на новую строку. |
Оператор read присваивает своим аргументам зна- J
чения, прочитанные с перфокарт или иного носителя.
Аргументы у read могут быть переменными (любого -
типа — целые, реальные, логические) и именами мас-
сивов.
Информация, нужная для таких операторов ввода-
вывода, имеется в описаниях нужных имен или в самой ;
форме аргумента (когда это строка). Приведенные \
здесь процедуры осуществил Д. Л. Либуркин в трансля- f
торе алгола АСВТ (на машинах М-4030 и др.). |
1.2. В написании иероглифов мы сочли целесообраз-
ным следующие сокращения и только их (!): }
int, bool, proc, com.
Кроме того, мы пишем без пробела goto (поскольку на
алголе это одно слово, точнее — один иероглиф), и пи-
шем beg, если соответствующее end находится в той же
строке. Обычно трансляторы это разрешают. Здесь в
последнем случае пишутся фигурные скобки { и }. Ло-
гические действия и и или изображаются значками
& и |.
1.3. В наших программах большие и малые буквы
считаются одинаковыми, но каждый объект всегда пи-
шется единообразно (в пределах одной программы).
Поэтому наши программы останутся верными, если их
переписать буквами одного типа (всеми малыми или
всеми большими, как это реализуется на многих маши-
нах). Мы сочли это полезным и удобочитаемым. Буквы
у нас только латинские.
2. Большинство решений имеют форму программ, но
некоторые оформлены как процедуры. Почти всегда дан-
ные вводятся извне и печатаются.
3. При замене русских букв латинскими мы пользу-
емся следующим стандарто’м:
ч сн ж W ы Y Ё JO
ш SH , X и ь 6 ю JU
щ SC и J ъ 6 я JA
26
А А Е,ЭЕ MM CS БВ 3Z HN TT В V И I О О У и Г G К К П Р ' Ф F ДО Л L PR ЦС
ОЛИМПИАДА 80
begin int M, Z, /, k, п, q; com 80.1.1;
read(M); print(M); n:~sqrt(M)l2;
begin int array P[l:nJ; NSP;
prints 3); k:=\; P[l]:=3;
for i :== 5, Z+2 while do
begin for ; 1, /+1 while do
begin q:~P[j]; if q*q >i then goto B/?;
then goto NP
end; BP:
print(Z); if k^n then goto NP;
k'.^k+\\ P[£]:==Z; NP:
end Z;
end end prostye chisla; \
begin int mt it j, k, n; read(m); com 80.1.2;
begin int array A, P[l:m]; read(A);
for i :== 1, Z+l while do P[Z]:=Z; goto Г;
Q: for Z:=m—1 step —1 until 1 do
if B[Z]<P[Z+1] then goto P; goto VSJO;
p: n:=P[i]; for j := m step —1 until Z do
if n<P[/] then goto S;
S: P[i]~P[i]; P[j]:=n;
Z?:=0; for k:=k+l while Z+^</n+l— k do
{п:=РУ+^1; P[Z+^]:=Pl/n4-l-^]; P[m+1-A?]:=n};
T: for Z := 1, Z+l while Z<m do prZnf(A[P[Z]]);
NSP; goto Q; VSJO:
end end perestanovki;
begin real a, b; int k, n; com 80.1.3;
read(at k); print(a, k, '=’);
b:=t;
Q: n~k+2; if n+n<k then b:=b*a;
k:=n; a:=a*q;
if /г>0 then goto Q; print(b)
end a**k=b;
begin int Z, /, kt mt n, xt y; m:=33; n:=6; com 80.1.4;
begin int array At B[1J:=1; /г:=Л[2]:=0;
27_
for /:=3, ж while Z<n do Л[/]:=4;
for Z:=n, Z—1 while i>\ do
if Л[/]=4 then Л[/]:=1 else
begin х:=Л[/]:=Л[/]+1; 1];
B[i]if .r=l then y+i else
if .r=2 then #•—Z else
if x=3 then y*i else p-s-Z;
for step 1 until n do B[j]:=B[l— 1]+/;
if B[n]=£m then goto /?; k:=k+l;
for j:=2, /4-1 while j<n do prZn/(‘(’)i print(iy
for /’ := 2, /4-1 while j^n do
begin if j>2 then print(*)*); х:=Л[/];
if x~l then prints+') else
if x=2 then print^—’) else
if x=3 then prints*') else
print print(j)
end; print('~', m); NSP; goto J?
end; NSP; print(k)
end end ((((1?2)?3)?4)?5)?6;
begin int Z, /, p, q; intarray Л[1:2, 1:15];
read(A)\ for i1, 2 do
for j 1, /4-1 while pC15 do
for p := Z, p4-l while p^2 do
for <7:= if Z<p then 1 else /4-1 step 1 until 15 do
if Л[/,/1=Л[р,<7] then goto Vs jo-,
Vsjo: print(A, i, j, p, q)
end;
begin Int nt; i, j* read(m)\
for Z :== 1, Z4-1 while 2*Z*Z^m do
begin j := sqrt(tn—i*i);
if i*i+j*j=tn then goto DA
end; prinH'nef)-, goto VYH\
DA: prints, j, m); VYH:
end m=f*Z4-/*/;
begin int w, Z, /, s; read(tn);
begin int array Л[1:т]; read(A)\ s:==0;
for Z :== 1, Z4-1 while Z</n do
begin for j:=l step 1 until Z—1 do /
if Л[/]=Л[/] then goto BYL\
s:=s4-l; BYL:
end Z; print (m, Л, s)
end end;
23
com 80.2.1;
com 80.2.2
com 80.2.3;
begin int m, Z, /, s; read(m); com 80.2.3—2;
begin int array A[l:m];
read(A); s:=O;
for Z:=l, Z+1 while Z<m do
begin for j := Z+1 step 1 until m do
if Л[/]=Л[/] then goto BYE;
s:=$+l; BYL'.
end Z; print(A, s)
end end;
begin int N, i, j, k; com 80.3.1;
read(N); print(N);
for Z :=ь 0 step 1 until 9 do
for /:=0 step 1 until 9 do
begin
if then prZnt(Z+10*j+100*&)
end <
end Z+/+fc==AT; .
begin int n, Z, /; bool b', com 80.3.2;
read(n); Z»:=true;
for i := 0, Z+1 while Z<n do
begin read(j); '
print(li b then 1— j else j);
if j=o then Z>:==false
end; if b then prZnZ(l)
end;
begin int m, n, Z, /, k; read(m, n); com 80.3.3;
begin real MIN, MAX', array read(X);
Af/jV:=X[l,l]; for j := 2 step 1 until n do
if X[l,j]<MIN then
k~l; MAX:—MIN;
for Z := 2. step 1 until m do
begin MIN:=X[i,Y\;
for / := 2 step 1 until n do
if X[i,j}<MIN then M^:=X[yj;
if MIN>MAX then {MAX:—MIN; k:=i} '
end; print{X, k)
end end;
begin int m, n, i, j, k; read(m, n); com 80^3.3—2;
л begin real min, Max; array X[1 :m,l:«]; read(X);
for i := 1 step 1 until m do
begin for j := 1 step 1 until n do
29
begin if Z>l&X[Z,j]<Max then goto S/; д
if /=1 \X[i,j]<min then /nZn:=X[ZJ]
end /; Max:~min; &:=Z; SIi
end i; print(X, k)
end end;
begin int n, i, aO, al, a2;
read(n); al:=a2:=0;
begin int array X[l:nJ; read(X); print(X);
for i := 1, H-l while Z<n do
if X[Z]=2 then a2:=a2+l.
else al;s=al+X{ij; aO:=n—al—a2;
for i := 1, H-l while i^n do -
X[Z]:=if Z<aO then 0 else
if a2 then 1 else 2;
print(X)
end end;
ОЛИМПИАДА 81
begin int n, Z, j;
read(n); printin'); Z:=l; /:=0;
M: if n-i-2*2=ra then Z:=Z+/ else j:=Z+/;
n:=n-*-2; if n>0 then goto M;
print(j)
end f(2n)=f(a), /(2n+l)=f(«)+/(«+1);
begin Int n, i, j, k, p;
int Zl, jl, kl, pl; bool b;
n:=l; M: n:=n+l; 6:=false;
for Z := 1, Z+l while i*i<n do
for j := 1, H-l while /<Z&Z*Z+/*/<a do
for k := 1, k+1 while k^j do
if Z*Z+/*/+Zs * k < n then
begin p'.—sqrt(n--i*i—j*j—k * k)\
if Z*Z+/*/+^*^+p*P=w&P<^ then
begin if b then goto VSJO;
Z1:=Z; jl:=j;.kl:=k; pl:=p; b:==trne
end
end Z, j, k, p; goto M;
VSJO: print(n, Zl, jl, kl, pl, i, j, k, p)
end 2 po 4 kvadrata;
begin int Z, j, n; read(n); print(n);
begin int array A[l:nrl:n]; Int k, p, q\
com 80.3.4;
com 81.1;
com 81,2;
com 31.3;
P.:=0; for p 1, p+1, while p+p</i+l do
begin q:=n—p+1;
for j := p step 1 until q do Л[р,/]:=&:=&+1;
for i := p+1 step 1 until q do Л[/,(/]:—£:=&+!;
for j :== n—p step —1 until p do A[q,j]:=k:=k+\;
for i := n—p step —1 until p+l do Л[/,р]:=£:=&+1
end; print(A)
end end;
begin int z, /, k, n; read(n);print(n);
begin int array Л[1:п,1:п];
proc AK;
begin Л[/,/]:=&:=&+1;
if k=n*n then goto VSJO
end AK;
A>:=0; z:=/:=l; •
Ml: AK; j:=j+l; if z+/<n+l then goto Ml;
М2: AK; z:=z’+l; if i<j then goto М2;
М3: AK; r-=j—l; if z’+/>n+l then goto М3;
M4: ЛК; z:=z—1; if z>j+l then goto M4;
goto Ml; VSJOi print(A)
end end;
com 81.3—2;
begin int z, /, k, m; com 81.4;
for z := 1, z’+l while z<9 do
for j :== 0, j+1 while /<9 do if /=#z then
for k 0, &+1 while 6^9 do if k=£i&.k=£j then
for m :== 0, nz+1 while /n^9 do if
then prznf(((z* 10+j)*10+&)*10+/n)
end;
begin int z, /, k, tn, a, b, c; com 81.4—2;
fdr z := 1, z+1 while z<9 do
begin n:=z*10;
for j :— 6, /+1 while j<9 do if /=H=z then
begin b:=(a+j)*10:
for k,:= 0, &+1 while do if k^i&.k=A=l then
begin £:=(&+&)*Ю;
for /n:=0, tn+1 while m^9 do If tn^i&m^j&m^k
then print(c+m)
end c end b end a end;
begin int n, i, t, max; read(n); com 81.5;
begin int array Л[1:п]; read(A);
31
for I := 1, Z+l while Z<n do
if A[Z]=0 then Z:==;Z+1 else
{if max<i then max~t\ Z:=0};
if max<t then max:=t;
print(n, A, max)
end end;
begin int n, Z, t, max\ read(n)\
begin int array А[1:я]; read(A)',
t:~max:~Q;
for Z := 1, Z+l while Z+n+l —i>max do
if A[Z]=/=O then Z:=0 else
{Z:—Z+l; if max<t then max:=t}; -
print(n, A, max)
end end;
com 81.5—2;
ОЛИМПИАДА 82
begin Int m, n, i, j, S; read(m, n);
begin int array A[l:/n,l:n]; read(A)',
S:=fy
for Z := 1, Z+l while i^.m do
for / := 1, /+1 while j^n do
if A[Z,/]=1 then
begin if Z>1 then
{if A[Z—1,/]=1 then goto Net] ;
if />1 then
{if A[Z,/—1]=1 then goto Net}*,
S:=S+1; Net:
end Z, /; print(mt n, A, S)
end end;
com 82.1;
begin int m, n, Z, /, S; read(tn, n);
begin int array A[0:m,0:n];
for Z := 0, Z+l while Z</n do
for / := 0, /+1 while do
if Z=0 | /=0 then A[Z,/]:==0
else fead(A[i,j]);
S:=0;
for i :« 1, Z+l while i^jn do ;
for / :== 1, /+1 while do -
if A [Z,/]=1 & A [ Z — 1,/]=0£A[Z, i-11 =0
then S:==S+1; print{mt n, A, S)
end end;
com 82.1—2;
32
com 82.2;
J. begin int P, tn, n, I, j, k\ read(P)\
begin int array A, B[1:P*P];
Л[1]:=0; В[1]:=Л[2]:=Л[2]:=1; Jfe:=2;
for n : = 2, n+1 while л<Р do
for m := 1, m~rl while do
begin for i := 2, Z+l while i^k do
if m*B[Z]==n*A[Z] then goto Ml else
if m*B[i]<n* I [t] then goto 12;
М2: for j := k, /—1 while />Z do
{A[j +1]:=Л[/]; B[/+U:=B[/]};
Ah’]:=m; B[Z]:=n; k:~k + 1;
Ml: end/л, n; print(P)\
for i 1, Z+l while i^k do
{NSP; prlnt(Mi\, 4\ B[Z], ‘=’, W]/B[Zj))
end end m/n;
begin int P, ntnt i, it a, 6;
; read(P)\ print(P)',
m:=0; zi:=l;
IT*. NSP*t print m, •, «=’, m!n^
for b := 2, b + 1 while b<P do
begin а:=/и*Ь-ьп+1;
if a*/<b»Z then
{t:=a; /:=&}
end;
if /</ then
{m:=Z; i:=/; goto IT]
end minx
begin int л, tn, st i\ read(n, m)*t
begin int array 4[l:n); bool array B[l:«l;
read[A); print( г, mt, д); s:=0;
for i := 1, /-Н while i^n do B[Z]:=true;
Г: for i 1, f+1 while /<n d°
if B[Z] then goto BR else
{BUl:=Mhue; s: -s— 4[t]};
BR*. BR]:»false; s:==s+ A[t];
If s=/n then print(B) else goto T
end end;
begin int n, lt j\ read(n)*,
begin array X[l:n]; read{X)*t рНпЦХУ
for I := 1, Z4-1 while /<л do
2 А. Л. Брудно, Л. И. Каплан
com 82.2—2;
com 82.3;
com 82.4;
33
И ВД ^0 then
{/:«/+!: If then { Х(/>Х[г): ДфМ) }J;
print(X)
end end;
begin int m, nt i, /, iO;
real mi, Ma; read(m,n);
begin array Л[1:т, read(Ay,
for i :«» 1, Z+l while Z<m do
begin for /:=«!, /+J while /С» do
begin if i> l&A[Z,/]<Afa then goto SZ;
if /=1 | A[i,j]<rni then mi:=A[i,j]
end j; Ma:=mi; iO:=*i; SI:
end Z;
for I := 1, /+1 while j^n do
begin for i :=» 1, Z+1 while Z</n do
У A[ZJJ>Afa then goto Bri;
print(i0, j, A[iO,j]): goto Da: Bri:
end /; print^nef); Da: print(ni, n, A)
end end;
begin int n, k, i, j; read(n, fi);
begin int array X[l:n], read[X, У);
for i :«= Q st,ер. 1 until n—k do
begin for j := 1, /+1 while j^.k do
if ^[/+/]=^У[/] then goto Brj;
print(lda\ z’+l); goto Da; Brji
end Z; printsnei\ 0);
Da print(n,. k, X, Y)
end end:
ОЛИМПИАДА S3
proc BIT REV:
begin int m, n, b, k\
for m:=512, m+1 while m<1024 do
begin n:==/n; 6:=0;
lo'r Jj := 512, k/2 while n>0 do
if n^k then
k; b:==£»+512/&};
print(b)
end m end bit-revers;
proc BIT REV:
begin int kt m; m:=l; goto RRM;
' 34
20m 82.5;
com 82,6;
com 83.1;
com 83.1—2;
ММ К: £:=£/2;
МВКд if then got» MMK*t
tn:=tn+k;
PRMt print (tn)\ Z?:==512;
if m<1023 then goto MBK
end bit-revers\
bool proc TV NT (x, y, xl, pl, x2, y2, хЗ, y3); com 83.2;
real x, yt xl, y\, x2, y2t хЗ, y3;
begin bool proc RZ(x\, y\, x2, y2, хЗ, y3};
real xl, y\, x2, у2, хЗ, y3\
/?Z:=((x3—xi)*(y2—pl)—(x2—xl)*(y3—
((x—xl)*(y2—pl)— (x2—xl)*(y—yl))<$
TVNT:—RZ(xlt y\9 x2, y2, x3, y3)|
RZ(x2, y2, x3, y3, xl, yl)\
RZ(x3, y3> xl, yl, x2, y2)
end tochka (0) vne treugolGnlka (I, 2, 3);
proc LAB(Mt N, A, i, j); согтЯЗ.З;
value M, N, i9 j\ int M, Nt i, y, int array Al
begin int p, q„ k; A[ij\;==*k;==2i
NK: if /=1 \i=M\i=^l[p=N then goto PD:
PK-. p*.=l; q.=h
for i := p—1, p, p+1 do for ] ’:= 7—1, q, q+l da
if (Z==p I/«^)&A[Z,/]=O then
{ A[Z,/]:=£:=£+1; goto NK
KM: if fe=2 then {print^net vyhoda')\ goto VS/в};
4(p, ?1:=1; fe:^-l;
for i :== p—1, p, p+1 do for / := q—l, qt q+t do
if A[i,j]=k then goto PK;
PD-. prints it j); NSP-,
if k~2 then goto VSJO-, k:=k—l‘y p:—ry
for i := p—1, p, p+1 do for / := q—I, q9 7+1 do
if l<Z&Z<M&l</&/<tf then
{ if Л[/,/1=Jb then goto PD KS/O:
end labirint*,
proc LAB(M, N, A, Z, /); com 83.3-2;
value M. N, i, /; int M, N, i, у int array A;
begin bool VYH\
proc L(Z, /); int f, /;
if VYH then else if A[Z,/]=O then
begin if Z=11 i=M | /=11 /=^ then УГЯ:=4гие;
L(l, j-iy, Щ, /+«); L(i-l, j)',
it VYH then printer, i, j, ')’)
2*
35
P . . . . .. z...v
I
end,
VW—false; £(?, /); If ~IVY’I then рНпЦ'пе! vyhoda')
end labirint s rekursiej;
proc LAB (M, /V, A, it /); com 83.3—3;
Inf Mt V, it ft int array.^ j
begin int p, q, bt e; int array X, Y fl: Me 'b
Л[£ /]:«=2; X[l]:-f; e:«l;
if p=1 | i=M | /=1 | /=JV then goto P£>;
for b := 1, H-l while b^e do
begin р:=Ж, q:^Y[b];
for i ;a== p—lf pt p-|-l do for j:= q—1, q, 9+1 do
if (i=»p j/^9) &Л[/,/]=0 then
begin Л[/,/]:==Л(р,9]+1;
if 11 I /== 1 I V then goto PD\
e:«e+l; Xfe]:-C УИ:==ч
end
end b; print ('net vyhoda'); goto VSJO;
PD: MSP; print (AIL j]t L /); p:^t q-*4\
if Л[£/]=2 then goto VSJO;
for i := p—1, p, p+1 do for j9-*!, q, p+l do
if (t=p then
{И Ли,/]=.4[р,р]—1 then goto?#}; VSJO'
end labirint
proc Р/£Л(М, X); int M; array X; com 83.4;
begin int it j, k;
/:==/:—&:=1; if M<3 then goto VSJO;
IT: if X[/]<X[f+l]&X[t+l]>Xff+2] then
begin r:=u+2; /:=/+2;
if £</ then £:=/;
if Z+1<M then goto IT
end else
begin i := f+1; /~1;
if f+A<M then goto IT
end; VSJO: nrint(M.XJt)
en ’ pita;
proc MDN(m, n)\ int mt n; com 83.5;
begin int i, j, k; i:=m; j:=n;
if then £oto iMj;
jMi: k:—i; i:=j; j:~k\
iM j: j:—j—jЧ- i♦/;
if />0 then goto jMt
end zokratitB drobG m/n;
36
proc ‘VlDN(mt n); int m, n;
be*in int i, j\
for /:= 1 step 1 until n do
be^in i\~i*m!n\
if then goto T
end; T: n:~i: n:~ j
end s ok rat lib drobb m/n',
ОЛИМПИАДА 84
begin com IN VERS! J A
int ij, k, n: read(n)\ printsn=\ n)\
begin int array P, T[l:nJ; read(T);
for t:= 1 step 1 until n <’o P [i]:=0;
for i:= I step 1 until n do
begin /:=0; fc:=0; SI:
it />[/г]=0 then /:»/+!;
if then goto S/; P[k\:=i
end i; print (T, P)
end end inverse ja]
begin com DOROGA
int m, n, it I, k\ read(tn, n); prinRtn, n);
begin real x, r; array A[1:л—1], В,
read(A); prints A)',
for i :=« f step 1 until m do B[ZJ:=O;
for k := 1 step I until n—1 do
begin for f := 1 step 1 until m do
begin r:=B[l]+A[l, >!;
for ! != 2 step I until m do
begin x:=B[/]+А1А/Л];
if x<7 then r:=x
end i: C[j]:—r
end /; for ):= 1 step 1 until n do £(/]:«= C[/J
end k; r:=B[l];
for i :== 2 step 1 until m do
if then r.=B[t’J;
print(r)
end end doroga]
begin com SOVERSHENNYE CHISLA
int /ч, i, j, s; read(m)\ printsm}\ NSP\
for i := 2 step 1 until -i do
begin s:==/:s=l; for / := H-l while /<J do
if then .;==s+/;
com 83.5—2;
84.1;
84.2;
84.3;
37
if then prlnt{i)
end i
end sovershennye chisla;
begin com SOVERSHENNYE CHI SLA
int m, /, /, k, s; read(m); print(*m—\ m);
for i :» 2 step 1 until tn do
begin s:=/:=l; SJ: /:=/+!;
if then
{$:=$+/: if j<k then s:=<s-H);
if j<k then goto SJ;
if 5=/ then print(i)
end J
end sovershennye chisla;
begin com PERIOD DROBI M/N
int M, N, i; bool b; read(Mt N); prini(M. N}{
begin bool array Z)[0.W—1J;
M;=M—M~N*N; b;=ir^;
BF; for t:=0 step 1 until N~~ 1 do DpJ^true;
SM: £>[Af]:—false:
if then print (i);
if £>[M] then goto SM;
if b then {6:=false; goto BF}
end end period drobi;
begin com PERIOD DROBI M/N
int Af, N, i, jt k; read(M, N); printtM, N);
M.=M~-M~-N*N;
for k ;= 1, &+1 while k^N\j^=M do
begin if k=N then j:—M;
i:=\Q*M’~N; M:=lO*M~i*N;
if k^N then pritU(i)
end
end period drobi;
begin com PERIOD DROBI M/N
int M, N, /, /, k, pt q; read(Mt N); prini(M^ .N);
M;=M-M+N*N; i.^M;
for k := 1 step 1 until N do
/:=i; p;=l; - .
for j := 10*/—10*/-7-^*^
88
M4-2;
84.4-3;
while /фг do д:=р-М;
q-~N+p*p-^p;
tor k :=AH1 step 1 until q do
goto W:
Mf: M:=^10*M—10*МЧ-Л/<Ж
IW-j-ЖиА^
RN: it №& then goto Шт
for k :== 1 step 1 until p do
М:=1Ы-
end period drobi;
begin com SLUANIE MASSIVOV
int M, Nt i, j, k; read(Mt Af); print(M, V);
begin array A[1:M], ВЦ:ЛГ]9 Cll:AHAfJ;
read{At В); print(At B)\,
11=1; for£:~l step 1 until M+N do
begin if i>M then goto BJ;
if f>N then goto Ah
If then {Ah CW:=M *=#1)
else {Bh C[fe]:=B[/]; /:=/+!}
end; print(C)
end end slij nie\
begin com CALENDARS
int at b, ct it j\ int array Л4 (1:111:
bool proc D{x)\ int x; Z):—(c—c-~~x*x);
for I: - 1, 3, 5> 7, 8, 18 do Mkk=3t;
for i: == 4, 6, 9, 11 do Al[Z]:=30; M[2J:=28;
read(a, b, c); com ctislo, tnesjac, god;
for step 1 until b—1 do
if 6>2&(D(4)&nD(100) | D(400)l then
print(a, bt ct j)
end kalendarfy
begin com RVADRATIKI 84.7;
int M, f, /, s; read(M); print(M);
begin int array A[1:M»1:A1]; read(A); print(A}\ s:=9;
for i : == I step 1 until Л4—1 do
for / : = 1 step 1 until M—1 do
if A [i,i]+A[lti+1 HA [H-1,/]+A [H 1,H U- IT
then s:=s+l; prints)
end end koodrattkl*.
39
4
§ 4. РЕШЕНИЯ НА ФОРТРАНЕ j
ч.-
Приведенные здесь программы написаны на широко s
распространенном фортране IV и могут быть выполнены
почти на любом трансляторе фортрана. Школьники,
изучившие более поздние версии, например фортран 77, ,
смогут некоторые программы переписать короче.
ОЛИМПИАДА 80
С 80.1.1
DIMENSION К(500)
READ 100,М
PRINT 110JVL
N=1
К(1)=3 ;
DO 2 1=5,M,2 -x
DO 1 J=1,N
KJ=K(J)
IF(I/KJ*KJ.EQ.I) GOTO 2
1 CONTINUE
’ PRINT 100,1
IF(I«I.GT.M) GOTO 2
N=N+1
K(N)=I
2 CONTINUE
STOP
100 FORMAT(1X,I6)
110 FORMAT(,_M=,.ie/7H....... . . 2/7H .... . . 31
END
C 80.1.2
INTEGER A(9),B(9),P(9)
READ 100,M,(A(I), 1=1,M)
IF(M.EQ.l) GOTO 10
M1=M—1
DO 1 1=1,M
1 P(I)=I
GOTO 8
2 DO 3 1=1, Ml
K=M-I
IF(P(K).LT.P(K+1)) GOTO 4
3 CONTINUE
GOTO 11
4 N=P(K) ;
40 1
DO 5 J=l,I L=M—J-|-l IF(N.LT,P(L)) GOTO 6 -
5 CONTINUE
6 P(K)=P(L) P(L)=N L«(M-K)/2 DO 7 1=1, L N=P(K+I) P(K-H)=P(M+1-I)
7 P(M+1—I)=N
8 DO 9 1=1,M N=P(I)
9 B(I)=A(N) PRINT 110,(B(I),I=l,M) GOTO 2
10 PRINT 110,A(l)
11 STOP
100 FORMAT(I1,9(2X,I5))
110 FORMAT('_Z,9(I5,2X)) END '
с READ 100,A,К PRINT 100,A,К B«1 GOTO 2 80.1.3
1 A=A*A
2 N=K/2 1F(N+N.LTK) B=B*A K=N IF(K.GT.O) GOTO 1 PRINT 110,В STOP
100 FORMAT(1X,F5.2,2X,12)
no FORMAT(Z_Z,E13.6) END *
с INTEGER A(8),В(9),C(9), 80.1.4
р Z(4)/z+z/~z/*z»77, e/'=-7 M=35 N=6 К =0
<1
C(N)=E
A(1)=O
N1=N—1
DO 1 I=2,Nl
1 A(I)=4
2 DO 12 I=1,N1
J=N—I
IF(A(J).EQ.4) GOTO 11
A(J)=A(J)+1
L=A(J)
J=J+1
GOTO(3,4,5,6),L
3 B(J)=B(J— 1)+J
. GOTO 7
4 B(J)=B(J-1)-J
GOTO 7
5 B(J)=B(J-1)*J
GOTO 7
6 B(J)=B(J-1)/J
7 J=J+1
IF(J.GT.N) GOTO 9
DO 8 L=J,N
8 B(L)=B(L-1)+L
9 IF(B(N).NE.M) GOTO 2
K*=K+1
DO 10 L=1,N1
J=A(L)
10 C(L)=Z(J)
PRINT 100,(L,C(L),L=l,N),M
GOTO 2
11 A(J)=1
12 CONTINUE
PRINT ПО,К
STOP
100 FORMAT(9(I2,1X,A1),I2)
110 FORMATC^'.IS)
END
C ' 80.2.1
INTEGER A(2,15),C(30)
EQUIVALENCE (A(l.l).C(lM
READ 100,A
PRINT l00,((A(I,J),J=l,15),I=l,2)
DO 1 1=1,29
11=1+1
42
M=C(I)
DO 1 J=I1,3O
IF(C(J).EQ.M) GOTO 2
1 CONTINUE
2 L=(I+l)/2
K=I+2-2*L
Ll=(J+l)/2
Kl=J+2—2*LI
PRINT 11O,K,L,K1,L1
STOP
100 FORMAT(15(1X,I4))
110 FORMAT(1X,I1,2X,I2)
END
C 80.2.2
READ 100.M
PRINT 100,M
M1=SQRT(FLOAT(M/2Y14-O.t
DO 1 1=1,Ml
J=SQRT(FLOAT(M-I*l))+O.l
IF(I*I+J*J.EQJ4) GOTO 2
1 CONTINUE
PRINT 110
: STOP 1
2 PRINT 120,1,J -
STOP 2
100 FORMAT(1X,I4)
110 FORMAT('_NET')
120 FORMAT(2(1X,I2))
END
Добавка 0.1 введена на случай, когда корень из квад-
рата натурального числа окажется вычислен с недостат-
ком, а в иных случаях эта добавка не вредит,
С 80.2.3—2
INTEGER А(ЮОО)
READ 100,M,(A(I),I=l,M)
PRINT 100,M,(A(I),I=l,M)
K=I
IF(M.EQ.l) GOTO 3
M1=M—1
DO 2 1=1,Ml
N=A(I)
DO 1 J=I,M1
IF(A(J-H).EQ.N) GOTO 2
43
1 CONTINUE
k«=k+i :
2 CONTINUE
3 PRINT 100.K
STOP
100 FORMAT(1X,I4/15(1X,I4))
END
C 80.3.1
READ 100,N
PRINT 100,N
DO 2 1=1,10
DO 1 J=l,10
K=N-(J-1)-(1-1)
IF(KLT.l) GOTO 2
IF(K.GT.9) GOTO 1
M=100»K4-10*(J-l)+I-l
PRINT 110,M
1 CONTINUE j
2 CONTINUE
STOP
100 FORMAT(1X,12)
110 FORMAT(1X,13)
END
C 80.3.2
INTEGER»2 A(31)
READ 100,N,(A(I),I=»\,N)
PRINT 100,N,(A(I),I=l,N)
DO 1 1=1,N
IF(A(I).EQ.l) GOTO I
A(I)=1
GO TO 2
1 A(I)=0
N=N+l
A(N)==1
2 PRINT 100,N,(A(I)J«f N)
STOP
100 FORMAT(IX,I2/31UX,H))
END
C gp з з 2
REAL MAX,M IN,X (50,50)
READ 100,M,N,((X (1, J),l«1 1 ,N)
DO 1 1=1/4
44
I PRINT 110,(X(I,J),Je»t,N)
DO 3 I—l.M
DO 2 J==l,N
IF(I.GT.1.AND.X(I.J)LT.MAX) GOTO 3
1F(J.EQ.1.OR.X(I,J).LT.MIN) MIN=>X(I,J)
2 CONTINUE
MAX=MIN
K=l
3 CONTINUE
PRINT 120.K
STOP
100 FORMAT(I2.1X,12/10(1 X.F7.3))
И0 FORMAT(10(2X.F7.3))
120 FORMAT('_',I2)
END
C 80.3.4
INTEGERS X(1000)
READ 100,N,(X(I),l=«l,N)
PRINT 100.N,(X(l),l=l,N)
N0=«0
Nl—0
DO 1 I—LN
IF(X(I).LE.l) N1=N1+1
1 N0=N0+X(I)
N0=Nl—N0+(N—Nl)»2
DO 4 I—l.N
IF(I.LE.N0) GOTO 3
IF(I.LE.N1) GOTO 2
X(I)=2
GOTO 4
2 X(I)=1
GOTO 4
8 X(I)=0
4 CONTINUE
PRINT H0,(X(I).I=l.N)
STOP
100 FORMAT(1X,I4/40(1X.H))
HO FORMAT(40(lX,Ii))
END
ОЛИМПИАДА 81
C 811
READ 100,N
PRINT 100.N
45
i=i J=0
1 K=N/2 IF(K4-K.LT.N) GOTO 2 I=I+J GOTO 3
2 3 J=I+J N=K IF(N.GT.O) GOTO I PRINT 110,J STOP
100 110 FORMAT(1X,I3) FORMAT('_',I4) END
в 81.2 LOGICAL V N-l 1 N=N-H V=.FALSE. N1=SQRT(FLOAT(N)) DO 4 1=1,N1 DO 3 J=1,I IF(kI+J*J.GE.N) GOTO 4 DO 2 K=1J IF(IH4-JU+K*K.GE.N) GOTO 3 L=SQRT(FLOAT(N-IH-J*J-K<H W IF(bI+J*J+K*K+L*L.NE.N.OR.L.GTI> GOTO 2 IF(V) GOTO 5 11=1 J1=J K1=K L1=L V=.TRUE. GOTO 4
2 CONTINUE 3 CONTINUE 4 CONTINUE GOTO 1
। 5 PRINT 100,N,I,J.K.LtIlJLKl,Ll ‘ . STOP
10 0 FORMAT('_',I3/8(1X,I2)) END
( де Зм. примечание к программе 80.2.2:
c ei.a—s
COMMON L.K
INTEGER A(30,30)
READ 100,N
PRINT 100,N
L=N*N
K=0
1=1
J=1
1 CALL SP(A(I,J),&5)
J=J+1
IF(I-J-J.LE.N) GOTO 1
2 CALL SP(A(I,J),&5)
1=1+1
IF(LLT.J) GOTO 2
3 CALL SP(A(I,J),&5)
J=J—1
1F(I+J.GT.N+1) GOTO 3
4 CALL SP(A(1,J),&5)
1=1-1
IF(LGT.J+1) GOTO 4
GOTO 1
6 DO 6 1=1,N
6 PRINT 110,(A(I,J),J=l,N)
STOP
100 FORMAT(1X,I2)
110 FORMAT(30(1X,I3))
END \
SUBROUTINE SP(X,*)
COMMON L,K
INTEGER X
K-K+l
X=K
IF(X.EQ.L) RETURN 1
RETURN
END
C 8L4—2
INTEGER A(24)
N=0
DO 3 1=2,10
M1=(I—1)*10
DO 3 J=l,10 .
IF(J.EQ.I) GOTO 3
M2=(Ml+(J-i))*10
' ' ’' ’ ’ . ’ • ' - I • ’ !
47
DO 2 К=1ДО I
IF(K.EQ.l.OR.K.EQ.J) GOTO 2 1
M3=(M2+(K-l))*10 1
DO 1 L = l,10
IF(L.EQ.I.OR.L.EQJ.OR.L.EQ.K) GOTO 1
N=N+1
A(N)==M3+(L—1)
IF(N,LT.24) GOTO i
PRINT 100Л
N=0
1 CONTINUE
2 CONTINUE
3 CONTINUE
STOP
100 FORMAT(24(1X,I4))
END
C 81.5—2
INTEGER A(1000)
READ 1OO,N,(A(I),I=1 N)
PRINT 100,N,(A(I),I«l,N)
MAX=0
K=0
1=0
I 1=1+1
1F(A(I).EQ.O) GOTO 2
K=0
1F(I+MAX LT.N) GOTO I
GOTO 3
2 K=K+1
IF(K.GT.MAX) MAX=K
IF(l.LT.N) GOTO 1
3 PRINT 100,MAX
STOP
100 FORMAT(1XJ4/10(1X,I5))
END
ОЛИМВИАДА 82
C 82J
INTEGER*2 A(100,100i
READ 100,N,((A(l,J),l = l,N),j=l,N)
DO 1 1=1
1 PRINT 110.(A(1,J),J=m.N1
K=0
DO 4 J==1,N
48
J
DO 4 I = 1.N
IF(A(l,J).EQ.O) GOTO 4
IF(JEQ.l) GOTO 2
1F(A(I,J—-l).EQ.l) GOTO 4
2 IF(LEQ.l) GOTO 3
IF(A(I-l,J).EQ.l) GOTO 4
3 K-K+l
4 CONTINUE
PRINT 120X
STOP
100 FORMAT(I2/40(I1,1X))
110 FORMATC^'JOOIl)
120 FORMAT^',14)
END
INTEGER A.B,P
READ 100,P
PRINT 100,P
PRINT 110
M=0
N = 1
1 1 = 1
J=l
DO 2 B=1,P
A«M*B/N-H
li• (A*J.GE.B*I) GOTO 2
I=A
J=B
2 CONTINUE
M=I
N=J
R«M/(N+0.)
PRINT 120XN,R
IF(N.GT4) GOTO 1
STOP
100 FORA1AT(IX,13)
HO FORMATC^_0/_^1=0')
120 FORMAT(IX,I3,7,,13/=S/.F8.6)
END
INTEGER S,A(1000),B*2(1000)
READ I00,M,N,(A(I),l=l.N)
PRINT 100,M,N,(A(I),l==i,N}
DO 1 1=1,N
82.2—2
82Л
J B(I)=O
s=o
2 1=1
GOTO 4
a B(i)=o
S=S—A(I)
1=1+1
4 1F(B(I).EQ.1) GOTO 3
B(I)=1
S=S+A(I)
1F(S.NE.M) GOTO 2
DO 5 1=1,N
1F(B(I).EQ.1) PRINT U0,I,A(I) ‘
6 CONTINUE
STOP
*00 FORMAT(1X,I8,2X,I4/10(2X,I5))
110 FORMAT(1X,I4,2X,15)
END
DIMENSION A(1000)
READ 100,N,(A(I),l=l,N)
PRINT 100,N,(A(I),I=l,N)
K=0
DO 1 1=1,N
)?(A(I).EQ.O) GOTO 1 ,
K=K+1
A(K)=A(I)
1 CONTINUE
K=K+1
IF(K.GT.N) GOTO 3
DO 2 I=K,N
2 A(I)=0
3 PRINT U0,(A(IhI=l,N)
STOP
100 FORMAT(1X,I4/15(1X,F4.1))
110 FORMAT(15(1X,F4.1))
END
C • 82.5
REAL MAJVII,A(50,50)
READ 100,M,N,((A(l,J),I=l,M)4=l>N} .
DO 2 I=1JW
DO 1 J=1,N
50
IF(I.GT.1.AND.A(I.J).I.E.MA) GOTO 2
IF(J.EQ.l.OR.A(I,J).LT.MI) MI=A(I,J)
1 CONTINUE
MA=M1
10=1
2 CONTINUE
DO 4 J=1,N '
DO 3 1=1,M
IF(A(I,J).GT.MA) GOTO 4
3 CONTINUE
PRINT 100,I0,J,A(lO,J)
GOTO 5
4 CONTINUE : ,
PRINT 110 . '
5 PRINT 100.M.N
DO 6 1=1.M
6 PRINT 120,(A(UU=4;N)
STOP
100 FORMAT(2(1X,I2)/10(IX,F7.3))
H© FORMAT('_0'r
120 FORMAT(15(1X,F7.3))
END
G . . 82.6
INTEGER X(1000),Y(1000)
READ 100,N,(X(I),1=1,N)
READ l00,K,(Y(I),I=l,K) -
PRINT 100,N,(X(I),I=l,N)
PRINT 100,K,(Y(I),I=l,K)
I=-l
1 1=1+1
IF(I+K.OT.N) GOTO 3 ,
DO 2 J=1,K
IF(X(I+<NE.Y(J|) GOTO t
2 CONTINUE
1=1+1
PRINT ПОД
STOP 1
3 PRINT 120
STOP 2
100 FORMAT(1X,14/10(2X45))
110 FORMATt^DA^'J^
120 FORMAT('_NET')
END -
5)
ОЛИМПИАДА 83
с 83.1-2
INTEGER В
М-512
В-1
GOTO 3
1 В-В-К
К-К/2
2 IF(B.GE.K) GOTO 1
в-в+к
М—М+1
3 PRINT 100,M.B
К-512
IF(M.LT.1O23) GOTO 2
STOP
100 FORMAT(Z„M—',I4,'—U_B(M)-'.Ц)
END
C 83.2-2
READ 100,XI,Y1,X2,Y2,X3,Y3,X,Y
PRINT 1OO,X1,Y1,X2,Y2,X3,Y3,X,Y
S=GERON(X1,Y1,X2,Y2,X3,Y3)
Si—GERON(X1.Y1,X2,Y2,X,Y)
S2-GERON(X1,Y1,X3,Y3,X,Y)
S3=GERON(X2,Y2,X3,Y3,X,Y)
IF(S1+S2+S3.GT.1.000001»S) GOTO I
PRINT 110
STOP 1
1 PRINT 120
STOP 2
100 FORMAT(8(2X,F6.2))
110 FORMAT('_TOCHKA V TREUGOL6NIKE')
120 FORMAT('„TOCHKA VNE TREUGOL6NIKA') .
END
FUNCTION GERON(X1,Y1,X2,Y2,X3,Y3)
DIS(XI,Y1,X2.Y2)-SQRT((X1-X2)»*2+(Y1-Y2)*.2)
A-DIS(X1,YI,X2,Y2)
B—DIS(X1,Y1,X3,Y3)
C—DIS(X2,Y2,X3,Y3)
P-(A+B+C)/2.
GERON—SQRT(P»(P—A)*(P—B)»(P—C))
RETURN
END
62
INTEGER P,Pl,P2,Q.Q1 Q2,K*2,A*2(40.40)
. READ 1OO,M.N.I.J.((A(P,Q),P=1>M),Q=1>N)
PRINT 100jn,N.l,J
DO 1 P=1,M
1 PRINT 110,(A(P,Q),Q=l,N)
A(I,J)=2
K=2
C GRANICA
2 IF(I.EQ.1.OR.I.EQ.MOR.J EQ.1.OR.J.EQ.N) GOTO 7
C NOV AJA KLETK.A
3 P=I
Q=J
P1=P-1
P2=P+1
Q1=Q-I
Q2=Q+1
DO 4 1=P1.P2
DO 4 J=Q1,Q2
IF(I.NE.P.AND.J.NE.Q.OR.A(I,J).NE.O) GOTO 4
K=K+1
A(1,J)=K
GOTO 2
4 CONTINUE
IF(K GT 2) GOTO 5
PRINT 120
GOTO 9
C VOZVRASCENIE
5 A(P,Q)=1
K=K-1
DO 6 I=P1,P2
DO fl J=Qi,Q2
IF(A(I,J).EQ K) GOTO 3
8 CONTINUE
С PECHAT& DOROWKI
7 PRINT 130XI.J
IF(K.EQ.2) GOTO 9
K=K-1
R=1
Q=J
P1=P-1
P2=P4-i
Ql=Q-l
Q2=Q+l
DO 8 I-PI.P2
53
83.3
DO 8 J=Q1,Q2
IF(LLT.1.OR.LGT<M.OR.J.LT.LOR.J.GT.N) GOTO 8
IF(A(I,J).EQJK) GOTO 7
8 CONTINUE
9 STOP
100 FORM AT(4( 1X, 12)/40 (11,1X))
110 FORMAT('_/,40I1)
120 FORMAT('_NET VYHODA')
130 FORMAT(Z_,,I4,2(2X>I2))
END
C 83.4
DIMENSION X(1000)
READ 100,M,(X(I),I=l,M)
PRINT 100,M,(X(I),I=l,M)
K=1
1F(M.LT.3) GOTO 3
1=1
J=1 •
1 lF(X(I).LT.X(I+l).AND.X(I+l).GTX(I4-2))
P GOTO 2
J=1
1=1+1
1F(K+I.LT.M) GOTO 1
GOTO 3
2 J=J+2
IF(J.GT.K) K=J
1=1+2
IF(I+1.LT.M) GOTO 1
3 PRINT 100,К . t
STOP . .
100 FORMAT(1X,I4/10(1X,F7.3))
END
C 83.5
READ 100,M,N
M1=M
N1=N
1 K==M1— M1/N1*N1
IF(K.EQ.O) GOTO 2
M1=N1
N1=K
GOTO 1
2 M1=M/N1 t
N1=N/N1
PRINT IOO.M.N.M1.N1 STOP
100 FORMAT(2((X,14)) END ОЛИМПИАДА 84
с 84.1 INTEGER TI,P(100),T(100) - READ 100,N,(T(I),I=l,N) PRINT 100,N,(T(I),I=l,N) DO I I=l.N
1 P(I)=0 DO 3 1=1,N TI=T(I) -K=o
2 J=0 J=J+1 IF(P(J).NE.O) GOTO 2 K=K+1
3 IF(K.LE.TI) GOTO 2 P(J)=I PRINT 11O,(P(I),I=1.N) STOP
100 но FORMAT(1X.I3/20(2X,I2)) FORMAT(30(1X,I3)) END
с; 84.2 DIMENSION A(15,15,2O),B(15),C(15) READ 100.N.M PRINT 100.N.M N1=N— I READ 110,(((A(I.J>K)>I=l,M).J= l «М),К=tNl) DO 1 K=1,Nl DO 1 1=1,M
1 PRINT 110,(A(I,J,K),J=l.M) DO 2 I=t,M
2 B(I)=0 DO 6 K=1.N1 DO 4 J=l.M R=B(1)+A(1,J,K) DO 3 1=1.M X=B(I)+A(I,J,K) IF(X.LT.R) R=X
55
3 CONTINUE
4 C(J)=R
DO 5 J=1,M
6 B(J)=C(J)
6 CONTINUE
R=B(1)
DO 7 1=1,M
IF(B(I).LT.R) R=B(I)
7 CONTINUE
PRINT 120,R
STOP
100 FORMAT(2(1X,I2))
110 FORMAT(10(1X,F7.3))
120 FORMAT(1X,F9.3)
END
c 84.3—2
READ 100 M PRINT 100.M JF(M.LE,6) GOTO 5 M1=M-1 DO 4 1=6,Ml N=1 J=2 1 k=i/j IF(K.LE,J) GOTO 3 JF(J*K.LT.I) GOTO 2 N=N+J+K IF(N.GT.l) GOTO 4 2 J=J+1 -
GOTO 1 3 IF(J*J.EQ.I) N=N+J
IF(N.EQ.I) PRINT 100,1 4 CONTINUE 5 STOP 100 FORMAT(1X,I7) END C 84.4—2
READ 100,M,N PRINT 100, M.N M=M—M/N*N DO 1 I«1,N M=M*10 1 M=M-M/N*N A
66
к=м
2 К=К»10 J=K/N PRINT 110,1 К=К—I»N IF(K.NE.M) GOTO 2 STOP
100 ПО FORMAT(2(1X,I3)) FORMAT(lX.Il) END
С 8M DIMENSION A(1000),B((000),C(2000) READ 100,M,(A(I),I=l,M) READ 100,N,(B(J),J=1,N) PRINT 100,M.(A(I),I-1.M) PRINT 100,N,(B(J),J=l,N) 1=1 J=1 L=M+N DO 3 K=1,L 1F(I.GT M) GOTO 1 IF(J.GT N) GOTO 2 IF(A(I).LT.B(Jj) GOTO 2
1 C(K)=B(J) J=J+1 GOTO 3
2 C(K)=A(I) 1=1+1
3 CONTINUE PRINT 110,(C(K>.K=l,L) STOP
100 по FORMAT(1X,14/10(1 X.F7.3)) FORMAT(15(1X.F7.3)) END
с 84.6 • INTEGER A.B.C
с CHISLO MESJAC GOD DIMENSION M(U) DATA M/31,28,31,30,31,30,31,31,30,31,30/ READ 100,A,B,C N=A IF(B.EQ.l) GOTO 2 J=B-1
67
DO 1.1-14
, 1 N=M-f-M(I)
IF(B.GT.2.AND.(MOD(C,4).EQ.O.AND.
P MOD(C,100).NE.0.OR.MOD(C,400).EQ.0))
P N=N+1
2 PRINT lOO.A.B.C.N
STOP
100 FORMAT(2(1X,I2),1X,I4,1X,I3)
END
C
INTEGER*2 A(50,50)
' READ 100,M,((A(I.J).I=1.M).J=l,M)
DO I 1=1,M
1 PRINT 110,(A(l,J),J=l,M)
K=0
L=M—1
DO 2 J=1,L
DO 2 1=1,L
IF(A(I,J)+A(I+l,J)+A(I,J+l)+A(I+l.J+l).EQ.17>
P K-K+l
2 CONTINUE
PRINT 120,К
STOP
100 FORMAT(I2,20(1X,I2))
110 FORMAT(40(1X,I2))
120 FORMAT(1X,14)
END
§ 5. ПРОГРАММИРОВАНИЕ
ПЕРЕБОРА ВАРИАНТОВ
Программирование перебора вариантов является
сердцевиной программ искусственного интеллекта, неза-
висимо от того, к чему он прилагается — программиро-
ванию игр, выбору решений, распознаванию образов
в т. п. Между тем даже программист, опытный в вычис-
лительных задачах, знающий операционные системы . и
языки программирования, зачастую оказывается беспо-
мощен в программировании перебора, поскольку схема
перебора не укладывается в схемы циклов, имеющихся
в языках программирования.
Сейчас мы составив блок-программу перебора. Сде-
лаем это на одной определенной задаче, но сделаем
58
так, что для других задач перебора потребуется менять
лишь конкретное содержание блоков, а сама блок-про-
грамма сохранится.
Вот наша задача. Какими способами можно
расставить на шахматной доске 8 ферзей так, чтобы они
не угрожали друг другу *).
Прикинем, как искать эти расстановки. Поставим
первого ферзя на какую-нибудь клетку. Затем поставим
второго ферзя на первую клетку и проверим, что ему
не угрожает первый. Если угрожает, то передвинем вто-
рого ферзя и снова проверим и т. д. Когда второй ферзь
окажется на допустимой клетке, возьмем третьего фер-
зя и будем двигать его, пока он не окажется на допу-
стимой клетке и т. д.
Уже это побуждает ввести два понятия, фундамен-
тальных для теории перебора: номер хода и номер ва-
рианта. Их принято обозначать буквами i и /. В расста-
новке ферзей номером хода будет порядковый номер
ферзя (которого мы пытаемся поставить), а номером
варианта — порядковый номер попытки установить этого
ферзя после того, как положение предыдущих фиксиро-
вано. Понятие «номер варианта» не следует понимать
буквально. Им, например, может служить само поле, на
которое предполагается поставить ферзя. Важно лишь,
.чтобы рассмотрение вариантов было упорядочено. ‘
s Сказанное уже стоит записать блок-схемой (см. с. 60).
f Продолжим рассмотрение нашей задачи. Размещая
одного ферзя за другим, мы, в лучшем случае, размес-
тим последнего (восьмого) ферзя и сможем вывести
(например отпечатать) получившуюся расстановку фер-
зей. Однако в ином случае, исчерпав все варианты рас-
положения очередного (скажем, i-ro) ферзя, то есть не
сумев его поставить на доску, мы должны будем вер-
нуться на ход назад и перейти к следующему варианту
расстановки предыдущего ферзя, (t—1)-го. Ясно, что
для этого нам придется вспомнить последний рассмот-
ренный вариант установки (i—1)-го ферзя. И затем,
увеличив номер варианта, продолжить просмотр вариан-
тов установки этого ферзя.
В этих движениях вперед и назад по номерам ходов
и состоит особенность схемы перебора, которая не укла-
*) То есть яа квадратной клетчатой доске размером 8X8 так,
чтобы никакие два ферзя не стояли на одной вертикали, горизон-
тали или диагонали.
69
PWt
PRPt.
шапка программы
VA'CHti
ZAPv
ZAP:
дыгается в готовую схему цикла (однократного по I
или двукратного по I и /) обычных языков программи-
рования.
Подытожим грубо наше рассмотрение. Мы движемся
вперед, увеличивая номер хода. Для каждого (оче-
редного) хода движемся вбок, подбирая допустимый
вариант, и переходим вперед к следующему ходу, если
вариант подобран. Если вариант подобрать нельзя, то
мы возвращаемся на ход назад и продолжаем дви-
жения вбок, начиная с последнего варианта, рассмот-
ренного на этом ходе. Это записывается в блок-схеме
и блок-программе (рис. 5.1). (Заметим только, что блок-
схема дает лишь представление о последовательности
работы разных разделов программы, в то время как
блок-программа является точной программой.);
60
S4: шапка программы
NACH: fc«Oi начальная подготовка;
PER: fc-f+l; И i>n then goto ZAP;
fi—0; подготовка вариантов;
ВОК: if £>/n then goto ZAD;
образование очередного варианта;
PRV: if (вариант: недопустим)
then goto SOK;
PR^: прописка влрианпа;
goto ₽£?;
ZAP: запись очередного решения;
ZAD: 1; if <»0 then goto VSJO;
VYP: выписка последнего варианта и хода; -
восстановление текуиого варианта
предыдущего хода;
goto ВО Ki
VSJO: окончание программы
Ряс. 6.1. Блок-программе перебора
Наша блок-программа является самой общей, при-
годной для любой задачи перебора, а блоки, к которым
она обращается, зависят от конкретной задачи. В зави-
симости от сложности возложенных на них функций они
могут реализоваться несколькими командами, помещен-
ными в саму блок-программу (чего, однако, лучше не
делать), или представлять подпрограммы, которым пе-
редается управление. Могут быть они и законченными
процедурами (для алгола) или SUBROUTINE (для
фортрана).
1. Чтобы легче разобраться в блок-программе, нач-
нем с простейшего способа решения задачи о расстанов-
ке ферзей и посмотрим, какой получатся ее блоки и вся
программа. Именно: обозначим клетки доски (как
это принято в шахматах) парами чисел (х, у), где х —
номер вертикали и у — номер горизонтали. Упорядочим
поля по вертикалям, а внутри вертикали — по горизон-
талям. И будем пытаться ставить очередного ферзя
на поля доски, рассматривая их в таком порядке:
(1.1), (1.2)..(2,1), (2,2),. . .
Договоримся об обозначениях. Возьмем доску раз-
мером А X В, N ферзей и положим 4 = В = Л' = 8. Это
61
делается для ясности программы. Для Записи положения
ферзей заведем два массива X и У по Л/ элементов каж-
дый. Общее число найденных вариантов обозначим бук-
вой k. Договоримся еще об одном обстоятельстве. Мы
бы не хотели считать разными позиции, в которых фер-
зей поменяли местами. Поэтому второго ферзя начнем
пытаться ставить не с ноля (1,1), ас поля, следующего
за полем (Х[1], У[1})> на котором уже находится пер-
вый ферзь. Стоит заметить, что порядковым номером
поля (х, у) будет j—B*(x—1)-Ну и что последнее поле
будет иметь номер j=A*B.
Теперь рассмотрим получившуюся блок-программу и
напишем ее блоки.
SH: Шапка программы сильно зависит от языка про-
граммирования. В алголе в нее помещается описание
объектов, нужных в программе. Поэтому ее следует
лишь начать и продолжать дописывать по мере появле-
ния объектов:
begin com FERZIA*.
' int i, j, Л, B, N,. m,
• —8; т;==Д*В;
begin int array X, K[l:Af]:
Далее пока пойдет строка
Z:=0;
Вся «начальная подготовка» свелась к одному операто-
ру,. обнуляющему число k найденных решений (но надо
не забыть внести переменную к в описания}.
Раздел «вперед» начинается просто:
PBR*. И i>$ then goto 2ЛР*.
if Z=1 then /:=0;
Далее в бдок-программо идет «подготовка вариантов»/
Здесь она должна быть такой, чтобы в разделе ВОК
образовался первый вариант размещения /-го ферзя.
Значит, в «подготовке вариантов» надо в (Х|/|, У|Д)
записать поле, предшествующее первому варианту.
Если t=l, то для этого удобно взять фиктивное поле
(1,6), за которым действительно следует (1,1), а если
i>l, то можно взять поле, где стоит (/—1)-й ферзь. Та-
ким образом, получаем часть программы:
И t=i then {XfИЧ—Ф
eke (ад:=Х(г-4]; ‘ <
62
Далее идет раздел BOKi
BOX'- /:=/+1. if i>m then goto ZAD:
Образование «очередного варианта» можно сделать
так:
jl Y\i}<B then Уи]:=Г[«1+1
else УЩ:=1};
Проверку допустимости (выбранного положения фер-
зя г) лучше оформить., булевской процедурой NEDOP,
Тогда этот раздел в программе будет иметь, вид
PRV: If NEDOP then goto ВОК
Прописка варианта у нас произошла автоматически, по-
скольку мы его сразу занесли в X (t], У[<}, но не для
всех алгоритмов это удобно. В данном же случае оста-
ется только перейти к метке PER:
PRP: goto PER.
Запись очередного решения состоит в его печати и
увеличении числа k найденных решений. Например, таю
ZAP-. *:=*+!: NSP: print(k)
for p+1 while p^N do
рлп/(Л[р], Г[р],
Напомним, что NSP есть переход на новую строку пе-
чати.
ZAD: 1; if />0 then
+ У[/]; goto ВОК}-,
VSJO: NSP: print(‘variantov', ,k)
При движении назад, нам понадобилось восстановить
в ; номер последнего варианта предыдущего хода. Во-
обще же возврат назад — наиболее сложный раздел
программы перебора. Двигаясь вперед, мы перерабаты-
ваем информацию о позиции, и бывает трудно одно-
значно восстановить предыдущую. Вопрос этот автома-
тически решается при рекурсивной организации про-
граммы. Но тогда при движении вперед приходится пе-
реписывать столько информации, что скорость работы
становится недопустимо низкой для программирования
игр.
. Остается написать процедуру проверки, бьется ли
поле i-ro ферзя предыдущими ферзями:
bool proc NEDOP: . ..
begin NEDOP:=false: .
for p1 step 1 until i—1 do
ea
if ХЫ~ХН|Г[Р1-П']
I Г[р]—X[pl=r[^J—XIZ1
И[р]+Х[р]«Г(/1+Х[/1 then
{MEDOP «true goto VYH\ VYH:
end MEDOP\
Сначала проверяется, не стоят ли ферзи р и I на
одной вертикали, потом — на одной горизонтали, по-
том—на восходящей диагонали (слева снизу — направо
вверх) и, наконец, —на заходящей диагонали (слева
сверху — направо вниз).
Вся программа окончательно приобретает вид
FERZ1-X.
begin com FER7.IA:
int Z, /, 4, В, /V, m, k. p;
А==В:=ЛЛ=8; m==A*B-
begin int array I
boo! proc MEDOP:
begin MEDOP =4a*se
for p:=l step I unfit /—1 do
if X[p]« M/JI Г[Р1 « ГЫ
V[/|
|ГЫ+Др1=КИ+*И then
{NEDOP;~true. goto VYH} VYH:
end NEDOP:
NACH: i;=>d; fe:=0:
PER: i:=i+l; i? i>N then goto ZAP;
it 4=1 then /:=0
If Z=1 then (X[t) =1; Г(1 ] =0}
else {X[/j.=X{i-1|. rUWU-tn;
BOK: j:—iif j>m then goto ZAD,
if Y\i\<B then r(ij:=n«l+l
else {X[/]:=JWJ+« H<! = 41
PRV: if NEDOP then goto BOR;
PRP: goto PER;
ZAP: k;=k+l; NSP- print}*};
for p:= 1, p + I white p^N do
Printm,Y[p], ‘_J):
ZAD: Z:=i-1. If i>0 then
{/:=B«(XU]-1) 4- H<L goto BOR};
VSJO: NSP; prini(‘varianlov', k)
end end FERZ1-};
Программа эта верна. Она помогла нам разобрать
блок-программу перебора. Но на этом ее полезность
64
кончается. В среднем нового ферзя мы пытаемся поста- '•
вить на 32 поля. А это грозит привести к 832« Ю30 ва-
риантам (!). Бросается в глаза, что если очередной ферзь
не установлен в очередной вертикали, то все ферзи заве-
домо не разместятся, и мы будем продолжать бессмыс-
ленную работу.
2. Чтобы ускорить работу программы, будем ставить
i-ro ферзя на i-ю вертикаль. Тогда число вариантов не
превысит 88 = 224 « 108 (на самом деле менее 104), что
уже приемлемо.
Блок-программа, разумеется, сохранится. Выпишем
участки, которые надо переделать. Мы откажемся от
массива X и всюду заменим X[i] на L Массив У, как это
принято в шахматах, назовем именем POZA, а для крат-
кости записи текущие действия будем выполнять не с
POZA [i], а с переменной / (которая теперь равна
PQZA(ij). Зато теперь появится содержание в разделе
^прописка»— там будет занесение / в POZA[iJ. Раздел
«запись» упростится, а. в разделе ZAD появится зане-
сение в / последнего опробованного варианта из
POZA fi]. Программа заметно упростится и примет вид
FERZI-2.
begin com FERZI-2;
int i,j,A,B,N,k,p;
4:=JV:=8; B:=8;
begin int array ®07Л[1
bool proc NEDOP-,
begin NEDOP:=talse;
for p1 step 1 until I—1 do
if POZA[p]—j | POZA[p\-p=j-t~
\POZA[p]+p—j+i then
\NEDOP:=true; goto VYH}; VYH:
end NEDOP-,
NACH-. i:=0; fe=0;
PER: »:=Z+r. if i>N then goto ZAP;
Г.=0;
BON: j:=l+l; if j>B then goto ZAD;
PRV: if NEDOP then goto BOR;
PRP: POZA[i]:=j; goto PER;
ZAP: k:=k+l; NSP; print(k, POZA);
ZAD: i:=i— 1; if i=0 then goto VSJO;
j:=POZA[i]; goto BOR;
VSJO- NSP; print^oarlantov', k)
end end FERZI-2;
3 А. Л, Брудно, Л. II. Каплан
85
3. Стоит подумать об ускорении процедуры NEDOP.
Мы сравниваем положение f-ro ферзя со всеми преды-
дущими. Это грозит затратой w действий. Не лучше ли
будет при установке очередного ферзя отметить поля
доски, на которые он бьет, и тогда в одно действие по-
смотреть, осталась ли свободной клетка, на которую
мы собираемся поставить нового ферзя. Оказывается,
нет. И дело здесь даже не в том, что на отметку полей
всех ферзей уйдет A*N действий. Важнее, что при ходе
назад или вбок нам будет трудно снять метки с осво-
бодившихся полей — ведь поле могло биться не толь-
то тем ферзем, которого мы снимали, но еще и дру-'
гими.
Выход из затруднения состоит в следующем. Заведем
три массива GOR, VOS, ZAK для списков горизонталей,
восходящих и заходящих диагоналей. И при установке
очередного ферзя мы сможем в три действия отметить
занятые горизонталь и две диагонали. А при попытке
установить нового ферзя сможем в три действия прове-
рить, свободно ли поле. Важно заметить, что при дви-
жении назад мы также легко можем исправить эти мас-
сивы— ведь на данной горизонтали или диагонали мо-
жет находиться лишь один ферзь!
Новый вариант программы (см. программу FERZI-3)\
потребует введения трех булевских массивов, которые
нужно будет очистить в разделе NACH. В процедуре
NEDOP исчезнет цикл, и она упростится настолько, что
ее оператор проще будет поместить в раздел PRV (про-
верка). Но усложнится PRP (прописка). Здесь появится
занесение отметок в массивы GOR, VOS и ZAK о том,
что заняты горизонталь и две диагонали той клетки,
куда установлен новый ферзь. И последнее — в разделе
ZAD (возврат назад) появится снятие отметок о заня-
тости в этих массивах.
begin com FERZI-3;
int f, /, Л, В, k, p\
B:=8;
begin int array POZA[1: #];
bool array GOR[\: В],УО8[1-Л: В-1],2ЛК[2 : В+Л];
NACH: Z:=0; Лг:===О;
for p:=l, p+1 while p<B do GO7?[p]:= false;
for p:= 1— Л, p+1 while p<B—1 do VOS[p]:= false;
for p:=2, p+1 while р<В + Л do ZAK{p]\— false;
PER: if i>N then goto ZAP;
ВОК: /:=/+1; if j>B then goto ZAD;
PRV: if GO/?(/J | V0S[/-7] I ZAKU+i]
then goto ВО К
PRP: GOR[j]:—VOS[j—i]:=ZAK[jA-i]:= true:
POZA[i]:=j; goto PER;
ZAP: k:=k+l; NSP; print(k,POZA);
ZAD: i:=i— 1; if z=0 then goto VS JO;
j:=POZA[l];
GORU]:=VOS[f-i]:=ZAKl/+il~ false;
goto BOK;
VS10: NSP; print('variantov', k)
end end FERZI-3;
4. Полученная программа настолько удовлетвори-
тельна, что Дейкстра *) на ней и остановился. Все же
один ее недостаток бросается в глаза: устанавливая по-
следнего ферзя, мы пррбуем все 8 полей, тогда как
свободным могло остаться лишь одно. Чтобы избежать
этого и тем значительно ускорить вычисления, мы за-
ведем список свободных горизонталей, и будем пытаться
ставить очередного ферзя только на поля из этого спи-
ска. Подчеркнем, что образование списка вариантов
i-го хода является приемом мощным и достаточно об-
щим для применения в различных конкретных задачах.
'Выигрыш от него покрывает издержки на расход места
для этого списка и на действия, нужные для его под-
держания. Заметим все же, что список-свободных гори-
зонталей не является списком полей, куда можно поста-
вить i-го ферзя (так как эти поля могут биться по диа-
гоналям) , но он сокращает число проб.
Что касается места, то оно у нас есть. Это (на
i-м ходе) — ячейки массива POZA, начиная с t-й и до
конца. Нужно будет только взять массив POZA дли-
ною В и вначале заполнить его списком свободных (т. е.
всех) горизонталей:
, POZA [i] :=/ для i— 1,2, .... В.
Но нужно поддерживать этот список. При движении
вперед это выполняется легко. Найдя на t-м ходе в
массиве
POZA[l], ..., POZA[i],POZA[i+l], .... POZA [B]j
♦) Дал У., Дейкстра Э., Хорр К. Структурное программирова-
ние.— М.: Мир, 1975.
3* 67
на некотором месте ]"^i подходящую для i-ro ферзя
горизонталь POZA [/], мы меняем местами значения
элементов POZA[i] и POZA[j] и тем самым выполняем
и прописку ферзя i, и образование нового списка сво-
бодных горизонталей (начинающегося теперь с элемен-
та i + 1 массива POZA).
Трудность возникает при движении назад, когда нам
надо будет вернуть значения POZA [f] и POZA [/] на
свои места, чтобы восстановить порядок рассматривае-
мых вариантов. Предвидя это, заведем массив Z[l^]
и будем при движении вперед вписывать в элемент* Z[f]
номер выбранного варианта / хода I. Благодаря этому
при движении назад на ходе i мы прочтем в ячейке Z[i]\
число /, и сможем вернуть на свои места значения
POZA[i] и POZA[j],
5. Все это приводит к программе FERZI-A. Разберем
се на основе блок-программы перебора, не ссылаясь на
предыдущие программы.
begin com FERZI-4;
int Щ,А,В,Н,к,р;
A=V:=8; B:=8;
begin int array POZA[\ :B], Z[1: V];
bool array : B-l], ZAK[2 : В+Л];
NACH: Z:=0; A>:=0;
for p'~ Г, p+1 while p^B do POZA[p]:—p;
for p:==l—Л, p+1 while p<B—-1 do VOS[p]:= false;
for p:=2, p+1 while p<B+A do ZAK[p]:= false;
PER: z:=/+l; if i>2V then goto ZAP;
BOK: /:«/+!; if j>B then goto ZAD;
p:=POZA[j];
PRV: if VOS[p-i] | ZAK[p+i] then goto BOR;
PRP: VOS[p~z]:=Z4K[p+/]:==true;
POZA[j]:—POZA[i]; POZA[i]:=p;
Z[i]:~f; goto PER;
ZAP: k:=k-pl; NSP; print (k, POZA);
ZAD: /:==/—1; if i=0 then goto VSJO;
VYP: j:=Z[i]; p:=POZA[i];
POZA[t]:~POZA[j]; POZA[j]:=p; .
VOS[p—z]:=Z4X[p+z]:== false;
goto BOK;
VSJO: NSP; print^variantov", к)
end end FERZ1-4;
SH: Шапка программы сильно зависит от языка
программирования. В алголе здесь нужно поместить
описания и заранее можно описать переменные А, В —
число вертикалей и горизонталей доски, N — число фер-
зей, i и j — номера хода и варианта. В нашем алгоритме
обязательно N=A и надо положить A—N=B=8. Сле-
дует описать два целых массива: массив POZA
для записи номера горизонтали ферзя, стоящего на дан-;
ной вертикали, и для записи, списка свободных горизон-
талей и массив Z[1 :N] для записи номера j последнего
варианта, рассмотренного на ходе i. Надо описать и
два булевских массива:
VOS[1—А:В—1]—для списка диагоналей у—х=
—const,
ZAK[2:B-j-A]—для диагоналей t/-f-x=const.
В них будет отмечаться, свободна ли данная диа-
гональ.
Остальные объекты будут внесены в описание по мере
их появления в программе. Правило это важное, так как
никто не может предвидеть всех объектов, которые ему
понадобятся. Поэтому хотя описания стоят в начале про-
граммы (блока), но дописывается эта часть последней.
И тот, кто этого не знает, затрудняется писать на алголе.
NACH: Первоначальная подготовка. Здесь обнуля-
ются i и k (переменная k служит для подсчета числа
расстановок ферзей). Массив POZA заполняется спис-
ком свободных (то есть всех) горизонталей, массивы
(VOS и ZAK очищаются числом false.
PER: Номер хода увеличивается; если он превосхо-
дит число ферзей, то расстановка найдена. Иначе поиск
расстановки следует продолжить и номер / варианта
(предварительно) делается равным i—1 с таким расче-
том, чтобы в разделе ВОК он стал равен номеру i, с
которого в массиве POZA начинается список свободных
горизонталей для хода i. Напомним, что номер варианта
не должен быть обязательно его порядковым номером —
лишь бы варианты были упорядочены по возрастанию
своими номерами (у нас здесь номера вариантов хода i
суть j—i, i-j-1, ...).
ВОК: Здесь увеличивается номер варианта j хода I,
и если варианты исчерпаны, то следует идти назад.
В переменную р, для краткости, заносится номер очеред-
ной свободной горизонтали.
PRV: Проверяется, бьется ли клетка (i, р) предыду-
щими .ферзями (с номерами меньше г). Если бьется, то
оа,
надо идти вбок. Если не бьется, то — к прописке ферзя I
на горизонтали р.
PRP: Прописка. Отмечается занятость двух диагона-
лей в массивах VOS и ZAK. В элементе POZA [/] запи-
сывается номер р горизонтали, занятой ферзем г, а сво-
бодная горизонталь, записанная раньше в этом элементе,
переносится в элемент POZA [/], откуда был взят но-
мер р. Это должно работать верно (то есть не делать
ничего) и в случае i—j. Наконец, в Z[i] запоминается
номер варианта /.
ZAP*. Печатается найденный вариант расстановки п
его порядковый номер k.
6. Мы рассмотрели 4 варианта программы расста-
новки ферзей. И на этом можно остановиться. Но игро-
вую программу почти всегда удается усовершенствовать.
Можно, например, заметить, что программа FERZIA
рассматривает свободные горизонтали в порядке, зави-
сящем от уже выбранных. Читатели, которые захотят
рассматривать горизонтали в фиксированном порядке,
могут познакомиться с более трудной программой
FERZbb.
begin com FERZl-Ь;
Int A, B, N, i, j, k, p;
Л:х=ЛГ:==$; B:==8;
begin int array POZA[l :N], Z[0: BJ;
bool array VOS[l-4 : В—1], ZAR[2 : В+Л];
NACH: for £:=0, while k^B do
for k+l while k<B do false;
for &:=2, &+1 while k^B-^A do ZAR[k]:= false;
PER: if i>N then goto ZAP; p:=Q;
BOR: j:=p; if p>N then goto ZAD;
PRV: if VOS[p-z] I ZAR[p+i] then goto BOR;
PRP: VOS[p-i]:=ZAR[p + Z]:=true;
Z[j]:=Z[p]; Z[p]~j; POZA[i]:=p;
goto PER;
ZAP: NSP; print(kJPOZA);
ZAD: 1; if f=0 then goto VSJO;
VYP: p:—POZA[i\; j:=Z[p]; Z[p]^Z[j]; Z[j]~p;
VOS[p—i]:==ZAR[p+i]:==ialse;
goto BOR;
VSJO: NSP; print(*variantov\k)
end end FERZI v porjadke variantov;
В программе FERZl-Ъ также четыре массива: POZA,
VOS, ZAK и Z. Но в Z[j] помещается номер горизон-
тали, которую следует рассматривать после рассмотре-
ния горизонтали / (если горизонталь / осталась свобод-
на). Если же горизонталь / заняли ферзем, то в Z[j]\
заносится номер горизонтали, которая была рассмотре-
на последней перед горизонталью / и осталась сво-
бодной.
Вначале массив Z[0: В] заполняется номерами го-
ризонталей так, чтобы первой рассматривалась горизон-
таль Z[0], второй — Z[Z[0]], а следом за послед-
ней рассматриваемой шла фиктивная горизонталь В+4,
Например, так:
для 0^/<В.
Попытка установить очередного ферзя i всегда начина-
ется с горизонтали Z[0]. Если она не удалась, то по-
следовательно рассматриваются горизонтали Z[Z[0]],
Z[Z[Z[0]]] и т. д. Если, наконец, ферзя i удалось уста-
новить на горизонталь p=Z [/], то делается следующее:
Z[/]:=Z[p];
ибо в дальнейшем после горизонтали / должна будет
рассматриваться горизонталь Z [р], и далее
Z[p]:=/; POZA[i\. — p\
При движении назад все возвращается к исходному
состоянию операторами
p:—POZA[i]; j:=Z[p];
Z[p]:=Z[j]; z[j]:=p;
Остальное выполняется так же, как и в программе
FERZI-4.
ZAD: Движение назад. Номер хода уменьшается на _1:
и проверяется, не окончена ли задача.
VYP: Выписка. Все возвращается к такому состоя-
нию, которое было при образовании последнего вариан-
та расположения ферзя i до его прописки.
VSJO: Печать числа вариантов.
7. Посмотрим, сколь универсальна наша программа.
Она без изменений идет при любых значениях А, В, N
при условии, что
A=N^B.
Переделка программы на случай N А В предостав-
ляется читателю.
71
'Для решения задачи .80.1.2 о перестановках доста-
точно убрать массивы VOS и ZAK.
Решение других наших задач на частные случаи пе-
ребора тоже не вызывает сложных переделок.
W 1
W
W
W
W.
W
W
W
W
иг
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
Рис. 5.2
И все же основное содержание этого параграфа в ।
блок-программе перебора и в том, чтобы научиться ею |
пользоваться. J
Задачи. 1. Какими способами можно обойти доску I
6X6 шахматным конем по замкнутому пути, который |
совмещался бы с собою при повороте доски на 90°?. а
72
2. Переделайте программу FERZI так, чтобы она
печатала и считала только те позиции, которые нельзя
перевести друг в друга поворотами и зеркальными от-
ражениями доски. Их всего 12 (рис. 5.2),
§ 6. РЕТРОСПЕКТИВНЫЙ АНАЛИЗ
Есть задачи, в которых перебор оказывается безна-
дежно долгим, а анализ ситуаций, начиная с заключи-
тельных, быстро приводит к цели.
1. Вот самая известная задача такого рода. Два
француза решили выяснить, не являются ли они пря-
мыми потомками по мужской линии короля Карла Ве-
ликого. Были у них все метрические архивы. Первый
француз начал с Карла Великого. У короля было 11 сы-
новей. У сыновей снова были сыновья..., и к концу дня
первый француз выяснил, что не сможет закончить ана-
лиз за всю свою жизнь. А второй француз начал с себя,
нашел в записях своего отца, потом его отца... и в тот
же день закончил работу.
2. Вот более трудная задача. Она из сказочных
шахмат.
Неприкасаемый король. У белых король и
ферзь, у черных —один король. Могут ли белые выиг-
рать, не делая ходов своим королем, стоящим на поле
сЗ?
Эта задача, была известна'еще в прошлом веке, но
явилась первой шахматной задачей, решенной машиной
раньше, чем людьми. Впрочем, зная, что решение есть,
человек находит его за 1---2 часа.
2.1. Попытаемся решить задачу перебором. У белых,
как правило, больше 20 вариантов хода, у черных —
примерно 5. Вариантов ход-ответ более 100. А всего
вариантов просмотра на глубину в 20 ходов-ответов
получается более 10020 = 1040. Если машина будет про-
сматривать миллиард (109) позиций в секунду (что уже
не реально), то анализ займет миллиарды миллиардов
лет (напомним, что возраст галактики менее 100 мил-
лиардов лет). Попытка явно не удалась.
2.2. Можно, однако, заметить, что всего позиций не
так уж много. У белого ферзя менее 64 положений, у
черного короля — тоже. Всего положений (считая и не-
возможные) 4096, а с учетом очереди хода .8192. Значит,
сведения о них можно поместить в память машины. .
73
Введем понятие о ранге позиции.
Ранг позиции — это число ходов, которые должны
сделать белые, чтобы дать мат.
Заведем два четырехиндексных массива!
ВР, СР [1:8, 1:8, 1:8, 1:8],
Индексы Г, Е, К, Р элемента BP[F, Е, К, Р] и элемента
CP[F,E,K,P] будут обозначать:
F и Е — номера вертикали и горизонтали, где стоит
белый ферзь,
К и Р — то же для черного короля.
В самих элементах этих массивов будут записываться!
BR — ранг позиции, если ход белых,
СР — то же, если ход черных.
2.3. Теперь решение состоит в заполнении массивов.
Сначала отмечаются невозможные позиции, маты, паты
и другие ничьи (король съел ферзя). Для матовых по-
зиций в СР, естественно, заносится 0.
Далее, для каждого i = 0,1, ... делается следующее.
(1) Просматриваются все позции (F, Е, К, Р), еще не
имеющие ранга ВР. Если из такой позиции можно пойти
ферзем в позицию (Fl, £1, К, Р), где СР равно i, то
в BP [F, Е, К, /?] заносится Н-1.
(2) Просматриваются все позиции (F, Е, К, RJ, еще не
имеющие ранга СР. Если из такой позиции все ходы
королем ведут в позиции, уже имеющие ранги ВР, то
в CP[F, Е, R,P] заносится число i-f-1-
Фактически это можно сделать экономнее, но для
нас сейчас важно только принципиальное решение.
2.4. Работа заканчивается, когда при очередном зна-
чении i не появится новых значений в элементах ВР.
Если все позиции получили ранги ВР, то мат всегда
возможен, если не все — то не всегда. Так, было выяс-
нено, что при белом короле на сЗ мат дается не позже
23-го хода.
2.5. После того как массивы заполнены, можно напи-
сать программу игры человека с машиной. Если машина
играет белыми, то делает очередной ход ферзем так, что-
бы ранг СР новой позиции был на единицу ниже ранга
ВР исходной позиции. Если же машина играет черными,
то делает ход королем в позицию с максимальным ран-
гом ВР. Любопытно, что эта тактика черных создает
человеку, играющему белыми фигурами, наибольшие
трудности.
U
Чтобы не отыскивать каждый раз нужные ходы, для
них удобно завести два четырехиндексных массива ВН
и СН (белых ход и черных ход). Если в позиции (F, Е,
K,R) ферзь должен пойти на' (P.El), то в ВН (F,E,K,R)
удобно записать число 10 * El -f-El. Если в этой позиции
черный король должен пойти на поле (7<1,Е1), то в
CH(F, Е, К, R) записывается 10«К14-/?1. Массивы ВН
и СН удобно заполнять одновременно с заполнением
массивов BR и CR.
2.6. Для, тех, кто захочет написать эти программы,
приведем числа, которые удобно предварительно зане-
сти в массивы и которыми удобно отметить особые по-
зиции:
Позиция BR ВН CR СН
предварительно 60 90 60 90
шах 00 90
съел ферзя | 50 90 50 90
ем ферзя ' 00 90 50 10*F+£
недопустимо • 00 90 00 90
мат 1 00 90 00 90
пат 50 90
3. Недавно с помощью ретроспективного анализа
было установлено, что король с двумя слонами всегда
выигрывает у короля с конем.
§ 7. ЧЕТЫРЕ ЗАНИМАТЕЛЬНЫЕ ЗАДАЧИ
ПО КИБЕРНЕТИКЕ
Это — лекция, прочитанная школьникам. Задачи,
приведенные в ней, известны*), но наши решения отли-
чаются от опубликованных.
1. Артиллерист и пехотинец. Артиллерист А
ведет огонь по пехотинцу, который может укрываться
в любом из пяти окопов В1,В2,Вз,В4,В5, расположен-
ных, как показано на рис. 7.1. В каком окопе укрыва-
ется пехотинец, артиллеристу не видно. Артиллерист
может стрелять в промежуток между любой парой со-
седних окопов, и пехотинец будет поражен, если ока-
жется в одном из них.
\
*) См.: Гарднер М. Математические новеллы. ^М.: Мир, 1974.
75
Требуется определить, как вести себя пехотинцу и!
артиллеристу, если: >
а) пехотинец хочет иметь максимальный шанс из-
бежать поражения в наихудшем для него случае;
б) артиллерист хочет иметь максимальный шанс по-
разить пехотинца в наихудшем для артиллериста;
случае.
Это — типичная игровая задача оптимального пове-
дения. Если, например, пехотинец решит укрыться в Bj
Д5* -
"а
Вг*
Bi
Рис. 7.1
то (в худшем для Пехотинца случае) артиллерист мо-
жет решить выстрелить как раз между В\ и В2. Так же
невыгодно и артиллеристу решать заранее, куда он бу-
дет стрелять. Поэтому надо решать задачу с помощью
случайной стратегии, открытой Дж. Нейманом.
Есть в этой задаче и ловушка: может показаться,
что окопы В\, В$ равноценны и безопаснее равноценных
же окопов В2, В3, В*, которые поражаются выстрелами
по двум прицельным точкам. Несмотря на простоту за-
дачи, Р. Айзекс нашел ее достаточно интересной, чтобы
начать с нее курс «Оптимального поведения» для офи-
церов. Впрочем, решение у него сложнее, чем будет
у нас.
1.1. Прежде всего, должно стать ясно, что пехотинцу
можно не пользоваться окопом В2. Действительно, вся-
кий выстрел, поражающий Bit поразит и В2. Поэтому
положение пехотинца не ухудшится, если он заменит
укрытие в окопе В2 на укрытие в Bi. Аналогично обстоит
дело с окопом В^.
1.2. Итак, остаются окопы В\,В2, В$, в которых мо-
жет укрываться пехотинец, а артиллерист может пора-
76
зить одним, выстрелом любой ИЗ ЭТИХ ОКОПОВ, НО ТОЛЬКО1
'ОДИН.
1.3. Равноценность окоп'ов подсказывает такое реше-
ние. Пехотинец случайным и равновероятным образом
выбирает один из трех окопов: В\, В3, В5. Артиллерист
тоже случайным и равновероятным образом выбирает
одну из трех целей: между Bi и В2, между В3 и В4 или
между В4 и В3 (вместо, цели между В3 и В4 годится
цель между В2 и В3). Чтобы сделать равновероятным
выбор между тремя возможностями, можно, например,
бросить игральный кубик: если выпадут 1 или 2 очка,
то остановимся на первой возможности; если 3 или
4 очка, то — на второй, а если 5 или 6 очков, то.—на
третьей. -
При таком решении вероятность, что пехотинец оста-
нется невредимым равна 2/3, а вероятность, что артил-
лерист поразит пехотинца равна 1/3.
1.4. Это — решение задачи. Действительно, при дру-
гом поведении пехотинца он попадет в одну из трех си-
туаций:
Bi или В2; В3; В4 или В3 («у
с вероятностью выше 1/3. Ив неудачном для пехотинца
случае артиллерист может выбрать цель, при которой
пехотинец будет поражен в этой ситуации. Аналогично,
невыгодно в поставленных условиях отклониться от ре-
комендованной ему тактики и артиллеристу — иначе в
одном из случаев («) пехотинец будет поражаться с ве-
роятностью менее 1/3 и может выбрать как раз этот
вариант.
2. Тройственная дуэль. Три человека, назо-
вем их А, В и С, устроили дуэль по следующему пра-
вилу. Они бросают жребий, который равновероятно вы-
дает им номера 1, 2 и 3. После этого они поочередно
стреляют в порядке своих номеров: № 1, № 2, № .3,
№ 1, № 2, ... Каждый раз стреляющий выбирает, в кого
он будет стрелять, а убитый, естественно, выбывает из
очереди. Дуэль продолжается, пока не останется в жи-
вых только один из участников.
Требуется найти для каждого дуэлянта оптимальную
тактику поведения и вероятность остаться в живых,
если А убивает противника наверняка, В — в 80 % слу-
чаев, а С — в 50 %, и участникам дуэли это известно.
2.1. Сначала рассмотрим более простую дуэль двух
противников, назовем , их Р и Q, которые попадают, с
77.
'вероятностями р и q соответственно. Пусть они тоже
стреляют поочередно, причем первым стреляет Р. Обо-
значим вероятность его выигрыша (в этих условиях)
через х. Для вычисления х будем различать два несовме-
стимых события: того, что Р попадает первым выстре-
лом, и того, что и Р, и Q вначале промахнутся. Вероят-
ность первого события равна р, а второго — равна
|(1—р)(1 — q). В первом случае вероятность выигры-
ша Р равна 1, а во втором— снова равна х. Таким об-
разом,
х=р.1 + (1— р)(1 — q)x.
Откуда
л~ 1-(1 -₽)(!-<?) •
Если первым стреляет Q, то вероятность у выигрыша Р
будет равна произведению вероятности того, что Q про-
махнется, на вероятность х того, что после этого выиг-
рает Р;
y = {l-q)x= .
Так что y<ix, и поэтому пропускать свой выстрел при
дуэли двух противников невыгодно.
2.2. Вернемся к тройственной дуэли А, В, С и объ-
явим заранее оптимальную тактику: пока есть три дуэ-
лянта, А и В должны стрелять в сильнейшего против-
ника (то есть друг в друга), а С должен стрелять в
воздух. При этом вероятности выигрыша дуэли для А, В
и (?, как мы покажем, будут соответственно равны
0.3, 0.177..., 0.522...
Таким образом, лучшие- шансы имеет худший стре-
лок (!).
2.3. Докажем, что при предложенной нами тактике
.вероятности выигрыша действительно будут указанны-
ми. Пока дуэлянтов трое, участник С стреляет в воздух.
Поэтому события распадаются на две группы с вероят-
ностями pi=l/2 и р2=1/2: стрельбу начинает А или В.
Если начинает А, то он убивает В и продолжает
дуэль с С. Начинает ее С, и он либо попадает й выиг-
рывает, либо промахивается (с вероятностью р3=1/2),
и тогда наверняка выигрывает А,
78
Если начинает В, то либо он промахивается (с ве-
роятностью р4=1/5), либо попадает (ps=4/5). В пер-
вом случае возникает уже рассмотренная ситуация с
вероятностью выигрыша для А, равной р6=1/2. Во вто-
ром случае возникает дуэль между В и С, в которой В
стреляет вторым. Дуэль двух лиц мы уже подробно рас-
смотрели и находим, что В имеет шансы на выигрыш
с вероятностью р?, равной (р=4/5, <7=1/2):
_ (1 — <?) р_____4
Р1 1 - (1 - р) (1 - <?) — 9 •
Итак, вероятность выигрыша для А равна
Ра=Р1Рз+Р2Р4Р6=3/10.
Для В она будет равна
Pb=P2PsP7=8/45.
Для С она равна тому, что осталось от единицы:
Рс=1— рд—Рв=47/90.
2.4. Остается показать, что предложенные тактики
действительно оптимальны. ;
Для С это просто. Если он не пропустит свою оче-
редь и попадет в А (в В стрелять еще хуже), то у него
возникнет дуэль с В, в которой тот начинает. Вероят- ,
ность выигрыша С в этой дуэли равна (р = 1/2, q = 4/5):
„ _ (I - <?) Р _ 1
у 1 — (1 — р) (1 — <?) — 9 ’
что гораздо меньше, чем 1/2 — вероятность выигрыша
при выстрелах в воздух в худшем случае.
Для В это очевидно. Пропустив свою очередь на вы-
стрел или выстрелив в С, он наверняка будет убит сле-
дующим выстрелом А.
Но верно это и для А. Если его очередь стрелять, то
он уберет В и выиграет дуэль с С с вероятностью 1/2.
Если же он пропустит свою очередь, то снизит вероят-
ность выигрыша до 1/10 (с вероятностью 1/5 промах-
нется В, и с вероятностью 1/2 промахнется С)'.
2.5. И последнее: не выгоднее ли А и В заранее сго-
вориться, что они будут сначала оба стрелять в С, а
после устранения С тот из них, у кого оказался больший
номер, сам застрелится. Да, выгоднее, и это очень час-
тый дефект задач теории коллегиальных игр. В ней при- .
ходится предполагать, что участник нарушит договор
79
Хно не-правила игры), когда ему это окажется вы-
годным.
3. Справедливый дележ. Хорошо известен спо-
соб справедливого дележа золотого песка между двумя
участниками. Способ состоит в том, что один участник
делит песок (по своему усмотрению) на 2 кучки, а вто-
рой— выбирает себе любую из них. Как справедливо
разделить песок, если число участников равно л?
3.1. Пояснение. В отличие от предыдущей задачи
способ дележа должен остаться справедливым, даже если
несколько участников сговорятся действовать так, чтобы
увеличить свою долю за счет других участников.
3.2. Не торопитесь читать решение. Попытайтесь сде-
лать задачу хотя бы для трех участников.
3.3. Решение. При «=1 решение тривиально (не
надо делить). Поэтому, решая задачу для п>1 участ-
ников, можно предполагать, что известен способ спра-
ведливого деления песка между п—1 участниками.
Если «>1, то первые п—1 участников (их можно
взять какими угодно) делят весь песок справедливо
между собою, что по предположению можно сделать.
После этого каждый из них делит свою долю по соб-
ственному разумению на п частей и предлагает взять
последнему участнику любую из этих частей.
4. Выбор шара. В урне находится п шаров. На
каждом шаре написано число (все числа различные).
Число « велико и известно заранее, а числа, написан-
ные на шарах,— любые (не обязательно от 1 до п) и
заранее не известны.
Игра состоит в следующем. Играющий выбирает на-
удачу шар из урны, прочитывает на нем число и ре-
шает— берет он этот шар или нет.
Если не берет, то выбранный шар отбрасывается (не
возвращается в урну), и игра продолжается. Играю-
щий выбирает наудачу новый шар, читает на нем число
и снова решает, брать этот шар или нет, и т. д.
Если играющий берет очередной шар, то игра пре-
кращается, и игрок считается выигравшим в том и
только том случае, если на выбранном им шаре ока-
жется самое большое число, среди чисел, написанных
на всех п шарах, находившихся в урне с самого начала.
Требуется указать тактику играющего, при которой
он будет иметь максимальные шансы на выигрыш.
4.1. Пусть, например, шаров «==100, и на первом
выбранном шаре оказалось число 1000. Брать его или
80
нет? Может быть, на следующем шаре окажется число
1000000, а может, 0.000001.
Если решить брать первый же вынутый шар, то ве-
роятность выигрыша будет равна 1/п. Но если десятый
или последний, то она тоже будет равна 1/п. Поэтому
задача может показаться бессмысленной.
Но это рассуждение поверхностно. С каждым сбро-
шенным шаром растут шансы потерять шар с макси-
мальным номером, но растет и информация о шарах,
которые были в урне. Если сброшен шар с числом 5,
то в дальнейшем не имеет смысла брать шары с числами
меньшими, чем 5.
Попытайтесь сами найти тактику, при которой ве-
роятность выигрыша не стремится к нулю, когда число
шаров п стремится к бесконечности (отыскание опти-
мальной тактики представляет математические труд-
ности) .
4.2. Вот тактика, которая дает вероятность выигры-
ша больше 1/4. Пропустим первую половину шаров, за-
помнив максимальное встретившееся число. Затем возь-
мем первый же шар, на котором будет число, больше
запомненного. Эта тактика заведомо приведет к выиг-
рышу, если шар с максимальным числом встретится во
второй половине, а со вторым по величине числом —
в первой. Вероятность такого выпадения при большом п
примерно равна 1/4.
4.3. Поиск оптимальной тактики. Зафиксируем п
и обозначим через а\>а2> ... числа, написанные на
шарах (в порядке убвания), и сами эти шары. Пусть
мы пропускаем первые i шаров, запоминаем максималь-
ное встретившееся число и берем первый же шар с чис-
лом, большим того, что запомнили. Вероятность Р выиг-
рыша складывается из вероятностей таких несовмести-
мых событий:
— шар а2 будет выбран; at останется;
— шар аз будет выбран; ai, а2 останутся и первым
из них встретится ар,
— шар ak будет выбран; аь а2, .... a^-i останутся
и первым из них встретится аг,
(Здесь «выбран» означает выбран среди первых I ша-
ров, а «встретится» — встретится при дальнейшей вы-
борке.) *
81
Вероятность того, что ак будет выбран, равна 1/п
(первых мест z, а всего мест п).
Вероятность того, что при этом а\, а2, .,., аь-i оста-
нутся, равна (/=«—/):
7 7 — 1 / — (fe — 2)
n —in —2‘*’n —(fe —1)
'(для а 1 подходящих мест /, а всего осталось мест п—1;
после этого для а2 подходящих мест /—1, а всего оста-
лось мест п—2 и т. д.). Наконец, среди шаров ai, а2, ...
..., ak-i любой заданный шар окажется первым с ве-
роятностью 1/(&—1).
Следовательно, вероятность Pk того, что шар ak бу-
дет выбран, а шары ai, а2, a*_i останутся, и пер-
вым среди них встретится съ, равна
р _______1 /(7-D ... (7-(fe-2))
k n A-l (n—l)(n —2) ... (n-(fe-l)) ’
что можно записать и так (i/n = x,j/n = у}: 1
р — * У (У — 1/п) ... (у — (А; — 2)/п)
(1 - 1/п) ... (1 - (fe-1)/п) *
Вся вероятность выигрыша Р будет равна
Р=Р24-Рз+ ••• +Р/+ь
При условии, что х постоянно*), получаем
л-1
Рл~>х -k'_ при п->оо,
и можно показать, что
Р->х[у + у2/2 + у^З + ...] при га->оо.
Хорошо известен ряд
ln(l + z/) = z/-z/72 + ^/3- ....
значит,
ln(l-z/)=-[z/+z/2/24- ...}.
Следовательно, при п-*оо предел Р (обозначим его
через Р(х)) равен
Р/х) ——xlnx.
Чтобы найти максимум Р(х), продифференцируем P(x)j
*) На самом деле стремится к пределу, отличному от 0.
32
и приравняем производную нулю:
Р'(х) ——(In х+х/х) =—(In х+1) =0.
Откуда lnx = —1 и х = 1/е. При этом и
Р(1/е)= 1/е = 0.368 ...
Итак, при наилучшем выборе i
i/n^X/e и Р (г/л) ~ 1/е,
нужно пропустить i^n/e шаров, потом взять первый,
больший выпавших, и вероятность выигрыша будет при-
близительно 1/е. Так, при п — 100 надо пропустить
i=37 шаров и Р~0.368.
§ 8. СЛУЧАЙНЫЕ ЧИСЛА
И ЭЛЕКТРОННАЯ ГАДАЛКА
В этом параграфе мы рассмотрим две задачи про-
граммирования: получение случайных чисел и угадыва-
ние задуманного числа.
1. Случайные числа бывают нужды при решении мно-
гих прикладных задач. С их помощью исследуют пове-
дение регуляторов в ответ на случайные отклонения
регулируемой величины. Они употребляются для при-
ближенного решения задач вычислительного анализа.
Бывают они полезны для проверки правильности работы
программы в неожиданных ситуациях. Нужны они в тео-
рии игр и других вопросах.
1.1. Для работы ЭВМ со случайными числами вна-
чале пытались вводить эти числа извне. Вводили в па-
мять готовые таблицы случайных чисел. Строили при-
боры, использующие случайные физические процессы,
например радиоактивный распад,’ и вводящие получен-
ные числа в машину. Все это было достаточно плохо.
Таблицу случайных чисел ЭВМ быстро исчерпывала, а
случайное физическое явление нельзя было повторить,
чтобы проверить вычисления.
1.2. Таким образом, возникла парадоксальная зада-
ча — вырабатывать в самой ЭВМ числа случайные, но
такие, чтобы их можно было повторить и чтобы после-
дующее число вычислялось по предыдущим, .но не зави-
село от них. Задача, разумеется, неразрешимая. Но
Дж. Нейман придумал алгоритм, последовательно вы-
числяющий числа Xi, х2, ..., очень похожие на случай-
ные, равномерно распределенные от 0 до 1. Их называют
83
псевдослучайными, или просто случайными. Сейчас мы f
изложим этот алгоритм.
Метод середины квадрата. Буд^м строить
Четырехзначные псевдослучайные числа. Возьмем произ-
вольное целое ki из диапазона 0 < k\ < 104. Это будет,
наше первое число. Если нам уже известно kti то возве-
дем его в квадрат и возьмем 4 средних разряда. Если,
например, £/ = 2251, то врзведя его в квадрат, получим
= 05067001, и поэтому ki±\ — 0670.
Чтобы получить из нашей последовательности
ki,k2f ... последовательность действительных чисел
хьх2, ..., равномерно распределенных между 0 и 1,
надо положить Xi — ftz/104.
Несмотря на очевидные возражения, вроде того, что
эта последовательность непременно начнет повторяться
или что она может выродиться,в сплошные нули, числа
Xi, х2, ... похожи на случайные. В среднем в половине
случаев хг-<х/+], а в половине — наоборот. Среди пер-
вой тысячи чисел Xi, х2, ... примерно половина будет
меньше 1/2, а половина больше, и т. д.
Разработаны и более сложные способы получения
псевдослучайных последовательностей, препятствующие
обращению членов последовательности в нули и удли-
няющие период ее повторения. Но принцип они исполь-
зуют тот же, и для понимания существа дела достаточно
изложенного.
L3. Напишите процедуру-функцию m(k), доставляю-
щую по k = ki следующее значение т — k^\ четырех-
значных случайных чисел.
Решение.
-nt proc tn (ft); int k\
begin int p, q\ ^:=10**4; &
if k < 1000 then k:=k + 1234;
p;==fc*fc; p:=p-~-100;
m: =p—p-i-q*q
end
Для борьбы с тенденцией обнуления мы ввели преобра-
зование k := k + 1234.
Наши Четырехзначные псевдослучайные числа слиш-
ком быстро начинают повторяться н склонны к обнуле-
нию. Обычно работают с десятизначными числами. На-
пишите такую программу, учитывая, что во всех проме-
жуточных вычислениях числа не должны иметь более
десяти разрядов.
84
Указание. Представьте десятизначное число парой
пятизначных.
Решение. Программа вычисления по заданному
k — kt следующего т = ki+i может быть такой (все пере-
менные описаны как целые) :
д:= 10**5; г:=10**10;
a:=zk-i-q; b:=k—a*.q\
х:=а»а:, y:=2*a*b', z:=b*b;
m:=(x—x-i-q*q)*q+y+z-i-q;
Придумайте сами другие методы получения случай-
ных чисел и запрограммируйте их. Например, метод, ко-
торый строит ki+2 по ki+i и ki. Рассмотрите такой метод
(г = 10**10):
k i+г'. ~7*k i 4. t +3*fe {+123456789;
ki+2‘.=ki+z—ki+2-r-r*r,
В нем надо начинать с двух десятизначных чисел, и он
будет давать числа от 0 до 1010.
Составьте алгоритм, подающий случайным образом
числа Г, 2, 3, 4, 5, 6, взамен бросания игрального кубика.
Указание. Можно рассмотреть наши случайные
четырехзначные числа и вычислить 6 * kt -г- 10 »* 4 -f-1.
Случайные числа можно использовать для прибли-
женного интегрирования. Пусть (х>, yi) ~ пара независи-
мых случайных чисел, равномерно распределенных на
интервале от 0 до 1. Пусть функция f(x) такова, что
0^ f(x)1 при 0 х 1. Тогда
1
^f(x)dxf&m/n, (♦)
о
где п — число всех рассмотренных случайных пар
(хг, yi), а т — число тех из них, для которых yt f(x).
Пользуясь этим, найдите величину интеграла (») для
f (х) = х2 по п — 500 случайным точкам (х<, yi). Изме-
ните программу так, чтобы вычислять с ее помощью
объемы трехмерных тел, например,
х>0, #>0, г^0 и x3 + ^ + zJ^l.
85
2. Электронную гадалку, которую мы сейчас опишем,
придумал создатель теории информации. К. Шеннон. Ра-
ботает она так. Человек пишет на бумаге число О или 1.
Машина этого числа не знает, но печатает 0, 1 или 2.
Двойка означает, что машина не берется угадать напи-
санное число, а 0 или 1 —ее предположение о написан-
ном числе. После этого человеку сообщают предположе-
ние машины, а в машину вводят число, написанное че-
ловеком.
Вначале машина играет неважно, но после двух-трех
десятков проб начинает угадывать в 90 % случаев, сколь-
ко бы человек ни пытался ее запутать. Это производит
впечатление.
Устроена программа так. В ней имеется 5-индексный
массив А [0:1, 0 *2, 0:1, 0: 2, 0 :1] из 72 элементов. Вна-
чале массив очищен нулями, и машина первые три раза
печатает двойки. В дальнейшем машина помнит несколь-
ко последних ходов своих и человека. Если человек по-
следними написал числа а\, аг, аз и машина на это от-
вечала bt, b2, Ьз, то в ячейку A[ai, blt а2, Ь2, аз] добав-
ляется единица, то есть машина запоминает, что после
комбинации ait Ь\, а2, Ь2 человек выбрал число аз. Чтобы
предсказать, что теперь напишет человек, машина срав-
нивает числа А [а2, Ь2, аз, Ьз, 0] и А [а2, Ь2, аз, Ьз, 1]. Если
первое сильно превосходит второе, то предсказывает
число 0, если наоборот, то число 1, а если они отли-
чаются мало, то печатает число 2, то есть отказывается
угадывать. Можно усовершенствовать программу, до-
бавляя на ходе i в нужную ячейку не единицу, а число
(1.1)/, и тем самым уменьшая вес старых событий, кото-
рые человек успевает забыть.
Запрограммируйте гадалку так, чтобы цифры, напи-
санные человеком, и цифры, предсказанные машиной,
располагались на экране парами и чтобы человек видел
последние 10—20 пар. Показывайте все время на экране
текущий процент верных угадываний. Испытайте вариант
гадалки, не учитывающей своих предсказаний, но зато
руководствующейся более длинными сериями чисел че-
ловека.
Если бы человек определял свои числа бросанием
монеты или с помощью случайных чисел, то программа
не смогла бы угадать заметно более 50 % чисел. Но че-
ловек не умеет задавать числа случайно, и электрон-
ная гадалда расшифровывает его тактику или психо-
логию,
86
§ 9. ЧТО ТАКОЕ СТРУКТУРИРОВАННОЕ
ПРОГРАММИРОВАНИЕ
1. Структурированное программирование — это опре-
деленный способ организации программы, коренным об-
разом влияющий на разработку больших программ.
Структурированное программирование облегчает напи-
сание большой программы, ускоряет его, упрощает от-
ладку, помогает разделению работы между исполните-
лями и открывает возможности для дальнейших пере-
делок программы.
Структурированное программирование возникло не
позже конца, пятидесятых годов и рассматривалось в пе-
чати уже в середине шестидесятых *), но была серьезная
причина,- задержавшая распространение нового метода.
При программировании снизу-вверх программистская
квалификация требовалась от исполнителей, а руководи-
тель мог быть администратором. При программировании
же сверху-вниз руководитель должен быть квалифициро-
ванным программистом. Только Дейкстра **) в семи-
десятых годах сумел убедить программистов ведущих
фирм в категорической необходимости структуриро-
ванной организации больших программ. С тех пор по
структурированному программированию стали выходить
толстые книги и научные статьи.
В настоящее время большая неструктурированная
программа воспринимается как написанная архаично
или неграмотно.
Школьники старших классов зачастую работают над
составлением больших программ. Эти программы долж-
ны быть структурированными. Поэтому мы решили вклю-
чить в эту книгу сведения о структурированном програм-
мировании.
2. Сформулируем основной признак структурирован-
ной программы.
Структурированная программа целиком состоит из
блок-программы и блоков (то есть операторов или под-
программ), к которым блок-программа обращается.
Блок должен возвращать продолжение программы к
оператору блок-программы, следующему за обратив-
шимся к нему.
*) Брудно А. Л. Введение в программирование, в содержатель-
ных обозначениях.—М.: Наука, 1965. (См. пп. 12.2 и 13).
**) Дал У., Дейкстра Э., Хоор К. Структурное программиро-
вание. — М.: Мир, 1975.
87
Блок-программа должна быть обозримой (достаточ-
но короткой). Она (по возможности) не содержит вы-
числений и состоит лишь из операторов перехода (услов-
ных или безусловных) на блоки (выполняющие нужные
вычисления) и на операторы самой блок-программы.
Можно сказать, что выполнение структурированной про-
граммы состоит в выполнении ее блок-программы, кото-
рая организует работу своих блоков, играющих в ней
роль операторов с определенными локальными функ-
циями.
В литературе и устной речи встречаются различные
названия для блок-программы — от «собиралки» до
«программной записи блок-схемы». Все же блок-про-
грамма пишется по более жестким правилам, чем
блок-схема, и становится более определенной и обяза-
тельной.
3. Чтобы написать структурированную программу,
надо разбить задачу на отдельные осмысленные части,
и начать писать ее с блок-программы, обращающейся к
этим, еще не написанным частям (блокам). Не беда,
если при написании блок-программы будет не известно,
как выполнить задачи, поставленные перед блоками —
решение следует отложить до написания самих блоков.
Все, что не ясно, надо исключать из блок-программы и
относить к блокам, а в блок-программе выяснять только,
когда к какому блоку следует обратиться.
.Блок нужно оформлять как отдельную часть про-
граммы с одним входом *и одним выходом. Он может
быть просто частью программы, но может иметь вид
блока алгола, процедуры алгола или SUBROUTINE
фортрана. Если при написании отдельного блока снова
появятся трудности или его программа окажется ;плохо
обозримой, то программу этого блока следует тоже раз-
бить на более мелкие осмысленные части и написать
его блок-программу. Итак, структурированную програм-
му разбивают на блоки — это называется декомпозицией
программы — и пишут сверху, то есть начиная с блок-
программы.
Отладку программы надо постараться начать до на-
писания всех блоков, вставив вместо отсутствующих
блоков какие-нибудь операторы, имитирующие их ра-
боту и дающие определенные ответы. Структурирован-
ную программу легче будет потом уточнить, усовершен-
ствовать и даже переделать.' Это тоже ее важное пре-
имущество перед программой, написанной по старинке
3%
«в линеечку», когда все, что выполняется подряд, запи-
сывается и в программе подряд.
4. Преимущества структурированного программиро-
вания убедительно сказываются только на больших про-
граммах, которых здесь мы не можем привести. По-
этому ограничимся тем, что мы декларативно смогли
сообщить, и дадим сводку принципов структурирован-
ного программирования.
5. Принципы структурированного про-
граммирования:
(1) Программа должна состоять из блок-программы
и блоков; к'которым блок-программа обращается. Так
же пишется и всякий сложный блок.
(2) Блок-программа состоит из операторов обраще-
ния к блокам и операторов перехода (условных и без-
условных) к операторам блок-программы. '
(3) Блок имеет единственный вход и единственный
выход. Блок всегда возвращает управление оператору
блок-программы, следующему за тем, который обра-
тился к нему.
(4) Программа пишется и отлаживается сверху, то
есть начиная с блок-программы (то же относится к бло-
ку, имеющему блок-программу). Вместо отсутствующих
(к данному моменту) блоков пишутся заменители, ими-
тирующие работу этих блоков.
(5) Изложенные здесь принципы можно нарушать
.только в случаях серьезной надобности.
§ 10. ОБУЧЕНИЕ ПРОГРАММИРОВАНИЮ
В УЧЕБНО-ПРОИЗВОДСТВЕННОМ ЦЕНТРЕ
1. Учебно-производственный центр вычислительной
техники (УПЦ-ВТ) Октябрьского района г. Москвы ра-
ботает 12 лет. Базовым предприятием УПЦ-ВТ все время
является институт, имеющий вычислительные машины и
кадры квалифицированных программистов.
2. Занимаются в УПЦ-ВТ ученики девятых и деся-
тых классов соседних школ. Классы занимаются цели-
ком, но ученикам предоставляется /некоторый выбор
специализации, и на специальность «программист-лабо-
рант» идет от трети до половины учащихся. Таким об-
разом, наше обучение рассчитано на рядового уче-
ника.
89
(5) паскаль,
(6) язык си,
(7) операционные системы,
(8) бейсик.
Школьникам, выбравшим специальность программи-
ста-лаборанта, в течение 2 лет преподаются четыре про-
граммистских предмета из числа следующих:
(1) основы програм-
мирования,
(2) алгол,
(3) фортран,
(4) ассемблер,
Впрочем, не всем группам преподавались четыре кур-
са? Но всегда читался фортран и, по большей части, один
язык низкого уровня (ассемблер или содержательные
обозначения в курсе основ программирования*)).
2.1. Цель курса основ программирования двояка — по-
знакомить с цифровой электронной машиной с точки зре-
ния пользователя, то есть с тем, какие команды она вы-
полняет, и познакомить с программированием, то есть
с тем, как свести сложную задачу к командам машины.
При прохождении этого курса ученик получает пред-
ставление о возможностях машины и границах этих воз-
можностей, то есть об обстоятельствах, которые остают-
ся скрытыми при программировании на языках высокого
уровня.
Обучение ведётся в содержательных обозначениях на
условной машине ММ. Содержательные обозначения
близки к обычным математическим, а машина ММ — это
простейшая универсальная машина с плавающей запя-
той. Такое построение курса дает возможность учащим-
ся усвоить существо дела, минуя синтаксис сложного
языка программирования и не отвлекаясь конструктив-
ными особенностями реальной машины.
Программы, написанные в содержательных обозначе-
ниях, кодируются в учебных целях вручную. Затем они
выполняются на реальной машине базового Института
(М-4030 или серии ЕС) с помощью программного интер-
претатора **).
Курс «Основы программирования» преподается у нас
недолго (1—1,5 семестра)так как большие программы
в содержательных обозначениях писать не стоит (они
*) По .книге Брудно А..Л. Введение в программирование, в
содержательных обозначениях. —М.: Наука, 1965.
**) Интерпретатор написали сотрудники ИНЭУМ Брудно А. Л.,
Мищенко А. Е., Коган М, М.
90
длинны и пишутся трудно, как на мнемокоде)1. Зато
после этого курса легко усваиваются любые языки про-
граммирования, а умение оценить возможности примене-
ния вычислительных машин в новых вопросах практиче-
ской деятельности остается надолго. По описанному ме-
тоду выучилось много поколений программистов.
Изучение ассемблера оказалось неудачным, и мы со-
общаем об этом, чтобы предостеречь. В машине ММ все-
го 16 команд, а на ассемблере ~ 150. И хотя изучается
команд ассемблера гораздо меньше, все равно ученик не
может обращаться с ними так же свободно, как с коман-
дами машины ММ. Вывод результатов на печать на ас-
семблере сложен, а в библиотеке ММ прост. Содержа-
тельные обозначения пользуются привычной символикой
I(например, 4--* / <), знаки операций ставятся между
операндами (например, a + b)f а передачи управления
указываются стрелкой или меткой. В ассемблере для
этого служат мнемонические обозначения,' которые надо
выучить и запомнить. Все это делает курс ассемблера,
формальным, малоинтересным, и мы от него отказались.
2.2. Изучение языков высокого уровня (алгол, фор-
тран, а также и других) дает учащимся эффективный
аппарат решения прикладных задач. По ходу теорети-
ческого прохождения курса учащиеся обязательно пи-
шут программы, которые пропускаются на вычислитель-
ных машинах.
При изучении алгола упор делается на лингвистиче-
ские возможности языка программирования. Подчерки-
вается краткость и ясность его определений, их широта
и отсутствие исключений. Демонстрируется близость ал-
гола обычному описанию алгоритмов на человеческих
языках. В алголе, например, можно описать процедуру-
функцию «сигма», подобную оператору
а
X (выражение),
и с помощью только этой процедуры-функции вычислять
и сумму элементов массива, и скалярное произведение,
и значение полинома.
Но следует отметить и недостатки алгола — отсут-
ствие машинно-(или трансляторно-)независимых опера-
торов ввода-вывода.
При изучении фортрана значительное внимание уде-
ляется возможностям организации ввода-вывода. Объяс-
91
няется удобство описаний типов по первой букве. Сооб-'
щается о широком распространении фортрана, о том, что
подавляющее количество пакетов прикладных программ
написано на фортране.
Особенностей преподавания других курсов мы здесь
касаться не будем.
Изучается сначала фортран, а затем (если он пре-
подается) — алгол. Делается это по двум причинам: ор-:
ганизационной и педагогической.
1) После 9-го класса учащиеся проходят производ-
ственную практику на различных предприятиях, где
программируют на фортране. Если в 9-м классе прохо-
дить алгол, то практику придется вести самим препода-
вателям.
2) После алгола учащиеся неохотно учат фортран.
Это вызвано необходимостью заучивать несколько пра-
вил со многими исключениями. Так, например, индек-
сом переменной, началом цикла, его шагом и границей
в алголе служит любое арифметическое выражение.
В фортране же здесь каждый раз свои оговорки, меняю-
щиеся от транслятора к транслятору.
3. Каждый ученик занимается в УПЦ-ВТ один день’
в неделю. После занятия он сдает написанные им тексты
программ, которые перфорируются и пропускаются в па-
кетном режиме. На следующем занятии (то есть через
неделю) учащийся получает листинги сданных программ,
исправляет обнаруженные ошибки и т. д. На обслу-
живание всего УПЦ-ВТ (до 1000 учащихся) ИНЭУМ
тратит одну (закрепленную) машинную смену в не-
делю.
По окончании двухгодичного обучения ученики сдают
экзамен и получают свидетельство о присвоении квали-
фикации «программист-лаборант».
Наш опыт показывает возможность преподавания
программирования в школах, не имеющих собственных
машин, При помощи предприятия, выделяющего немного
машинного времени. Но он не должен затушевывать тот
факт, что современный возврат к работе за пультом (те-
перь— дисплеем), когда ученик отлаживает свою про-
грамму на уроке, а не ждет результата неделю, несрав-
ненно повышает интерес к предмету и эффективность
' его изучения. И для этого школам требуется собствей-
ное оборудование дисплейные классы.
92
§ 11. ПЕРСПЕКТИВЫ ОБУЧЕНИЯ
ПРОГРАММИРОВАНИЮ В ДИСПЛЕЙНОМ
КЛАССЕ
1. В первое десятилетие существования цифровых
электронных машин программист отлаживал свою про-
грамму за пультом машины, которая была полностью
в его распоряжении. Он мог пускать программу с лю-
бого оператора до любого. Останавливать ее и продол-
жать. Мог увидеть промежуточные результаты, которые
понадобились, и исправить программу прямо в памяти
машины. За пультом программист просиживал час-два,
и, как правило, за один-два раза отлаживал программу
й получал результат.
Но со стороны это выглядело расточительно — более
90 % времени машина простаивала, а программист ду-
мал. И когда скорость машины поднялась в 100 раз
|(а цена — в 10), пультовая отладка прекратилась.
2. И наступил этап пакетного режима. Теперь про-
граммиста вообще перестали пускать в машинный зал.
Он сдавал программу и получал «листинг» — листы бу-
маги, на которых программа напечатала свои, заплани?
рованные заранее результаты, а операционная система и
транслятор — сообщения об обнаруженных ошибках.
Разобрав в спокойной обстановке листинг, программист
вносил исправления в программу и снова отправлял ее
на машину. Число программистов, обслуживаемых одной
машиной, стало исчисляться сотнями.
Внешне это выглядело хорошо. Машина работала не
только без простоев, но и с тройной (как минимум) за-
грузкой: она одновременно одну программу вводила, по
другой — считала, а результаты третьей — печатала.
И все же пристальному взгляду картина представля-
лась не столь радужной. Для отыскания ошибок ока-
зывалась нужна печать не тех результатов, которые
были запланированы (человек падает не там, где под-
стелил солому), а операционная система и транслятор
сообщали не столько об ошибках программиста, сколько
об ошибках, которые появились от этого. Число выходов
на машину, нужных для отладки, возросло, а календар-
ное время на отладку одной программы (от начала —
до конца) выросло катастрофически.
Короче говоря, если при пультовой отладке машина
в основном простаивала, то в пакетном режиме она в
основном работала впустую, выполняя расчеты, которые
93
программист прекратил бы, увидев уже происшедшее.
И цифровые электронные машины вышли на второе ме-
сто в мире по производству бумажной макулатуры (по-
еле газет).
И все же машинного времени -в пакетном режиме
идет на задачу меньше, хотя программистского — боль*
ше, и этот режим оказался выгоднее старой пультовой
отладки.
Описанное в предыдущем параграфе относилось к
организации обучения программированию именно в па-
кетном режиме. Ученик сдавал программу, а через не-
делю, забыв ее, получал листинг и узнавал, что пропус-
тил в начале программы запятую, от чего машина
дальше все понимала наоборот. Он поправлял програм-
му и сдавал ее вместе с новой, написанной на этом за-
нятии. В следующий раз он получал два листинга и т. д.
, Высокая квалификация и умение требуются от препода-
. вателя, чтобы сделать в этих условиях программирова-
ние интересным для подавляющего большинства учащих-
ся обычного школьного класса.
3. Дальнейшее развитие и удешевление цифровых
электронных машин привело к возврату к пультовой от-
ладке, но на новой основе. Наступил дисплейный этап
работы с машиной.
Дисплей — это экран с клавиатурой (похожий на
объединение телевизора с пишущей машинкой). Рабо-
тая за дисплеем, программист сам вводит в машину
программу, передает команды управления операционной
системе и видит на экране результаты своих действий
и работы машины.
Работа за дисплеем дает возможность ученику прямо
на занятии отладить свою программу и получить ре-
зультат. Кроме того, дисплей дает возможность общать-
ся с машиной в диалоговом режиме и, пользуясь этим,
программировать игры человека с машиной — от кре-
стиков-нуликов до шахмат. Надо сказать, что лучшие
ученики охотно придумывают такие игры и разрабаты-
вают программы. Менее предсказуемым было другое
преимущество дисплея — возрождение энтузиазма ра-
боты за пультом. В дисплейном классе учителю прихо-
дится больше тратить усилий, чтобы закончить урок,
нежели чтобы его начать.
4. Что касается предметов, то они у нас остались
почти теми же. Это прежде всего фортран. Затем смо-
гут появиться язык си, введение в программирование,
184 ' '
алгол (или паскаль). Но обязательно приходится "начи-
нать с общих приемов работы за дисплеем — общения с
операционной системой (например, редактором). И не-
обходимо остановиться здесь не на разумном минимуме,
а на настоящем.
г' 5. Технически дисплейные пульты могут организовы-
ваться одним из следующих двух способов:
а) К одной средней или мини-машине подключаются
несколько дисплеев (10—20). Тогда все результаты ра-
боты класса могут быть записаны на магнитный диск
в каталог этого класса. Для вывода результатов на пе-
чать тоже может использоваться одно быстропечатаю-
щее устройство на все пульты.
б) Каждый дисплей автономно связан со своей ми-
кромашиной. Или даже встроен в маленькую персональ-
ную машину, промежуточную между микромашиной и
карманным калькулятором. Но во всех этих случаях дис-
плей должен иметь какое-то печатающее устройство и
какую-то внешнюю память на магнитофонной кассете
или флоппи-диске (небольшой гибкий диск). Эта кассета
или диск закрепляется за учеником.
В школьных машинах можно отказаться от быстро-
действия, дорогих печатающих устройств, магнитных
дисков и лент, но нельзя отказаться от внешней памяти,
дающей возможность ученику продолжить работу, не
законченную за один выход на машину. Школьная ма-
шина должна быть «инженерно-независима», то есть
устойчива и проста в инженерном обслуживании.
Затраты на оборудование школьного дисплейного
класса, разумеется, выше, чем при обучении школьников
в пакетном режиме выполнения программ.
6. И наконец, может быть, главное — школьная
электронная вычислительная машина должна получить
математическое обеспечение (операционную систему,
трансляторы, библиотеки), рассчитанное на обучение
программированию по школьным программам с тем,
чтобы обучение не увязало в специфических особенно-
стях операционной системы, редактора и дисплея. Мы
должны быть готовы к тому, что создание и совершен-
ствование такого обеспечения учебного процесса ока-
жется большой самостоятельной работой.
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ АВТОРОВ.......................3
§ 1. ОЛИМПИАДНЫЕ ЗАДАЧИ...................5
§ 2. АЛГОРИТМЫ РЕШЕНИЙ...................10
§ 3. РЕШЕНИЯ НА АЛГОЛЕ ................. 25
§ 4. РЕШЕНИЯ НА ФОРТРАНЕ................ 40
§ 5. ПРОГРАММИРОВАНИЕ ПЕРЕБОРА ВАРИАНТОВ . . 58
§ 6. РЕТРОСПЕКТИВНЫЙ АНАЛИЗ..............72
§ 7. ЧЕТЫРЕ ЗАНИМАТЕЛЬНЫЕ ЗАДАЧИ ПО КИБЕРНЕ-
ТИКЕ .................................. 75
§ 8. СЛУЧАЙНЫЕ ЧИСЛА И ЭЛЕКТРОННАЯ ГАДАЛКА 83
§ 9. ЧТО ТАКОЕ СТРУКТУРИРОВАННОЕ ПРОГРАММИ-
РОВАНИЕ ................................87
§ 10. ОБУЧЕНИЕ ПРОГРАММИРОВАНИЮ В УЧЕБНО-ПРО-
ИЗВОДСТВЕННОМ ЦЕНТРЕ....................89
§ 11. ПЕРСПЕКТИВЫ ОБУЧЕНИЯ ПРОГРАММИРОВАНИЮ
В ДИСПЛЕЙНОМ КЛАССЕ . , . . , е . , . . 93
нои