Автор: Королёв С.А.   Бейда А.А.  

Теги: программирование   информатика   эвм   компьютерные технологии  

ISBN: 5-341-00466-3

Год: 1991

Похожие

Задачи мудрецов. Книга для учащихся

Язык программирования Си. Задачи по языку Си

Олимпиадные задачи по программированию

Комбинаторные задачи: олимпиады по программированию

Текст 
                    A. A. БЕЙДА, С. A. КОРОЛЕВ

ИГРОВЫЕ
3444ЧИ
И


A. A. БЕЙДА, С. A. КОРОЛЕВ

ИГРОВЫЕ
М44ЧИ

КНИГА ДЛЯ УЧАЩИХСЯ

МИНСК «НАРОДНАЯ АСВЕТА» 1991


ББК 32.973
Б41

P e ц e н з e н τ A. H. Останин, профессор Белорусского
политехнического института

Б41

Бейда A. A., Королев С. А.
Игровые задачи и ЭВМ: Кн. для учащихся.—
Мн.: Нар. асвета. 1991,—144 c.: ил.
ISBN 5-341-00466-3.
Книга содержит задачи и программы для их решения.
Авторы показывают, что целый ряд научно-популярных книг,
сборников головоломок, а также учебников может стать источ­
ником интересных задач на программирование, решая которые
школьники глубже усваивают изученные правила и законы,
отрабатывают навыки доказательства теорем. Адресуется уча­
щимся старших классов.

4802030000—135
Б------------------------ 146—91
M303(03)-91

ISBN 5-341-00466-3

ББК 32.973
© Бейда A. A., Королев С. A., 1991


Предисловие
Эта книга представляет собой набор задач и про­
грамм для их решения. Многие программы разработаны
в двух вариантах — для микрокалькулятора «Электро­
ника МК-54» и на Бейсике — и только там, где возмож­
ностей микрокалькулятора было недостаточно, оста­
вался Бейсик (ОС ДВК). Каждая программа снабжена
подробным руководством по ее разработке, а там, где
использовался микрокалькулятор, особо подчеркнуты
различия в разработке алгоритма решения, зависящие
от выбора вычислительного средства. Изложение ве­
дется таким образом, что практически никаких специ­
альных знаний о языках программирования или осо­
бенностях программирования для микрокалькуляторов,
выходящих за рамки школьной программы, не требует­
ся. Желательно помимо учебника иметь только какойнибудь справочник по расчетам на микрокалькуляторах
(папример, |1|). Таким образом, данную книгу можно
рассматривать как элементарный практикум по про­
граммированию.
Другая сторона дела состоит в подборе задач.
Основные принципы, использовавшиеся при этом, видны
уже при чтении оглавления. В первой главе микрокаль­
кулятор используется в качестве партнера в научноисслсдовательской работе. Это глава о том, как можно
ставить и проверять гипотезы, обладая вычислительным
средством; и еще о том, как полезен алгоритмический
стиль мышления в выработке стратегии научного
поиска.
Начиная со второй главы, показывается, что целый
ряд традиционных научно-популярных книг, сборников
головоломок и занимательных задач, а также учебни­
ков может стать источником интересных задач на про­
граммирование. А неизменное присутствие игровой
компоненты в большинстве книг такого жанра, как
нельзя лучше служит этому делу. Игра занимает одно
3


из важных мест в жизни человека во всех возрастах.
Она представляет собой творческий процесс, в котором
человек наиболее естественным и непринужденным
образом раскрывает свои способности. На материале
игровых задач можно глубже освоить только что вы­
ученный новый закон, отработать навыки вычислений
или этапы доказательства теоремы и τ. π. При этом на
базе ЭВМ процесс обучения становится широко раз­
ветвленным, многоуровневым. Некоторым аспектам
затрагиваемой проблемы и посвящена третья глава.
Наконец, в четвертой главе речь идет о некоторых
принципах машинного решения логических задач. А за­
канчивается эта глава игрой. Понятие алгоритма близко
понятию правил игры, поэтому, общаясь с ЭВМ, можно
также в игровой форме учиться искусству програм­
мирования. Одна из важнейших особенностей игровой
компоненты и состоит как раз в том, что она пробуждает
интерес к программированию, позволяет в наиболее
доступной форме усваивать практические навыки
программирования.


1. Какую задачу мы будем решать
Известному английскому математику Г. Г. Харди
(1877—1947) принадлежит следующее высказывание:
«Элементарную теорию чисел следует считать одним из
наилучших предметов для первоначального математи­
ческого образования. Она требует очень мало предва­
рительных знаний, а предмет ее понятен и близок; ме­
тоды рассуждений, применяемые ею, просты, общи и
немногочисленны; среди математических наук нет рав­
ной ей в обращении к естественной человеческой любо­
знательности».
В этой главе мы обратимся к одной простой задаче
элементарной теории чисел. Для ее решения необходимо
знать самые начальные сведения этой теории. Но мы
поступим иначе. Попытаемся ответить на следующий
вопрос: как развивалась бы наша мысль в познании
процессов и явлений, если не имея еще общих теорий,
мы имели бы ЭВМ для усиления нашего мозга —
удобный инструмент, способный удовлетворить пытли­
вость нашего ума в значительно большей степени и со
значительно меньшими физическими затратами, чем
если бы на то мы употребили обычный ручной труд.
Итак, задача.
Даны натуральные числа a, n и b. Вычислить оста­
ток от деления числа an на b.
Если задача формулируется в общем виде, то и ее
решение должно быть таким, чтобы оно позволяло
получить ответ при любых значениях a, n и b. Обратим
лишь внимание на слово «любых». На практике (осо­
бенно, когда мы собираемся воспользоваться какимлибо вычислительным средством) правильнее было бы
употреблять его в паре со словом «допустимых». Дейст­
вительно, если мы будем пользоваться, например,
микрокалькулятором, то ни одно натуральное число
5


(как данное по условию, так и возникающее в про­
цессе счета) не должно превышать 99999999: нату­
ральные числа на индикаторе МК-54 изображаются
в диапазоне от 1 до 108- I = 99999999.
2. Велико ли число 2,987

Примемся вначале за изучение частных случаев.
Пусть:
Начнем с того, что число 21987
^-n-------- &------ очень велико. Для того чтобы убе~
~ ^
диться в этом, составим несложную
1У87
3
программу для вычисления αn на
------- ------- МК-54.

(1)

Здесь оператор БП 08 страховочный. В результате
мы не сможем обнулить счетчик команд, если нечаянно
нажмем на клавишу C∕Π после окончания счета. Если
счет окончен и его нужно возобновить при новых зна­
чениях а и n, необходимо нажать на клавишу B/O и
произвести ввод данных.
Соответствующий алгоритм написан нами на псев­
докоде. Внешнее оформление алгоритма отвечает пра­
вилам, принятым в алгоритмическом языке. Однако
6


Программа
Номер
команды

---- ^Л

^γ

Коммен­
тарии

Команда

Код

00
01

x→∏a
С/П

4—
ВВОД а
50

02

x→Π0

40

ВВОД tl

03

1

01

^x: = l

04
05

∏→xa
×

06
07

F L0
04

5Γ
04

F L0
Δ

08

С/П

50

С/П

09
10

БП
08

51
08

БП
V

6- Rx: =
= Rx • а
12

допускается широкое
использование oπeраторов MK-54. Для
удобочитаемости
и
лучшего восприятия
смысла многих таких
операторов при их
написании мы будем
использовать стрел­
ки и метки (для ме­
ток берутся буквы
греческого алфави­
та). Так, например,
фрагмент
------- ►Л Rx: = Rx • а
F
L0___
------ ^------------- Δ

γ С/ГЬ--------------------означает, что всякий раз после исполнения команды
#x: = Rχ. а содержимое регистра 0 уменьшается на
единицу и затем сравнивается с нулем. Если остав­
шееся число больше нуля, возобновляется исполнение
команды Rx.≈Rx∙at помеченной меткой Δ. В против­
ном случае осуществляется переход к команде С/П.
Переменная Rx будет стандартно служить для обозна­
чения содержимого регистра x. Вдоль записи алго­
ритма всегда будут отводиться два столбца: для вели­
чин, встречающихся при счете, и соответствующих им
регистров памяти. При необходимости мы будем от­
водить еще один столбец для комментариев.
Воспользовавшись составленной программой, по­
лучим, в частности, что
225 = 33554432,
226 = 67108864,
но, увы, 227 ≈l,3421773∙108. Это уже вещественная
константа, хотя еще и вручную несложно установить
точное значение 227:
227 ≈= 67108864 • 2 ≈= 134217728.
Вот что будет получаться на микрокалькуляторе
дальше:
24°≈l,0995116∙1012>
2200 ≈l,6069376∙ 106°,
2330 ≈2,1872502∙10",
2332 ≈ 8,7490008 • 10",
2333→EΓΓOΓ.
7


Все. Возможности микрокалькулятора исчерпаны.
Таким образом, мы не смогли достичь значения 2l9a7
даже приближенно, хотя для наших целей в этом и нет
никакого проку. После значения 226 все вычисления
теряют смысл — ведь нам нужно целое (!) значение
числа 21987.
Попали ли мы в тупик? Нет. Огорчительным было
бы как раз именно то, что задачу можно решить непо­
средственным вычислением. Это означало бы, что она
как задача не состоялась.

3. Гипотеза, высказанная алгоритмом
Итак, попытаемся устранить возникающее затруд­
нение с переполнением разрядной сетки микрокальку­
лятора. При первом же анализе задачи возникает
естественное предположение, которое может быть вы­
сказано следующим алгоритмом:
алг r
(нат a, n, b цел r)
арг
a, n, b
рез
r
нач
нат S
S: = а
---- >• Δ r: = остаток (S, b)
C∕Π
S: = 5 • а
FL0_____________
--------- Δ
(2)

C∕Π <-------------------БП
------------- У
кон
—> γ

Как по-вашему, что это за предположение? Мы же
обратимся к нему после того, как обсудим некоторые
технические детали (см. (4)).
Для того чтобы преобразовать алгоритм (2) в про­
грамму для микрокалькулятора, необходимо дополни­
тельно разработать вспомогательный алгоритм вычи­
сления остатка. Очевиден следующий вариант такого
алгоритма:
r: = S
пока r ^ b

8


Мы предлагаем читателю записать с этого алго­
ритма программу для микрокалькулятора и исполнить
cc при S = 1000, a b = 3. Каково время счета? (t≈
≈ 10 мин.)
Ясно, что при такой скорости вычисления остат­
ка, мы не разрешив еще одной проблемы, наталки­
ваемся на другую. С другой стороны, каждый из вас
легко укажет иной способ вычисления остатка от де­
ления S на b:
r

s - Γ⅜1 • b.
L^J
Этот способ порождает линейный алгоритм всего в
несколько шагов и поэтому скорость его исполнения
с возрастанием разрыва между значениями S и b просто
не сопоставима со скоростью исполнения предыдущего
алгоритма.
Известен способ вычисления на МК-54 целой части
числа x (1 ≤x< 108) [1]. Если в регистре x (и на индикаторе) находится число

1 ≤ ⅜ < 108,
b
то вся процедура сводится к выполнению всего трех
операторов: x→∙∏9, K∏→x9 и ∏→x9. А так как не­
обходимо учесть и тот случай, когда S < b, то для
ιtι.ιι∣ικ'j∣eιιι∣H остатка необходимо создать разветвляю­
щийся алгоритм, в котором при S ≥ b выполняются
три указанных оператора, а при S ≤ b — один оператор
присваивания r: = S. Вот он (алгоритм):
r:=S
∖
Rx:=S-b
F x≥0_______

---------------- α
Rx: = ^- ч---------------b
Rx: =[‰]
Rx: = Rx • b
г. = S — Rx
------ >a Rx: = r
Теперь вставим этот фрагмент в исходный алго­
ритм (2).


4. От алгоритма к программе, а от нее к проверке
гипотезы

Вернемся к предположению, которое реализовано
в алгоритме (2) и его уточненном варианте (3).
Если последовательно вычислять остатки от
деления чисел ai, a2, a3, ... на число b, то, на­
верно, (ведь остатком всякий раз будет одно
из чисел 0, 1, 2, ..., b — 1) с некоторого момента
эти остатки начнут циклично повторяться.
10

(4)


Код

Коммен­
тарии

00
01

x→∏a
C∕Π

4—
50

ввод а

02
03

x→Π0
c∕π

40
50

ввод n

04

x→∏b

4L

ввод b

05
06

∏→xa
x→∏4

644

S: = a

07
08

∏→x4
x→∏3

64
43

r:=S

(И)
10

!1→xb

6L
11

11
12

Kx>0
25

59
25

13
18

∏→x4
∏→xb
÷

64
6L
13

10
17
18

x »110 49
Kll >x9 Γ9
II >x9 69

Номер
команды

Команда

Команда

Код

Коммен­
тарии

19
20

∏→xb
×

6L
12

Rx.≈
≈Rx∙b

21
22
23
24

∏→x4

x→∏3

64
14
11
43

25

∏→x3

63

Rx: = r

26

c∕π

50

C∕Π

Rx: =
≈S-b

27
28
29
30

∏→x4
∏→xa
×
x→ ∏4

Fx ≥ 0
α

31
32

F L0
07

07

F L0
Δ

33
34
35

C∕Π
БП
33

50
51
33

Останов
БП
V

a

≈S-Rx

64
6S: = S . а
12
44

5г"

I

o *l c°

X

14

⅛

|

Λ

Номер
команды

Это предположение еще очень уязвимо (почему?).
Ilo ссли вы этого пока не заметили, не будем вас то­
ропить. Чем привлекателен наш маленький помощник,
так это тем, что он позволяет стремительно проверять
любую гипотезу^на большом количестве примеров.
Тем более, что весь стиль наших рассуждений таков,
что суждения формулируются в алгоритмической фор­
ме и оформляются в виде алгоритмов. Итак, за дело.
Превратим алгоритм (3) в программу для микрокаль­
кулятора и примемся за счет.

V

Rx: -

-L^1

Результаты счета будем оформлять в виде табли­
чек, смысл которых вам, очевидно, понятен. Заметьте
при этом, что первоначально мы рассматривали один
частный случай. Однако к настоящему моменту у нас
возникла некая гипотеза (см. (4)) и потребность рас­
смотреть целую серию аналогичных примеров с целью
подтверждения или опровержения этой гипотезы. Ta11


ким образом, наши рассуждения начинают обретать
общность.

Здесь при Z=12 мы получаем вдруг, что r=10.
Что это? Период не наступает? Не будем торопиться
с выводами. Проверим содержимое регистра 4, в кото­
ром хранится значение S: ∏→x4. Оказывается S≈
≈2,4414063∙108. То есть S — вещественная констан­
та и, в силу неизбежного округления, S≠α12. Далее
пользоваться алгоритмом (3) для проверки гипотезы
(4) невозможно.
Пример 3.

12


Пример 6.
а

n

b

30

101

42

Показатели степени числа
4
5∖

∖

а

1
2

3

30
18
36

4

30

Аналогично примеру 2 выясним, что при i=6
S≈7,29∙ 108.
Пример 7.
а

n

b

6

1987

16

Показатели степени числа

9

8

7

6

5

а

r

1
2
3
4

6
4
8
0

5

0

гэ


При /=6, казалось бы, должен был быть остаток
г — 7. Значит ли это, что в данном случае период не
наступает? Проверяем (как и в примерах 2 и 6) содер­
жимое регистра 4: ∏→x4. Оказывается, S≈l,5625×
× 101°. В таком случае повторим вычисления и выясним
содержимое регистра 4 при Z=5. Оказывается, что и
при /=5 мы уже получили S≈3,125 • 108. Таким обра­
зом, в данном примере (в отличие от примеров 2 и 6)
мы не сможем высказать даже и предположение о
цикличной повторяемости остатков.
В примерах 1, 3, 4, 5 и 7 мы получаем подтвержде­
ние сказанному в (4), разумеется,только при тех зна­
чениях показателя степени числа а, которые в этих
примерах рассмотрены. Примеры 2, 6 и 8 тоже не опро­
вергают утверждение (4), но, в силу возникшего пере­
полнения разрядной сетки, и не подтверждают его.
5. Вопросов стало еще больше, или Новая гипотеза
Теперь одновременно возникает уже несколько задач:
а) Как производить счет, чтобы подтвердить (или
опровергнуть) гипотезу (4) для примеров 2, 6 и 8
(и аналогичных им примеров)?
б) Доказать утверждение (4) в общем случае (если
оно не может быть опровергнуто).
в) Ответить на вопрос: какова практическая польза
от гипотезы (4) в решении основной задачи, сформу­
лированной в этой главе.
Естественно будет в первую очередь искать ответ
на третий вопрос (вопрос в). Отвечать же на вопросы
а и б имеет смысл только тогда, когда на вопрос в будет
дан положительный и конструктивный ответ.
Итак, допустим справедливость утверждения (4)
и обратимся к примерам. Обозначим длину периода
(количество остатков, которые последовательноповторяются) буквой pf а длину предпериода (количество
14


остатков до первого периода) буквой t. Тогда, в при­
мере 1: t = 0, p = 2. Число n — t = 1987 при делении на
p = 2 дает в остатке 1. Разыскиваем строку показате­
лей степени числа а, содержащую 1. Ей соответствует
значение r = 2. Поэтому, очевидно, при делении 2 987
на 3 в остатке получим 2.
В примере 2: p = 6, t = 0. n — t = 1987 при делении
на p = 6 дает в остатке 1. Поэтому r = 5 (r = 5 соответ­
ствует строке показателей, содержащей 1,— она же явля­
ется первой строкой показателей, отвечающих периоду).
В примере 3: p = 1, t = 1. n — t = 499 при делении на
p = 1 дает в остатке 0, то есть делится на p. Поэтому
число n = 500 находится в последней строке показате­
лей. Следовательно, r= 16.
В примере 4: p = 2, t = 2. n — t = 488 при делении
на p = 2 дает в остатке 0, то есть делится на p. Поэтому
число n = 500 находится в последней строке показате­
лей и, следовательно, r=16.
В примере 5: p = 2, t = 0. n — t = 1347 при делении
на p = 2 дает в остатке 1. Поэтому число n = 1347 на­
ходится в строке показателей, содержащей 1 (она же
является первой строкой показателей, отвечающих пе­
риоду) , и, следовательно, r = 6 (так как этот остаток
соответствует данной строке).
В примере 6: p = 3, t = б. n — t = 101 при делении
на p = 3 дает в остатке 2. Поэтому число n — 101 на­
ходится во второй строке показателей, отвечающих
периоду, и, следовательно, r= 18.
И наконец, в примере 7: p=l, / — 3. n-/=1984
при делении на p = 1 дает в остатке 0. Поэтому число
H=1987 находится в последней строке показателей.
Следовательно, r = 0, то есть число 61987 делится на 16.
Обобщая сказанное, легко получаем следующее
утверждение:

Пусть L0 — число, которое определяется так.
Обозначим r = остаток (n — t, p) и положим
£0 = f ^ ÷ ^> если ' ≠ θ>
(t + p, если r = 0.
Тогда:
остаток (an9 fe) = ocτaτoκ (aLQ, b∖

(5)

При этом ясно, что утверждение (5) справедливо, как
только будет доказано утверждение (4) (см. задачу б).
15


6. Две задачи, имеющие одно и то же решение
Задачиа и б взаимосвязаны: улучшая методику
вычислений, мы^вынуждены переосмысливать гипотезу,
отыскивая в неи как сильные, так и слабые стороны.
В чем же уязвима гипотеза (4)?
Итак, мы последовательно вычисляем остатки от
деления чисел a∖ a2, a∖ ... на число b. То, что каждый
такой остаток — неотрицательное число, меньшее b,
еще весьма слабый повод для того, чтобы утверждать
цикличную повторяемость этих остатков. Не найдутся
ли такие целые числа а и b, что при последовательном
делении с остатком ai на b (z=l, 2, 3, ...) остатки
будут воспроизводиться непредсказуемо (непериодич­
но)? С другой стороны, переполнение разрядной сетки
в примерах 2, 6 и 8 тоже заставляет нас еще раз обра­
тить внимание на этот процесс делений. Причем в этой
ситуации мы вынуждены искать способ уменьшить
число al так, чтобы при делении уменьшенного числа
на b остаток не изменился.
Пусть
ai — b • s + r
и переполнения разрядной сетки еще нет. Тогда
al+x = al • а = abS + ar.
А так как abS делится
*
Остаток
на b, то числа al+l и Степень
а • r имеют одинаковые
а = bSι 4- ri
α1
Γ1
остатки от деления на b.
a∏ = bS2 + r2
r2
α
2
Решение найдено. Про­
a3
ar2 = bS3 + гз
Гз
j
цесс будет таким:
an
Γn
Так как для любого i:
o^п— i = bSn 4~ гn
0 ≤ ri < b1 то не более,
чем через b шагов най­
дутся такие i и /, что выполняется равенство
Γi≈rj
Пусть для определенности, t< j. Тогда в столбце *
получим:
а — bSi 4~ ∏.

_ori—i = bSi 4~ гi
ari = bSi +1 + г14-1
ai+ 1 = bSi + 2 + Γ∕ψ2

arj^↑=bSj + rj и ri = ri, откуда:
16

(6)


ari = bSι+1 4“ ∏+1
arι+ 1 = bSi+2 + 6+2
ari-∖ = bSi + rj и r∣ = ri, откуда:

art = bSι+1 + 6+ι

Утверждение (4) доказано. Следовательно, спра­
ведливо также и утверждение (5).
7. Алгоритм, который решает задачу
Таким образом, установлено, что алгоритм (3) мо-

17


числа an на b, а неприятная ситуация с переполнением
разрядной сетки (особенно болезненная в примере 8)
легко устраняется, если изменить этот алгоритм с уче­
том рассуждений (6). Вот как будет выглядеть изме­
ненный алгоритм (сравните его с (3)): (см. с. 17).
В этом алгоритме процедура (6) описывается сле­
дующей рекурсивной схемой
r: = а
г: = остаток (r, b)
C∕Π
r: = r • а
F L0
---------------------Δ

—>Δ

<—-------------------------------------------------Кроме того, в алгоритме появляется дополнительная
строка

^:=Л,
а

помеченная меткой γ. Действительно, если предполо­
жить, для общности, что при сравнительно небольшом
n остаток будет окончательно вычислен еще до обна­
ружения периода (и мы выйдем на бесконечный цикл,
определяемый оператором БП γ), то в этом случае бу­
дут подряд выполнены два оператора
r: = r∙a

Последнее приведет к высвечиванию на индикаторе
истинного значения остатка (а не увеличенного в α
раз).
Программа для МК-54
Программу решения исходной задачи, которую мы
приводим далее, можно уже применять для широкого
круга примеров. Достаточно лишь, чтобы числа n и
ab не переполняли разрядную сетку. (Изучите вни­
мательно алгоритм (7) и ответьте на вопрос:
почему?)
18


Коммен­
тарии

Номер
команды

Команда

4—
ввод а
50
_____ £

20
21
22
23

∏→x3

24

∏→x3

25

c∕π

Номер
команды

Команда

00
01

x→∏a
c∕π

02
03

x→Π0
c∕π

40
50

ввод n

04

x→∏b

4L

ввод b

05
06

∏→xa
x→∏3

643

x=α

07
08
09

∏→x3
∏→xb

63
6L
11

Rx: =
=r—b

10
11

Fx≥0
24

59
24

Fx>0
α

12
13
14

∏→x3
∏→xb

63
6L
13

Δ

Код

α

T

15
16
17

18
19

x→∏9 49
K∏→x9 Γ9
∏→x9 69
∏→xb
×

6L
12

Rx:=Jb

Rx: =
= [‰]

Код

Коммен­
тарии

F
14
r: =
11 = r-Rx
x→∏3 43

26
27
28
29

∏→x3
∏→xa
×
x→∏3

30
31

F L0
07

32
33
34

∏→x3
∏→xa

35

C∕Π

36
37

БП
32

^Γ Rx: = r

^50~

C∕Π

бз~
6 — r: = r • а
12
43

^Γ^
07

F L0
Δ

63
6— *x-=i
13
50

ТГ”
32

c∕π

БП
T

Rx: =
= Rx*b

8. Когда полезно усложнить алгоритм

Итак, мы имеем вполне удовлетворительный алго­
ритм для вычисления остатков. Однако исполнение
этого алгоритма при помощи микрокалькулятора coпропождпстся еще достаточно большим количеством
ручноготруда. Образноговоря, утверждения (4) и (5),
ιιo которым строится алгоритм, разбивают его на две
части. При этом оказывается, что (4) определяет его
машинную часть, а (5) — ручную. Правда, для вычис­
ления остатка от деления числа n — t на p можно вос­
пользоваться имеющейся программой, а ввод данных
осуществлять по следующей таблице:
К сожалению, полностью устра­
b
n
а
нить ручной труд, используя микро­
калькулятор, нельзя, так как для
I
n — /
P
решения данной задачи у него весьма
19


ограничена память. Однако ручной труд можно свести
доминимума. Приведем соответствующую программу.
Отвечающий ей алгоритм получается усовершенство­
ванием алгоритма (7). Прежде чем приводить этот
алгоритм, опишем введенные в него дополнительные
переменные.
i___ переменная, в которой накапливаем количество
произведенных в цикле делений с остатком; в момент
останова для чтения промежуточного остатка значение
i на единицу превышает показатель степени числа а,
остаток от деления которой на b вычислен.
⅛___ ключ, в зависимости от значения которого {k —
= 0 1 или 2) осуществляется переход к вычислению
остатка от деления an на b, определяются значения t
и p, вычисляется остаток от деления числа n
t на p,
соответственно.
L0 — содержимое регистра 0, используется для
организации цикла оператором F L0.
Исполнение алгоритма будет осуществляться сле­
дующим образом:
1
. Ввод данных α, n и b.
2 Последовательное заполнение таблицы:
i

1

2

3

4

∏

r∖

Г2

Гз

П

которое производится по следующему правилу:
а) когда наступает первый останов (после ввода
данных) на индикаторе читаем значение n, заносим
его в таблицу под номером 1, нажимаем клавишу Cx
(обнуляем индикатор) и пускаем машину на счет на­
жатием клавиши C∕Π.
б) При /-м останове на индикаторе читаем зна­
чение rl, заносим его в таблицу под номером / и про­
веряем, не совпало ли оно с каким-нибудь предшест­
вующим rAi ≤ /).
в) Если для любого t</ ∏≠∏ обнуляем индикатор нажатием клавиши Cx и пускаем машину на
г) Если для некоторого io ri, = ri набираемнаиндиκaτope число i0 и пускаем машину на счет: C/11. После
останова на этот раз читаем значение остатка r от
деления an на b.
20


А теперь опишем итоговый алгоритм и приведем
соответствующую программу.
Распределение
регистров
памяти

Ал гоpиτм

алг остаток (нат a, n, b цел r)

Коммен­
тарии

вели­ ре­
чина гистр

рез r

а
n
b
r

а
с
b
3

L0: = n
k∖= 1

L0
k

0
2

1)

i

1

2)

Rx

x

арг a, n, b

нач

i: — 1
Δ Rx: = r — b_____________
F x≥ 0________________
-- Q&

3)

'

II

„^ «

(8)

II

^

⅛⅛ 1

II

⅛⅛
Q
^

*
^⅜

H
≈,

I

<

≤

n„._X ^_________

Rx:-k
F x ≠ 0________________
—— p
nv. __
дХ.
— Кλ,___о
z -e
*_
F x = 0________________
------- κ
D v • -— Ir ‰
*~ ■
^Λ.
F x ≠ 0________________
-------- e
/ ∩. —
Dγ^^
l ι/ ^
LU.
— ^л
к_
БП
_______ ιbψ
--------

→ε LGι=p + t
→ гр k: = 0
bι = R8
БП
,, Q
► α Rx = k
F x ≠ 0________________

4)

*

t

5
5)

P

6

R8

8

6)

<----------- P
“

)

⅝. Λ/
■■ > X

i• — /
1

t. —

|
1 ^^___^_M^__.
л^ 1 X

7)
f____________________________ __ ___________

21


Продолжение
Ал гоp иτ м

Rx: =
C∕Π

Fx = 0
β
p r: =
F L0

γ Rx: =

а

C∕Π
БП
------- T
β
t: = Rx - 1
p: = i — t — 2
r: = n — t
R8≈b
b: = p
£: = 2
БП
-Δ

Распределение
регистров
памяти

Коммен­
тарии

8)

Конец
цикла

Останов
(8)

кон

Комментарии к алгоритму:
1) k = l дляопределения t и p;
2) начальное значение счетчиков остатков;
3) вычисление очередного остатка;
4) определение перехода по ключу k: для k = 0 на p;
для ⅛ = 1 на κ;
5) серия *: определение числа L0, используемого
в утверждении (5);
установка ключа k = 0, определяющего переход
к вычислению остатка от деления аш на b, равного,
в силу (5), остатку от деления числа an на b;
6) определение перехода по ключу k: для k = 0 на ρ;
7) увеличение счетчика остатков;
8) останов для чтения промежуточных остатков и
выполнения π. 2 приведенной выше инструкции по
исполнению алгоритма;
9) подготовка выходных параметров, необходимых
ддя исполнения серии команд *, и подготовка ключа
k = 2, определяющего переход к серии команд *.
22


Примечание. Цепочка (1), (2), (3), (7) и (8) пред­
ставляет собой эволюцию задуманного алгоритма ре­
шения задачи о делении с остатком числа an на b.

Программа для МК-54
Номер
команды

σ
Δ

Команда

Номер
Код 'Комментарии ι команды

4—
50

00
01

x→∏a
c∕π

02
03
04

x→∏c
x→Π0
C∕Π

05

x→∏b

4L

ввод b

06
07

1
x→∏2

01
42

k: = \

08

x→∏l

41

/: = 1

09
10

∏→xa
x→∏3

643

r. =a

11
12
13

∏→x3
∏→xb

63
6L
11

^χ∙.-r-b

14
15

Fx≥0
53

59
53

Fx≥0
α

16
17
18

∏→x3
∏→xb

63
6L
13

‰=4

19
20
21

x→∏9
K∏→x9
∏→x9

49
Γ9
69

Rx' = [Rx]

22
23

∏→xb
×

6L
Rχ∖ =Rχ • b
12

24
25
26
27

∏→x3

r∙.-r-Rx

x→∏3

63
14
11
43

28

∏→x2

62

Rx.≈k

29
30

Fx≠0
64

57
64

Fx≠0
P

Код

Комментарии

2

02
11

Rχ, = k-2

ввод а

31
32

ввод n
LQ: —п

33
34

Fx = 0
56

5E
56

Fx = 0
κ

35

∏→x3

63

Rx.≈r

36
37

Fx≠0
43

57
43

Fx≠0
ε

38
39
40

∏→x5
+
x→Π0

65
10 LOr=‰+∕
40

41
42

БП
47

^Γ

40
50

Команда

ε

ψ
b

a

κ

51
47

БП
4?

43
44
45
46

∏→x5
∏→x6
+
x→Π0

65
66
10
40

Δ0: = p ^-1

47
48

0
x→∏2

00
42

^:=0

49
50

∏→x8
x→∏b

68
4L

b.≈R8

51
52

БП
09

51
09

БП
σ

53

∏→x2

62

Rx:=k

54
55

Fx≠0
64

57
64

Fx≠0
P

56
57
58
59

∏→xl
1
+
x→∏l

61
01
10
41

i z = i ^- 1

60

∏→x3

63

Rx:=r

23


Продолжение
Номер
команды

61

P

V

Команда

Код

Комментарии

c∕π

50

Останов
для чтения
промежу­
точных ос­
татков и
выполнения
π. 2 ин­
струкции
по испол­
нению
алгоритма
Fx = 0
β

62
63

Fx = 0
76

5E
76

64
65
66
67

∏→x3
∏→xa
×
x→∏3

63
612
43

r: — г • а

68
69

FL0
11

5Γ
11

FL0
Δ

70
71
72

∏→x3
∏→xa

63
6—
13

Rx:=а

73

c∕π

50

останов

Номер
команды

β

Команда

Код

Комментарии

74
75

БП
70

51
70

БП
T

76
77
78

1

01
11
45

t,=Rx- 1

x→∏5

79
80
81
82
83
84

∏→xl
∏→x5

85
86
87
88

∏→xc
∏→x5

2

x→∏6

61
65
11
о: =i-t-2
02
11
46

r∙.≈n-t

x→∏3

6[
65
11
43

89
90

∏→xb
x→∏8

6L
48

R8: = b

91
92

∏→x6
x→∏b

66
4L

b:^p

93
94

2
x→∏2

02
42

^:=2

95
96

БП
11

51
11

БП
Δ

9. Для микро-ЭВМ нет проблем
Решая задачу о делении с остатком an на b для
микро-ЭВМ, нам полностью удается исключить ручной,
труд. Разумеется, будут наложены некоторые ограни­
чения на величины чисел a, n и b. Мы потребуем, чтобы
значения n и аЬ не превосходили число 999999. Цело­
численное значение, присвоенное вещественной пере­
менной (а именно такие переменные мы и будем исполь­
зовать в программе), Бейсик печатает как целое, если
в нем не более шести цифр, но во внутреннем представ­
лении рассматривает его как число с плавающей за­
пятой. При этом отсутствие десятичной точки в кон­
станте предполагает наличие ее за последней цифрой
справа. Проанализировав алгоритм (9), который мы
приводим дальше, можно легко убедиться, что при
24


Алгоритм

DIM R (5000)
Ввод A, N, В
7?(1): = остаток (А, В)
если k= 1
------------ то γ

все
R:=R(l)*A
для /от 2 до N
нц
R (/): = остаток (R, В)
для / от 1 до /— 1
нц
если R(/)=R (j)
---------------------- то α
все
нц
R:=R^*A
нц
Uγ PRINT R (N)
------- GOTO β
→ap=N~Hi
P: = l-J
Т: = остаток (R, P)

(9)

если L = 0
τoΛ-∕-l
иначе к = L + J — 1
все
PRINT R (I)
÷βEND
указанных ограничениях на n и ab значения всех, ис­
пользуемых в соответствующей этому алгоритму про­
грамме, переменных будут не более, чем шестизнач­
ными, а значит, будут оставаться целыми.
Кроме того, будет наложено дополнительное огра­
ничение на значение числа b, зависящее от длины
массива, который мы зарезервируем для хранения
25


остатков от деления ai на b (i==l, 2, 3, ...). Ранее
мы последовательно заносили эти остатки в таблицу
до тех пор, пока не обнаруживалось совпадение оче­
редного остатка с некоторым предыдущим. Сейчас мы
можем поручить эту работу машине. Она будет запи­
сывать остатки в специально зарезервированную
область в памяти, размерность которой описывается
в Бейсике оператором DIM. Поэтому, если для резерви­
рования такой области в программе будет задан, на­
пример, оператор DIM R (5000), то значение b не
должно превосходить число 5000.
Итак, опишем алгоритм решения задачи, предна­
значенный для реализации ее на Бейсике. Сравните
его с алгоритмами (7) и (8). Не правда ли, алгоритм,
составленный для программирования на языке высокого
уровня, читается и воспринимается легче. В нем про­
зрачнее вырисовывается схема решения в целом.

Программа на Бейсике
5 REM ГЛАВА Ь ПАРАГРАФ 9
10 DIM R<5000)
20 PRINT 'ВВЕДИТЕ ОСНОВАНИЕ СТЕПЕНИ А'
39 INPUT А
40 PRINT 'ВВЕДИТЕ ПОКАЗАТЕЛЬ СТЕПЕНИ N'
50 INPUT N
60 PRINT 'ВВЕДИТЕ ДЕЛИТЕЛЬ В'
70 INPUT В
80 R<D=A-INT<A×B)*B
90 IF №1 THEN 180
100 R=R<D*A
110 FOR 1=2 T0 N
120 R<I)=R-INT(R∙'B)*B
130 FOR J=1 ТО 1-1
140 IF R<I)=R<J> THEN 200
150 NEXT J
160 R=R СI)*A
170 NEXT I
180 PRINT 'ОСТАТОК PABEH'R<N>
190 GO ТО 280
200 R=N-.J+1
210 P=I-J
220 L=R-INT<RzP)*P
230 IF L<>0 THEN 260
240 I≈I-1
250 80 ТО 270
260 I=L+J-1
270 PRINT 'ОСТАТОК РАВЕН 'R<I>
280 END

Примечание. Бейсик допускает использование пере­
менной и массива с одним и тем же именем. В програм­
ме, приведенной выше, это переменная R и массив R.
26


1. О чем эта глава
Мы считаем главной высказанную в главе 1 идею
о гипотезах. Чем мощнее и продуктивнее вычислитель­
ное средство, тем более эффективно служит оно этой
идее, следовательно, тем более эффективно оно в руках
исследователя. Целью данной книги не является сколь­
ко-нибудь регулярное развитие одной какой-то теории,
основанное на широком обсуждении гипотез и качест­
венной их проверке с помощью вычислительных средств.
Скорее наоборот, мы считаем необходимым пересмотр
некоторого круга разнообразных задач, на которых
можно подтвердить еще раз сказанное ранее. Кроме то­
го, возможно увидеть что-то новое.
С этой целью обратимся к серии классических голо­
воломок Генри Э. Дьюдени. Даже беглое знакомство
с книгами этого замечательного мастера наводит на
мысль о том, что ряд задач и головоломок носит
явно алгоритмический характер. Уяснение этого факта
и служит подчас ключом к их решению. Правда, часто
при этом существуют дополнительные хитрости, позво­
ляющие упростить решение. Они, как правило, основаны
на более тонком проникновении в суть дела. Но все же
уяснение алгоритмичности проблемы и описание cooτветствующего алгоритма — явление принципиально
важное и требующее серьезного внимания. Тем более
что недалеко то будущее, когда именно такие умения
будут считаться особенно ценными качествами исследо­
вателя, вооруженного персональной ЭВМ.
Нас, правда, могут спросить, почему же мы все-таки
обратились к сборнику головоломок, а не выбрали для
своих целей еще несколько классических задач или
даже теорий. Думаем, что причины этого достаточно
ясны — это желание сделать книгу интересной и доступ­
ной более широкому кругу читателей; указать желаю­
щим богатый источник увлекательных задач, примени­
27


мых также как для кружковой, так и для самостоятель­
ной работы. Наконец, и мы хотим подчеркнуть это особо,
показать читателю, что многие головоломки могут слу­
жить также и головоломками для программирования.
2. Три различные цифры

Задача ([2], задача 121). Профессор предложил
студентам найти все числа, составленные из трех раз­
личных цифр, каждое из которых делится на квадрат
суммы своих цифр. Так, в случае числа 112 сумма цифр
равна 4, квадрат ее равен 16 и 112 делится на 16, но,
к несчастью, 112 составлено не из трех различных цифр.
Сумеете ли вы найти все возможные решения за­
дачи?
1. Суть проблемы. Число, составленное из трех цифр
a, b и с, может быть записано так:
100α+106 + c.
От нас требуется перечислить всевозможные упорядо­
ченные тройки цифр (α, b, с), удовлетворяющие следую­
щим условиям:
1) о ≠ 0 — старшая цифра числа всегда отлична от
нуля;
2) a ≠ b, b ≠ с, a ≠ с — цифры должны быть раз­
ными;
3) (100α + 106 + с) • (α ψ b + с)2 — число, состав­
ленное из этих цифр, делится на квадрат их суммы.
2. Имея в запасе всего 10 цифр, мы можем пред­
ставить себе перебор и проверку всех вариантов:

а: = 1
пока a ≤ 9
нц b:=0
пока b ≤ 9
нц
если a ≠ b
то с: =0
пока с≤9
нц
если b ≠ с и a Φ с

(1)

ТО если (100α + 106 + с) ∙ (α +
+ b + c)2
28


то напечатать число
abc
все
все
с: = с + 1
КЦ

все
b: = b + i
кц
a: = a + 1

кц

3. Теперь возникает вопрос о том, какое вычисли­
тельное средство будет применено для реализации этого
простого алгоритма. Начнем с наиболее доступного.
У нас в руках микрокалькулятор «Электроника МК-54».
Преобразуем алгоритм (1) к форме, удобной для
программирования на этом микрокалькуляторе. Перво­
начально подумаем над тем, как будет осуществляться
проверка условия
(100α + 106 + с) - (α + b + с)2.
Очевидно, нужно поступить так:
e: = 100a + 10& + c
f: = (а + b + с)2
если [у] ♦ f = e

(2)

то Rx: = e
C∕Π

все
Наш микрокалькулятор не имеет вывода на печать,
поэтому команда «напечатать число аЪс» реализуется
с помощью вывода результата на индикатор (Rx:=e)
иостанова (C∕Π) для прочтения (изаписи) полученно­
го результата. Кроме того, при внимательном рассмот­
рении этого фрагмента мы обязательно должны вспо­
мнить опыт, приобретенный в главе 1. А именно: если
окажется вдруг, что e < f (число меньше квадрата
суммы своих цифр). Тогда мы не сможем с помощью
последовательности команд x→∏9, K∏→x9, ∏→x9
e 1
осуществить выделение целой« части Гly|,
которая в этом

29


случае равна 0. Но тогда и £у] • f = 0 ≠ e. Таким
образом, фрагмент (2) естественно изменить следую­
щим образом (добавив проверку условия β≥∕?):
e: = 100a + 106 + c

f: = (a + b + c)2
Rx: = e — f

Fx≥0

(3)

то Rx: = e
C∕Π

ε все
Разумеется, эта проверка оказывается напрасной,
если бы вдруг оказалось, что всегда e^f и фраг­
мент (2) можно было бы сохранить в исходном виде.
На эту мысль наталкивает нас простая индукция.
Вот примеры:

123:
348:
756:
137:

(l+2÷3)2 = 36
(3÷4 + 8)2 = 225
(7 + 5÷6)2 = 324
(l+3 + 7)2=121

и
и
и
и

123>36;
348>225;
756>324;
137>121,

которые легко продолжить, имея под рукой все тот же
MK-54. Соблазнительно. Но тем, что не доказано, вос­
пользоваться нельзя. Но ведь производя вычисления
по алгоритму (1), мы попутно можем проверить эту
гипотезу. А если она подтвердится в процессе решения
основной задачи, то для ее полного установления
останется совсем немного — пересмотреть те трехзнач­
ные числа, у которых две или даже все три цифры
совпадают.
Вот вам и еще одна задача:
Верно ли, что любое трехзначное число боль­
ше либо равно квадрату суммы цифр, его составляющих. А если нет, то укажите числа, не
удовлетворяющие этому правилу.

,-к
' '

Для проверки гипотезы (4) нам придется внести
дополнительные поправки в фрагмент (3). Признаком
возникновения ситуации, опровергающей предполо­
30


жение, будем считать, например, последовательное
исполнение операторов
Rx: = 1
C∕Π

Так как при останове для чтения промежуточных
результатов на индикаторе будет высвечиваться трех­
значное число e, то выбор числа 1 в качестве признака
опровержения гипотезы является законным и не вызовет
путаницы. Попутно (раз уж пришлось к слову) поме­
тим для себя признак окончания счета по алгоритму (1).
Пусть им будет, скажем, последовательное исполнение
операторов
Rx: = 5
C∕Π
Это мы используем немного позже. Окончательно же
фрагмент (3) видоизменится так:
e:= 100α÷ 10& + c
f:=(a + b + cf
Rx: = e — f

Думаем, что читателю понятно, зачем появилась
метка φ и соответствующий ей переход БП φ после
останова для выдачи признака опровержения. Ведь за­
тем нужно возобновить нормальный ход исполнения
алгоритма (1). Заметим также, что если вдруг на инди­
каторе мы увидим признак опровержения, то, естест­
венно, сможем узнать о том, какое же число доставило
нам эту неприятность, вызвав на индикатор содержимое
того регистра памяти, в который будут последовательно
заноситься значения чисел e. Многоточия означают
31


пропущенные части алгоритма (1). Нам ясно также
что фрагмент от метки ε в (5) должен быть помещен
после всего алгоритма (1), чтобы не вносить в него
никаких нарушений.
Прежде чем записывать алгоритм (1) в форме
предназначенной для программирования на MK-54, про­
анализируем его еще раз в целом. Алгоритм пред’ставляет собой три вложенных цикла. Один из них (внешнии) может быть организован с помощью оператора
rL0, так как параметр цикла а изменяется не от 0 до 9
(как b и с), а от 1 до 9. С помощью оператора FL0 мы
можем организовать этот цикл, изменяя параметр а от
9 до 1 с шагом —1. Для этого начальное значение
а
9 заносится в регистр 0, а, получив в этом регистре
на девятом витке в цикле 0, мы тем самым выработаем
признак выхода из цикла.
Запишем, наконец, преобразованный алгоритм.

Ал гоp иτ м

Величины и
соответствую­
щие им регис­
тры памяти

вели­
чина

алг три различные цифры (нат a, b, ct e)
арг α, b, с
рез e
и«»
rr∖. = Γу∖
π m LΛJ.
—* α b: = 0
→- γ пока 6≤9
нц

а
b
с
e

Ре­
гистр

а
b
с
7

(?сли a ψ b

то с: = 0
→ β пока с ≤ 9
нц

если b≠c и a=≠=c

-----------------

32

то e: = 100a +
+ 106 + c
f: =(a + b +
+ c)2
Rx: = e — f
Fx ≥ 0________
~^

f

8

Приме­
чания


Продолжение
Величины и
соответствую­
щие им регис­
тры памяти

А л г σp и τ м

вели­
чина

Приме­
чания

ре­
гистр

/ √V

—• ε

■

если

~

∙f=e^

то κx.=e
C∕Π
> φ все

Чтение
проме­
жуточ­
ного ре­
зультата

все

-----------кц

c: = c+ 1

Etee

1>: = & + l
------ кц
FL0
--------- α
→∙ ω ‰ == 5
С/ ∏
БГ1
--------- ω
L÷ ∣з Rx: = 1
С/ ∏
БГ[
--------- φ
κ<)H

Останов

Конт­
роль ги­
потезы

4. Программа для МК-54

2—2740

Номер
команды

Команда

Код

Комментарии

00
01

9
x→Π0

09
40

L0:=9

a

02
03

0
x→∏B

00
4L

6:=0

T

04
05
06
07
08

9
Π→XB
— .
Fx≥0
80

09
6L
11
59
80

пока b ≤ 9

o ψ

33


Продолжение
Номер
команды

Команда

Код

09
10
11
12
13

Π→x0

—
Fx≠0
74

60
6L
11
57
74

14
15

0
x→∏c

00
4[

16
17
18
19
20

9
∏→xc
—
Fx≥0
74

09
6[
11
59
74

21
22
23
24
25

Π→xB
∏→xc
—
Fx≠0
po

6L
6[
11
57
68

26
27
28
29
30

Π→x0
∏→xc

60
6[
11
57
68

β

34

Π→XB

Fx≠0
68

Комментарии

НЦ

если α≠⅛

——∣

oo

c:=0

пока c≤9
oo >^

НЦ
если b=≠=c и
I

... a≠c

-

^

01
00
00
60
12
01
00
6L
12
10
6[
10
47

e: = 100a + 10b + с

∏→xc
÷
+
Fx2
x→∏8

60
6L
θ[
10
10
22
48

f: = (e + b + с)2

—

11

Ях: = e — /

31
32
33
34
35
36
37
38
39
40
41
42
43

1
0
0
∏→xa
×
1
0

44
45
46
47
48
49
50

Π→x0

51

Π→XB

×
+
∏→xc
+
x→∏7
Π→XB


Продолжение
Номер
команды

Команда

Код

Комментарии

52
53

Fx≥0
86

59
86

Fx≥0
ε

54
55
56

∏→x7
∏→x8

67
68
13

"-τ

57
58
59

x→∏9
K∏→x9
∏→x9

49
Γ9
69

Rx: = [Ях]

60
61

∏→x8
×

68
12

Rx: = Rχ. f

62
63
64
65

∏→x7

если ^J"j×

Fx=0
68

67
11
5E
68

66

∏→x7

67

Rx: = e

67

C∕Π

50

Останов для чтения
очередного резуль­
тата

68
69
70
71

∏→xc
1
+
x→∏c

6[
01
10
4[

с: = с 4- 1

72
73

БП
16

51
16

кц------- >β

74
75
76
77

Π→XB
1
+
x→∏B

6L
01
10
4L

b: = b + 1

78
79

БП
04

51
04

КЦ-------- >γ

80
81

FL0
02

5Γ
02

FL0
α

82

5

05

Rx.≈5

83
84
85

C∕Π
БП
82

50
51
82

Останов
БП
ω

φ

oo

о

ω

2*

×f = e

^—[

35


Продолжение
Номер
команды

ε

Команда

Код

Комментарии

86

1

01

Rx: = 1

87

c∕π

50

Контроль
гипотезы

88
89

БП
68

51
68

БП
φ

5. Счет по программе. Так как быстродействие
микрокалькулятора невелико (не более 0,5 с на выпол­
нение одной арифметической операции), то счет по
данной программе занимает весьма длительное время.
Однако не стоит огорчаться. Эта программа разового
использования. Можно уделить ей вечер, выполняя при
этом любую другую работу и в промежутках лишь
фиксируя результат вычислений. Вот как это выглядело
у одного из авторов. (Время указано достаточно при­
близительное, так как абсолютная точность в данном
случае в общем-то ни к чему.)
Действие

Время

19.35

Пуск

19.55

Получен первый результат
e = 972

20.05

β = 810

20.50

β = 605

21.00

e = 648

21.16

e = 512

21.38

e = 405

22.05

e = 324

22.20

Впервые появился признак
опровержения гипотезы:
Rx=∖
(А ведь прошло столько
времени, что гипотеза стала
казаться верной!)

22.26

e = 392

36

Примечания

∏→x7.
Читаем: e = 389.
Здесь
f = (3÷8 + 9)2 =
= 202 = 400. Таким обра­
зом, оказалось e < f.


Продолжение
Время

Действие

Примечания

22.27

^X=1

∏→x7; e = 398. Этого сле­
довало ожидать. При фик­
сированном a{a-3) числа
389 и 398 — парные, полу­
ченные перестановкой двух
последних цифр.
Возникает вопрос:

все ли числа, не удов­
летворяющие гипотезе
(4) — парные?

22.36

e = 243

22.40— Признак ‰=1 воспроиз­
23.10
водился 15 раз. Соответ­
ствующие числа e поме­
щены в правой колонке

23.15

e = 269,
287,
298,
139,
157,

278,
289,
129,
148,
158,

279,
297,
138,
149,
159

e=167,
176,
185,
189,
196,

168,
178,
186,
194,
197,

169,
179,
187,
195,
198

e=162

23.15— Признак Rx= 1
23.30
водился 15 раз

23.35

воспроиз­

Rx = b

Останов

Итак, нами найдены все числа, отвечающие усло­
виям задачи о трех различных цифрах. Это:
162, 243, 324, 392, 405, 512, 605, 648, 810, 972.
А вот числа, образованные тремя различными цифрами,
квадрат суммы которых превосходит само число, естест­
венно расположить так:
129
138
139
148
149
157
158
159
167
168
169
176
178
179
189

269
278
279
289
194

389
287
297
298

398

(6)

185
195
186
196

187
197
198

37


Здесь 8 чисел не являются парными и имеется 12 пар.
6. Выводы. 1) Программируя, будьте осторожны:
даже самый, казалось бы, очевидный факт еще не
есть факт достоверный.
Особенно опасно поддаться соблазну, упрощая
алгоритмы, сокращая лишние проверки и переходы,
принять за достоверное то, что лишь кажется очевид­
ным. Это может в некоторых случаях существенно
повлиять на логику всего алгоритма и повлечь за
собой целую серию (иногда весьма искусно замаски­
рованных) ошибок.
2) Составляя алгоритмы решения задач, приспосаб­
ливая их к тому или иному вычислительному средству,
можно встретиться с такими вопросами, которые
достойны именоваться самостоятельными задачами.
При этом могут возникать и любопытные головоломки.
Разве неинтересна задача?
Существуют ли трехзначные числа, у кото­
рых квадрат суммы цифр оказывается большим
данного числа? Если да, то сколько их и сколько
среди них парных?

(7)

Можно ли считать таблицы (6) ответом к зада­
че (7)? А каким был бы алгоритм (и соответствующая
ему программа) для микрокалькулятора MK-54, если
бы мы решали непосредственно задачу (7)? Можно ли
найти достоверный довод тому, чтобы оборвать испол­
нение алгоритма решения задачи (7), дойдя, скажем,
до проверки числа 400?
7. Исполнение алгоритма (1) на Бейсике. С учетом
принципа, положенного в основу фрагмента (2), алго­
ритм (1) очевидным образом переписывается на Бей­
сике. Проследите за тем, как каждое условие заменя­
ется в программе на противоположное. Это дает
возможность сохранить порядок следования строк
программы соответствующим существующему в алго­
ритме порядку.
С другой стороны, если мы хотим программировать
алгоритм (1) на Бейсике, то естественно подумать и над
тем, чтобы представить его в виде, наиболее удобном
для такого программирования. Ведь в данном слу­
чае мы имеем дело с тремя вложенными статичными
циклами (циклами с фиксированным числом повто-

38


^^МГЛАВА 2, ПАРАГРАФ 2л ПЕРВЫй ВАРИЙНТ
10 REM ЗАДАЧА 0 ТРЕХ РАЗЛИЧНЫХ ЦИФРАХ
зи A=ι
30 IF A>9 THEN 210
40 B=0
50 IF B>9 THEN 190
60 IF A=B THEN 170
7Θ C=0
80 IF C>9THEN170
90 IF B=C THEN 150
100 IF A=C THEN 150
110 Е=100ЖА+10ЖВ+С
120 F=<A+B+C>^2
HS IF INT<E×F>≡F<>E THEN 150
140 PRINT 'E='E
150 C=C+1
160 GO ТО 80
170 B=B+1
180 GO ТО 50
190 A=A+1
200 GO ТО 30
210 PRINT 'ВЫЧИСЛЕНИЯ ЗАВЕРШЕНЫ
220 END

рений) и поэтому
щему виду:

(1)

можно привести к следую­

для А от 1 до 9
нц
для В от 0 до 9
нц
если A≠B
то для С от 0 до 9
нц
если В ψ С н_А ≠ С
(9)
тоЕ: = 100Л + ЮВ + С
F: = (A + B + Cf
если [4-lA = E
L* J
то напечатать число
ЖГ
все
все
кц
все
кц
кц
39


Алгоритм в виде (9) читабельнее: он легче восприни­
мается и более естественен для перевода на
Бейсик. Вот как выглядит соответствующая про­
грамма:
5 REM ГЛАВА 2/ ПАРАГРАФ 2/ ВТОРОЙ ВАРИАНТ
10 REM ЗАДАЧА 0 ТРЕХ РАЗЛИЧНЫХ ЦИФРАХ
20 FOR A=1 ТО 9
30 FOR B=0 ТО 9
40 IF A≈B THEN 130
50 FOR C=0 ТО 9
60 IF B=C THEN 120
70 IF A=C THEN 120
80 E=100*A+10*B÷C
90 F≈<A+B+C)^2
100 IF INT<E/F)*F<>E THEN 120
110 PRINT ∙,E='E
120 NEXT С
130 NEXT В
140 NEXT А
150 END

/1лч

(10)

8. Примечание. Работая с Бейсиком, мы не испы­
тывали трудностей, приведших к формулировке зада­
чи (4) (или.в другом варианте (7)). Все решилось
куда проще. И если бы мы работали только с Бейсиком,
наверно, нас и не заинтересовал бы этот вопрос. А всетаки немного жаль... Правда, быстродействие микроЭВМ таково, что оно способно нас утешить: проверьте,
нужно ли тратить целый вечер на исполнение програм­
мы (10)?
3. Цифры и кубы
Задача ([2], задача 122).
Профессор Рэкбрейн попросил недавно своих моло­
дых друзей найти все пятизначные квадраты, у которых
сумма чисел, образованных двумя первыми и двумя
последними цифрами, равна точному кубу. Так, если мы
возьмем квадрат числа 141, равный 19881, и прибавим
81 к 19, то получим 100 — число, не являющееся, к со­
жалению, точным кубом.
Сколько всего существует решений?
Первое натуральное число, квадрат которого явля­
ется пятизначным,— 100. Оно не удовлетворяет усло­
виям задачи. Легко также установить, что последнее
натуральное число с таким свойством — 316(^^^9999 ≈
≈316,22618).
40


1. Алгоритм и соответствующая программа для
микрокалькулятора.
Величины и
соответст­
вующие им
регистры
памяти

Ал гоp иτ м

Приме­
чания

вели- Ре­
чина гистр
а
а
b
b
с
с

алг цифры и кубы (нат a, bi с)

нач нат R3, R4, h, R3 цел L0, L∖ вещ Rx, k
a: = 100
R3: = 100
^4: = 1000
L0: = 216
^: = l/3
r→∆ ^5:=9
Al:=3

R3
R4
L0
k
R3
U

3
4
0
2
5

r
Rx
h

d
x
6

1

b

a2
остаток (b, R3)
Rx = [b/R4]
h:=r + Rx
a≈[hk]
если с • с • c-h
— то γ

*
**

***
IV*
V*

иначе c: = c + l
если с • с • c = h

•

то
→γ Rx:-RK{3)
C∕Π
FU____________
--------- V
FLO <
---------- Δ

VI*

все<
все
FL0

ω Rx: =5
C∕Π
БП

------ω
кон

41


Примечания к алгоритму

*) Если /.0: = 216, значит, ниже будет организован
цикл с помощью оператора FL0.
»♦) Если Ll: = 3, значит, ниже будет организован
цикл с помощью оператора FL1.
*♦*) Почему в этом фрагменте мы не написа­
ли вместо ЯЗ непосредственно 100, вместо R4 — 1000,
а присвоили соответствующие значения R3 и R4
до цикла?
IV») Почему мы не употребили с: = [Л1/3], а вы­
числили k = 1 /3 до цикла?
V») Обратите внимание на то, как реализован
в программе этот фрагмент.
VI») В регистр x вызывается содержимое того
регистра, адрес которого получается увеличением со­
держимого регистра 5 на 1: косвенный вызов через
регистр 5 (см. [1]).
Номер
команды

Команда

Код

Комментарии

00
01
02
03

1
0
0
x→∏a

01
00
00
4—

a: = 100

04

x→∏3

43

^3: = 100

05
06
07
08

1
0
×
x→∏4

01
00
12
44

^4: = 1000

09
10
11
12

2
1
6
x→Π0

02
01
06
40

L0: = 216

13
14
15
16
17

1
Bt
3

£: = 1/3

x→∏2

01
0E
03
13
42

18
19

9
x→∏5

09
45

^5:=9

20
21

3
x→∏l

03
41

Ll:=3

Δ

42


Продолжение
Номер
команды

α

Команда

Код

Комментарии

∏→xa
22
1
23 ,
24
+
x→∏a
25

6—
01
10
4—

a:=a+l

26
27

Fx2
x→∏b

22
4L

b: == с?

28
29
30

∏→x3
—
x→∏9

63
13
49

31
32
33
34
35
36
37
38

K∏→x9
∏→x9
∏→x3
×
∏→xb
÷÷
—
x→∏d

Γ9
69
63
12
6L
14
11
4Γ

39
40
41
42
43
44

∏→xb
∏→x4
√x→∏9
K∏→x9
∏→x9

6L
64
13
49
Γ9
69

45
46
47

∏→xa
÷
x→∏6

6Γ
10
46

48
49
50
51
52
53
54

∏→x2
∏→x6
Fxy
x→∏9
K∏→x9
∏→x9
x→∏c

62
66
24
49
Γ9
69
4[

55
56
57
58
59
60
61
62

Bf
Bf
×
×
∏→x6
—
Fx≠0
75

0E
0E
12
12
66
11
57
75

63
64
65
66

∏→xc
1
÷
x→∏c

6[
01
10
4[

г: = остаток {by #3)

‰-. = [^4]

Л:=г + Ях

с: = [h *]J

«

если
с • с • с=h
то

. r

'

_________

c: = c+ 1

43


Продолжение
Номер
команды

Команда

Код

Bf
Bt
×
×
∏→x6

Комментарии

67
68
69
70
71
72
73
74

Fx = 0
81

0E
0E
12
12
66
11
5E
81

75
76
77
78

K∏→x5
C∕Π
FL1
75

Γ5
50
5L
75

чтение
a, a2, с

79
80

FL0
18

5Γ
18

FL0
Δ

о

81
82

FL0
22

5Γ
22

FL0
α

ω

83
84
85
86

5
C∕Π
БП
83

05
50
51
83

Останов

У

если с • с • c-h

то-------------

о

Результат счета
Результат

Время

17.06
17.23
17.52
17.58
18.20

а

a2

с

пуск
152
237
251
стоп

23104
56169
63001

3
5
4

2. Алгоритм и соответствующая программа на Бей
сике.

^3: = 100
^4: = 1000
&: = l/3
для А от 100 до 316
нц
44


B:=A2
R: = остаток (В, R3)
L: = [B/R4]
H:==R + L
cι = [Hk] ^
если с • с • с = H
— то α
иначе с: -cψl
если с • с • c≠ H
----------------------------- ТО γ
-> α иначе PRINT А, В, С
все
все
L>γκu
5 REM ГЛАВА 2/ПАРАГРАФ 3
10 REM ЦИФРЫ И КУБЫ
28 R3=1Θ0
30 R4=1000
4Θ K=lz3
50 FOR A≈100 ТО 316
60 B≈A^A
70 R=B-INT<B/R3)*R3
80 L=INT<BzR4)
90 H=R+L
100 C≈INT<H^K)
110 IF C*C*C=H THEN 140
120 C=C÷1 .
130 IF C*C.*C<>H THEN 150
140 PRINT Алл/\₽В</'/С
150 NEXT А
160 END

4. Особое число

Задача ([2], задача 101). Какое число образовано
из пяти последовательных цифр (идущих не обяза­
тельно по порядку) так, что число, образованное пер­
выми двумя цифрами, умноженное на среднюю цифру,
дает число, образованное последними двумя цифрами?
(Например, если мы возьмем число 12896, то 12, умно­
женное на 8, дает 96. Но к сожалению, 1, 2, 6, 8, 9 не
являются последовательными цифрами. Так что этот
пример в качестве решения непригоден.)
В общих чертах описать алгоритм решения этой за­
дачи несложно.
1. Зафиксировать некоторое расположение (пере­
становку) пяти последовательных цифр a, bi c9 d9 e.
45


¾

1

2. Проверить для числа abcde (а 104 + b 103 + с 102 +
+ dlO + β) условия задачи.
3. Если число abcde является решением задачи, на­
печатать его.
4. Если возможно, то составить еще одну переста­
новку, отличную от предыдущих, и перейти в начало
алгоритма.
5. В противном случае завершить исполнение (оста­
нов).
Исполнение π. 1 полностью определяется результа­
том исполнения π. 4. Здесь принципиально только то,
какую перестановку надо зафиксировать первый раз.
Допустим, что эта перестановка (0, 1, 2, 3, 4). Чтобы
не уменьшать общности, можно считать, что в таком
расположении эти цифры образуют число 1234; первые
же две цифры образуют число 1 и средняя цифра —
это 2. Тогда исполнение π. 4 может быть задано по
следующей схеме:
а) последовательный перебор всех перестановок
пяти фиксированных цифр;
б) если возможно, совершить сдвиг по последова­
тельности цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 на одну цифру
вправо и перейти к а);
в) в противном случае перебор всевозможных пере­
становок пяти последовательных цифр завершен.
Таким образом, алгоритм решения задачи будет
построен как только мы сумеем организовать процедуру
последовательного перебора всех перестановок пяти
фиксированных последовательных цифр. Отвлекаясь от
конкретной ситуации, обнаруживаем, что мы вплотную
подошли к задаче о построении алгоритма, воспроизво­
дящего (без повторений) все перестановкип чисел. Этот
алгоритм хорошо известен и достаточно подробно
изложен, например в [3]. Опишем его (при n = 5), от
чего рассуждения не утратят общности. Алгоритм со­
ставлен так, что в процессе его исполнения переста­
новки n чисел располагаются лексикографически
(в словарном порядке). Это значит, что перестановки
сравниваются слева направо поэлементно. Больше та,
у которой раньше встретился элемент, больше соот­
ветствующего ему элемента во второй перестановке.
(Например, если S = (3, 5, 4, 6, 7), a L = (3, 5, 6, 4, 7), то
δ<L.) Принцип работыалгоритма разъясним на при­
мере. Допустим, необходимо воспроизвести все пере­
46


становки цифр 3, 4, 5, 6, 7. Первой перестановкой
считаем перестановку
(3, 4, 5, 6, 7).

Последней

восцроизводимой перестановкой
(7, 6, 5, 4, 3).

будет

Предположим, что на некотором шаге работыалгоритма получена перестановка
P = (5, 6, 7, 4, 3).
Для того чтобы определить непосредственно сле­
дующую за ней перестановку, необходимо, пересматри­
вая данную перестановку справа налево, следить за тем,
чтобы каждое следующее число было больше предыду­
щего, и остановиться сразу же, как только это правило
нарушится. Место останова указано стрелкой:
(5, 6, 7, 4, 3).
t
Затем вновь просматриваем пройденный путь (cπpaва налево) до тех пор, пока не дойдем до первого
числа, которое уже больше отмеченного. Ниже место
второго останова отмечено двойной стрелкой:
(5, 6, 7, 4, 3).
t ft

Поменяем местами отмеченные числа:
(5, 7, 6, 4, 3).
й t
Теперь в зоне, расположенной справа от двойной
стрелки, упорядочим все числа в порядке возрастания.
Так как до сих пор они были упорядочены по убыванию,
то это легко сделать, перевернув указанный отрезок.
Получим:

Q = (5, 7, 3, 4, 6).
^
Q и есть та перестановка, которая должна воспроизво­
диться непосредственно после P,
Действительно, P < Q, так как, пересматривая эти
перестановки слева направо, видим, что первые элемен­
ты у них одинаковы(Р(1)==ф(1) = 5), a P(2)<Q(2),
(P(2) = 6, Q(2) = 7). Пусть существует такая перестанов­
ка R, что P<R<'Q. Тогда P(l) = ^(l) = Q(l). По
47


построению же Q(2) — это наименьшее во множестве
Q∖Q(1) = {3, 4, 6, 7}число, такое, что Q(2) > P(2). Поэто­
му для ^(2) верно одно из двух равенств: R(2) = Q(2)
или #(2) = P(2). Но так как в P элементы, начиная с P(3),
убывают, то из P<zR следует, что если P(2)-R(2∖
то и P = R. Аналогично, так как в Q элементы, начиная
с Q(3), возрастают, то из # < Q следует, что если
R(2) = Q(2), то и R = Q.
Теперь, когда в общих чертах уяснены все основные
принципы (говорят, что принципиально задача реше­
на), можно приступить к обсуждению деталей, поэле­
ментной прорисовке всего алгоритма. По сложившейся
уже схеме вначале будем создавать алгоритм, пред­
назначенный для MK-54.
1. Уже оговорено, что первоначально фиксируемой
будет перестановка (0, 1, 2, 3, 4). Необходимо решить,
какие регистры памяти будут отведены для хранения пя­
ти цифр этой, а затем и каждой последующей переста­
новки? Каким будет фрагмент программы, обеспечи­
вающий заполнение этих регистров памяти?
Условимся зарезервировать для наших целей регист­
ры R5, R6, R7, R8, R9. Почему именно их? Уже при
первых грубых прикидках понятно, что нам придется
организовывать несколько счетчиков, а также (осу­
ществляя переворот отрезка перестановки) прибегать
к косвенным переадресациям, причем через такие
регистры памяти, в которых происходит как уменьшение
на 1 при переадресации (что необходимо, когда про­
смотр перестановки идет справа налево), так и увели­
чение на 1 (что необходимо, когда просмотр переста­
новки идет слева направо). А для этого необходимо,
как минимум регистр R4 не занимать. Удобно также
элемент перестановки, хранящийся в регистре Ri, обо­
значать через Ri. Еще об одном. Ощущается сразу, что
программа ожидает быть длинной, так что под угрозой
возможность размещения ее в программной памяти
MK-54. Поэтому будем считать, что начальное состоя­
ние всех регистров памяти — нулевое (перед началом
счета память необходимо почистить). Отсюда, если в
программе впервые встречается некоторая переменная,
то можно считать, что изначально ей уже присвоено
значение, равное 0.
Последнее, что надо учесть: в схеме а), б), в) преду­
смотрено 6 сдвигов (по пять цифр) по последователь­
ности 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Пересмотрены все
48


перестановки цифр 0, 1, 2, 3, 4 — осуществляем сдвиг
на одну цифру и переходим к группе 1, 2, 3, 4, 5.
И так — 6 раз. Для реализации счетчика этих сдвигов
предусмотрим переменную d.
Опишем, наконец, обсужденный фрагмент алго­
ритма.
Δ Rx:=d-6
*
Fx≠0
*------- Y
на останов
**

^4: = 4<-------Ll:=5
Rx:=d
---- >ω RR^γ. = Rx
Rx: = Rx^ 1
FU___________

------- ω

**
⅛
*
IV
V
*

^ .
к фрагменту про­
верки условий за­
дачи для числа
R5R6R7R8R9,
составленного из
соответствующих
цифр Ri

*) К этому фрагменту мы должны обращаться 6 раз.
6 раз мы заносим в регистры ^5 — ^9 новую группу из
5 цифр [(0, 1, 2, 3, 4), затем (1, 2, 3, 4, 5), ..., наконец,
(5, 6, 7, 8, 9)], все перестановки которой затем подвер­
гаются проверке. Для организации таких обращений
пометим меткой Δ входную строку этого фрагмента.
**) Код седьмого обращения (d = 6) служит сигна­
лом к окончанию работы алгоритма.
***) Для заполнения регистров #5—R9 будет орга­
низован цикл оператором FL∖. В этом цикле должно
быть 5 повторений.
IV*) При d-м обращении к фрагменту наимень­
шим числом в заносимой в память группе цифр будет
число d.
V*) Первоначально в регистр 4 занесено число 4:
^4: =4. Здесь же оператор RK{^∖ =Rx осуществляет
занесение в регистр с адресом R4 +1 содержимого
регистра x, которое при каждом повторении в цикле
увеличивается на 1.
49


2. Фрагмент проверки условий задачи для числа
R5R6R7R8R9.
μ Rx: = (10-R5 + Rty-R7
Rx: = lO-R8 + R9
Rx: = Ry — Rx
Fx = 0________________________
_____ Ψ
C∕Π<-------------------------ψ формирование новой перестановки
цифр
Rb, R6, R7, R8, R9

*
**
***
IV*

*) Входная строка этого фрагмента должна иметь
метку, так как к нему мы будем переходить не только
после фрагмента заполнения регистров R5—R9 новой
группой цифр, а (и в основном) после исполнения того
фрагмента, который завершает формирование новой
перестановки из этой группы цифр.
**) Выполняя оператор 7?х: = 10-Я8 + #9, мы пере­
мещаем прежнее содержимое регистра Rx (число
(10∙^5 + ^6) ’R7) в регистр у.
***) Если числа 7?z/ = (10-7?5 + ^6)-^7 и Rx =
= ∖0∙R8 + R9 совпадают, значит, нужно совершить
останов для прочтения числа R5RQR7R8R9 = R5 • 104 +
+#6 • 103 + ^7 • 102 + √^8 • 10+^9, удовлетворяющего
условиям задачи. Правда, мы не предусматриваем вы­
вод этого числа на индикатор, так как для этого
перед C∕Π надо было бы поместить оператор
Rx: = R5 • 10000 + R6 • 1000 + R7 • 100 + R8 • 10 + R9
исполнение которого займет большую часть столь обе­
регаемой нами программной памяти. Поэтому, если со­
вершится останов и на индикаторе будет высвечи’
ваться число 0 (ведь Ry—Rχ = Q)t мы сможем прочи­
тать полученное число, последовательно вызывая на
индикатор все его цифры, начиная со старшей: ∏→x5;
∏→x6; ∏→x7; ∏→-x8; ∏→x9.
IV*) Формирование новой перестановки цифр R5,
R8, R7, R8, R9 должно следовать сразу же за описы­
ваемым фрагментом, так как переход к этой процедуре
осуществляется при любом исходе проверки условий
задачи для числа, образованного предыдущей πepecτaновкой этих цифр.
Формирование новой перестановки цифр R5, R6, R7,
δ0


^8, Я9 процесс многоактный и мы опишем его в не­
скольких фрагментах, следуя рассмотренному в начале
этого параграфа примеру.
3. Первый просмотр перестановки цифр (Я5, R6, R7,
R8, R9) справа налево.

ψ ^0: = 10
Ll: = 4
---- >α Rx:=RK(0)
Rx:=RK(0)
Rx:=Ry-Rx
Fx<0
----------- ε
Запомнить номер
регистра, содер­
^O: = W+1*
жащего первую
отмеченную цифРУ
FL1
------------a
d:=d+l^
БП

*
**
***
IV*
V*

VI*

*) Метка ψ описана в π. 2 как метка входной строки
в процедуре формирования новой перестановки цифр
R8, R6, R7, R8, R9.
**) Ll:=4, так как мы имеем 4 пары сравниваемых
цифр: (R8, R9); (R7, R8); (R6, R7); (R5, R6), а процесс
сравнения будем описывать в цикле, организуя его
оператором FLΛ. ^0: = 10, так как этот процесс будет
описываться как многократно воспроизводимый акт,
внутри которого последовательно изменяются адреса
двух соседних фиксируемых регистров, уменьшаясь при
всяком повторении на 1, в силу чего обеспечивается
пошаговое передвижение фиксируемой пары регистров
из крайнего правого положения в крайнее левое.
Поэтому последовательный вызов содержимого этих ре­
гистров на индикатор должен осуществляться косвенно
через такой регистр памяти, обращение к которому
производит уменьшение его содержимого на 1. Этим
свойством обладают регистры 0, 1, 2, З,и мы выбрали
для наших целей регистр 0. Первоначально же в ре­
гистр 0 естественно занести число 10 — на единицу
большее адреса крайнего справа среди регистров,
содержащих переставляемые цифры.
51


***) ЯЯ(0) — содержимое регистра, косвенно вызы­
ваемого через регистр 0. В регистр x (на индикатор)
вызывается содержимое того регистра, адрес кото­
рого получается уменьшением содержимого регист­
ра 0 на 1.
IV*) Допустим, что при сравнении цифр #8 и #9
оказалось, что Я8>7?9. Тогда мы должны перейти на
метку α, чтобы начать сравнение цифр ^7 и ^8. Для
этого предварительно нужно увеличить на 1 со­
держимое регистра ^0, иначе мы будем сравнивать
цифры ^6 и #7. И так для любой пары сравниваемых
цифр.
V*) Если вдруг окажется, что Ri<R(i-l), то цифру
Ri нужно отметить (в примере — стрелкой f). Для
этого надо запомнить номер i регистра, содержащего
эту цифру.
VI≠) К этои строке мы доберемся лишь тогда, когда
окажется, что^ просматриваемая перестановка цифр
была последней для данной фиксированной группы из 5
последовательных цифр. Следовательно, необходимо
вернуться к первому фрагменту (на метку Δ) для
выбора новой группы цифр. Предварительно увеличи­
вается на 1 число d, которое равно первой цифре в но­
вой группе.
4. Запомнить номер регистра, содержащего первую
отмеченную цифру.

zRa: = R0

|

*

*) Номер этого регистра в момент, когда отме­
чается первая цифра, содержится в регистре 0. Метка ε
была введена в π. 3.
Теперь, если следовать разобранному в начале па­
раграфа примеру, необходимо еще раз просмотреть
перестановку справа налево и отметить вторую цифру
(в примере — двойной стрелкой ft ), первую при следо­
вании справа налево, которая превосходит первую отме­
ченную. Затем последует перемена местами для отме­
ченных цифр. Но чтобы она состоялась, нужно будет
где-то в памяти запомнить первую цифру RK(a), адрес
которой хранится в регистре а. Затем на ее место
запишем вторую, а уже потом на место второй запишем
сохраненную первую — RK(a).
5. Сохранить в регистре с первую отмеченную цифру.
Rc: = RR(a).
52


6. Организовать второй просмотр перестановки
справа налево.

С

RQ: = 10
Rχ∙,≈RK(Q)-RK(a)
Fx≥0__________________
-η

*

Отметить вторую цифру*
и поменять ее местами
с первой

*) Вызывается цифра, хранящаяся по адресу R0 —
— 1, и сравнивается с первой отмеченной цифрой RK(a).
Пока RK(0) < RK(a∖ процесс пошагового сдвига влево
и сравнивания продолжается.
7. Отметить вторую цифру и поменять ее местами с
первой.
Rb: = R0
*
ΛK(α) = ΛK(6)
**
RK(b) = Rc
***
*) В регистре b запомнить номер регистра, содер­
жащего вторую отмеченную цифру. В момент ее фик­
сации этот номер содержится в регистре 0.
**) В регистр, содержащий первую отмеченную
цифру, записать вторую отмеченную цифру.
***) Значение первой отмеченной цифры, сохра­
ненное в регистре с, записать в регистр, в котором
была отмечена вторая цифра.
8. Перевернуть отрезок справа от позиции первой
отмеченной цифры.
R0: = 10
*
Проверить условие задачи
R4: = Ra
для вновь сформированного
числа
Rx.=R4-RQ + 2
R5RQR7R8R9
Fx<0____________
- μ
Rc:=RK(4)*----Ra:=R4
RK(a):=RK(0)
Rb:-R0
RK(b): = Rc
БП
β
53


*) Производя описываемую процедуру, мы сбли­
жаемся к центру одновременно с двух концов пере­
ворачиваемого отрезка, последовательно меняя местами
симметричные элементы. При этом средний элемент,
если он существует, остается неподвижным. Ясно, что
изначально мы должны были занести в регистр 0 число,
на единицу большее номера регистра памяти, содержа­
щего последний элемент отрезка, а в регистр 4 — число,
на единицу меньшее номера первого элемента отрезка
(а это как раз и есть номер регистра, в котором
была отмечена первая цифра).
Полагаем, что у вас уже достаточно опыта, чтобы
разобрать этот фрагмент алгоритма самостоятельно
9. Последний фрагмент — останов.
γ

^x:5 I
C∕Π I

*

*) Метка γ была введена нами для останова еще
в первом фрагменте. Так как во время останова
для чтения последовательности цифр, составляющих
искомое число, на индикаторе высветится число 0 (см.
фрагмент 2), а при выходе на останов индикатор, оказы­
вается, тоже высвечивает это число (см. фрагмент 1),
то мы сформулируем специальный признак останова —
число 5.
10. Подготовка к сборке алгоритма.
Пристальный анализ всех фрагментов перед сборкой
показывает, что оператор tf0:=10 (занимающий три
программные строки) встречается в фрагментах 3, 6 и 8.
Таким образом, будет занято 9 программных строк.
Кроме того, по стечению обстоятельств, в фрагменте 2
приходится еще два раза набирать число 10, на что
в общей сложности уйдет 4 программные строки. Присо­
вокупим их к девяти предыдущим. Итого, будет занято
13 строк программы. Теперь положим, что мы сфор­
мировали дополнительный вводный фрагмент: ^2: = 10.
Его реализация занимает три программные строки. За­
то вместо ^0: = 10 мы можем употреблять оператор
^0: = ^2, занимающий две программные строки. Если
бы речь шла только о фрагментах 3, 6 и 8, мы не
получили бы никакой экономии в программе (2 прогр.
c.×3 фрагм. + З прогр. c. = 9 прогр. c.), может лишь
имели бы незначительный выигрыш во времени счета
(но зато занимали бы лишний регистр памяти). Однако
54


во фрагменте 2 при таком подходе вместо набора числа
10 можно воспользоваться одним оператором Rx: =
= R2, занимаюЩим одну программную строку. Зна­
чит, в итоге будет сэкономлено две программные
строки.
*
Для чего это нужно? Когда будет полностью под­
готовлена программа для MK-54, вы увидите, что
именно эти две сэкономленные строчки позволили нам
поместить ее в программную память.
11. Еще раз изучим задачу.
Иной раз элементарный анализ задачи позволяет от­
вергнуть заведомо невозможные ситуации или, даже,
сильно упростить всю логику (к чему, правда, нужно
относиться очень осторожно). Так в нашем случае сле­
довало бы обратиться еще раз к фрагменту 1. Ока­
зывается, оператор Rx'. = d — 6, помеченный здесь мет­
кой Δ, может быть заменен на Rx: = d — 3. Это хотя
и не изменяет как-то программу, но все-таки чуть
не втрое сокращает время счета. Выигрыш суще­
ственный.
Почему же так? Просто, если рассматривать группу
цифр 3, 4, 5, 6, 7, то для любой перестановки (α, b, с, d, e)
цифр этой группы число abcde заведомо не будет отве­
чать условиям задачи, так как произведение ab • с
всегда будет числом трехзначным, отчего α5 • с ≠ de.
А если так, то то же справедливо уже и для групп
4, 5, 6, 7, 8 и 5, 6, 7, 8, 9. Доказать этот факт мы предо­
ставляем читателю.

12. Сборка алгоритма.
Ал гоp иτ м

алг Особое число (цел Я5, Я6, Я7,
Я8, Я9)
арг Я5, Я6, Я7, Я8, Я9
рез Я5, R8t R7, R8, R9

нач цел Я2, d, R4t £1, Я0, Ra, Rc,
Rb вещ Rx, Ry
R2: = 10

Распределение
регистров
памяти

Приме­
чания

вели­ ре­
чина гистр
Я5
Я6
R7
R8
Я9

5
6
7
8
9

R2

2

Вводный
фрагмент

55


Продолжение
Распределение
регистров
памяти

Ал гоpиτм

f→∆ R>с: = d - 3
F:<≠O____________________________

d

Приме­
чания

d

P

R<1: =4<_________________________
Ll:=5
Rx: = d
----- > ω RR(4) = Rx
Rx: = Rx 4- 1
FU_______________________
---------- ω
|

→μ ‰=(Λ2∙Λ5 + Λ6)∙Λ7<J
‰: = Я2 • Λ8 + R9
Rx: = Ry — Rχ
rx = υ_________
------ χ ^
(}∕∏ <—_________________________
u> ψ RQ: = R2
L1: = 4
—> α Rx: = RR(O)
Rx: ≈ RK(Q)
Rx: = Ry — Rx
Fx < 0_______________
------------ ε
|

R4
L1
Rx

4____
1____
x

Фраг­
мент 1

Фраг­
мент 2
Ry

_У

Чтение
резуль­
тата
Я5Я6"~
Я7Я8Я9
~R0~

0

Фраг­
мент 3

i

ЯО: = ЯО + 1 <-∣
FU___________________
------------ α

d: — d 4~ 1 ≤
’ БП
____л
---------- > ε Ra: = RQ
Rc.≈RK(a)

Ra

а

Rc

с

Rv: = R2
----------► η Rx: = RR(ty - RK(a)
Fx ≥0__________________________
---------------- η
Rb: = ЯО <--------------------RR{a}: = RR(b)
RK(b): = Rc
R0: = R2
R4: = Ra

'/
56

Фрагмент 4
Фраг­
мент 5
Фраг­
мент 6

Rb

b

I

Фраг­
мент 7


Продолжение
Распределение
регистров
памяти

Алгоρиτм

⅜

→ β Rx:=^4-R0 + 2
Fx<0_________________________
-------------------- μRc:=RK(4)

*---------------

Ra: = R4
RK(a): = RK(0)
Rb: = R0
RK(b): = Rc
БП
--------------------------- β
---------------> γ Rx: = 5
кон
C∕Π

Приме­
чания

Фраг­
мент 8

Останов
Фраг­
мент 9

13. Программа для МК-54
Номер
команды

Команда

Код

Комментарии

00
01
02

1
0
x→∏2

01
00
42

R2: = 10

03
04
05

∏→xd
3

6Γ
03
11

Rx: = d — 3

06
07

Fx≠0
95

57
95

Fx≠0
V

08
09

4
x→∏4

04
44

K4:=4

10
11

5
x→∏l

05
41

Ll: = 5

12

∏→xd

6Γ

Rx: = d

13

Kx→∏4

L4

RK(4): = Rx

14
15

1
+

01
10

Rx: = Rx + 1

16
17

FL1
13

5L
13

FL1
ω

18
19
20

∏→x2
∏→x5
×

62
65
12

Rx: = («2 ×

Δ

ω

μ

57


Продолжение
Номер
команды

Ψ

α

ε

58

Команда

Код

Комментарии

21
22
23
24

∏→x6
+
∏→x7
×

66
10
67
12

ХЯ5 + Я6)Х
ХЯ7

25
26
27
28
29

∏→x2
∏→x8
×
∏→x9
+

62
68
12
69
10

Rx: = Я2 ×
ХЯ8 + Я9

30

—

11

Rx: = Ry — Rx

31
32

Fx = 0
34

5E
34

Fx = 0
Ψ

33

C∕Π

50

Чтение числа
R5R6R7R8R9

34
35

∏→x2
x→Π0

62
40

RQ: = R2

36
37

4
x→∏l

04
41

Ll: = 4

38

K∏→xO

ГО

Rx: = RK(Q)

39

K∏→xO

ГО

Rx: = RK(Q)

40

_

11

Rx: = Ry — Rx

41
42

Fx<0
55

5[
55

Fx<0
ε

43
44
45
46

Π→xO
1
+
x→Π0

60
01
10
40

RQ: = ЯО + 1

47
48

FL1
38

5L
38

FL1
α

49
50
51
52

∏→xd
1
+
x→∏d

6Γ
01
10
4Γ

d: = d + 1

53
54

БП
03

51
03

БП
Δ

55
56

Π→xO
x→∏a

60
4-

Ra: = ЯО

≠


Продолжение
Номер
команды

Команда

1Код

57
58

K∏→xa
x→∏c

I
4[

Rc: = RK(a)

59
60

∏→x2
x→Π0

62
40

R0: = R2

61
62
63

K∏→xO
K∏→xa

ГО
1Г—
11

Rx: = RK(0)- RK(a)

64

Fx≥0
61

59
61

Fx≥0
η

Π→x0
x→∏b

60
4L

Rb: = RQ

η

65

66
67

β

Комментарии

RK(a): =
= RK(b)

68
69

K∏→xb ΓL
Kx→∏a L —

70
71

Π→xC
Kx→∏b

6E
LL

RK(b): = Rc

72
73

∏→x2
x→Π0

62
40

R0: = R2

74
75

∏→xa
x→∏4

644

R4: = Ra

76
77
78
79
80

∏→x4
Π→x0

64
60
11
02
10

Rx: = R4 —
-R0 + 2

81
82

Fx<O
18

83
84

K∏→x4
x→∏c

Γ4
4[

Rc∙. = RK(4)

85
86

∏→x4
x→∏a

64
4—

Ra: = R4

κ∏→xθ ГО
Kx→∏a L —

RK(a): =
= RK(O)

60
4L

Rb:=RO

87
88
89
90

2
+

Π→xO
x→ ∏b

^T

18

Fx<0
F

и


Продолжение
Номер
команды

Команда

Код

Комментарии

91
92

∏→xc
Kx→∏b

6[
LL

RK(b)-.≈Rc

93
94

БП
76

51
76

БП
______________ β______________

95
96

5
C∕Π

05
50

V

Результат счета

Останов

Таким образом, пятизнач­
ное^ число с требуемыми
свойствами
единственное.
Время
Я5Я6Я7Я8Я9
Это 13452.
Конечно, это число можно
9.12
пуск
было
бы достаточно быстро
9.18
3412
угадать. Но затем нужно
9.21
4312
10.02
13452
было бы выяснить, не сущест­
11.30
стоп
вует ли других чисел с тре­
буемым свойством. Следова­
тельно, единственность этого
пятизначного числа пришлось бы доказывать. А это
не всегда получается быстро и к тому же, чтобы при­
ступить к доказательству, нужно вначале приобрести
некоторую уверенность в том, что хочешь доказывать.
Изначально нужно было бы просто догадаться, что
других чисел нет. В то же время, имея достаточно
хорошие навыки в программировании, можно быстро
набросать программу и просчитать по ней. А это уже
определенный стиль мышления, определенный подход
к анализу и решению задач,и он, на наш взгляд, очень
необходим сейчас, а более того — в будущем. Кроме
того, добавим, что если вы обладаете персональной
ЭВМ, то все вопросы, связанные с программированием,
будут, конечно, решены быстрее и несравненно быстрее
осуществится счет.
Обратимся и мы еще раз к решенной задаче,
чтобы посмотреть, как будет выглядеть алгоритм,
предназначенный для программирования на Бейсике,
и соответствующая ему программа.
14. Алгоритм и соответствующая ему программа на
Бейсике.
Для хранения пяти подвергаемых проверке цифр
60


отведем массив R, зарезервировав соответствующую
область в памяти оператором DIMR (5).
Ал гоp иτм

Соответствие
фрагментам
предыдущего
алгоритма

DIM R (5)
D:=^
→ Δ если D ^ 3
____________ TQ у
иначе для 1 от 0 до 4

Фрагмент 1

нц

^(/): = D+1

кц
все
→
∣1 3___L
еслиН0Ж0)+ЯНУ^(2)
^ H
∖i ^*∖ ∖^/ i i' ∖1 // 2× ∖^/ = *10^(3)÷
v×χ∖ ∖^/ ∣
+ Λ(4)
то PRINT 10 000R (0) +
- +1000R(l) +100R (2) +
+ 10R (3) +R(4)
все
для / от 3 до 0 шаг — 1
нц если R(1) <R(I + 1)
--~~~~~ то β
все
кц
D: = D+1
________
GOTO
Vlk√ 1 v√ ΔLΛ
______ ^' Со Л
p (i
Z1 •• =
— ∕∖
ξ/ ∖у
для / от 4 до / +1 шаг — 1

■ 1

нц
если A<R(Γ)
---τ∏1 VГПxv
все
кц

----- >φ RW-.=RW
R(l}.=A
M: = 1
пока Z + Λ1 <5-Λl

нЦЛ: = ^(/ + М)
^(/ + M): = ^(5-M)
£(5-М): = Л
M:=M + 1
кц
____________
ь^
——.—— GΩTO
VJ‰∕ 1 v√ и
м*
______________ > γ END

Фрагмент 2

Фрагмент 3

Фрагмент 5

Фрагмент 6

Фрагмент 7

Фрагмент 8

Фрагмент 9
61


Подумайте, почему здесь отсутствует фрагмент,
соответствующий фрагменту 4.
Этому алгоритму соответствует следующая про­
грамма:
5 REM ГЛАВА2/ ПАРАГРАФ 4
10 REM ОСОБОЕ ЧИСЛО
20 DIM R<5>
30 D≈0
40 IF D>=3 THEN 270
50 FOR I≈Θ TO 4
60 R<I)=D+I
70 NEXT I
S0 r£T5.i0*R<®>+R<1)>*R<2X>1^
THEN 100
90
100PFORTIЖ < STEP^?*R C1 *+1$^ C 2 *+18*R C 3 * +R ^ 4 *

110
И5
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270

IF R<I><R<r+l> THEN 140
NEXT I
D=D+1
GO ТО 40
A=R(I)
FOR .J=4 ТО 1+1 STEP -1
IF A<R<J> THEN 180
NEXT .J
R(I)≈RGJ)
RGJ)≈A
M=1
IF I+M>=5-M THEN 80
A=R<I+M>
R<I+M>=R<5-M)
RG5-M)≈A
M=M+1
GO ТО 210
END

Как вы думаете, почему в программе отсутствует
строка, соответствующая в алгоритме последней строке
фрагмента 8 (GOTO μ)?
15. Близкие задачи.
Вот еще две задачи, близкие решенной в предыду­
щем параграфе.
1. Пять карточек ([2], задача 102). У меня пять
карточек, на которых изображены цифры 1, 3, 5, 7 и 9.
Как расположить их в ряд таким образом, чтобы
произведение числа, образованного первой парой карто­
чек, на число, образованное последней парой карточек,
минус число, стоящее на средней карточке, равнялось
числу, составленному из повторений одной и той же
цифры? Например, (см. рисунок), ЗГ, умноженное
на 79, минус 5 равно 2444; последнее число подошло
бы нам, если бы вместо 2 на первом месте стояло
тоже число 4.
3
1
5
7
9
62


Очевидно, должно быть два решения, поскольку обе
пары карточек — две первые и две последние — рас­
положены совершенно симметрично.
2. Две суммы ([2], задача 104). Можете ли вы
расположить цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 двумя груп­
пами по четыре цифры в каждой так, чтобы суммы
чисел, составленных из цифр каждой группы, были
равны между собой?
Очень просто получить ответ, заменив 9 на 6. На­
пример, каждая из сумм двух групп чисел 1, 2,
7, 8 и 3, 4, 5, 6 равна 18. Но такая замена не до­
пускается.
Чем похожи эти две задачи на решенную и чем от
нее отличаются?
Можно ли использовать готовые фрагменты состав­
ленного ранее алгоритма при составлении алгоритмов
решения этих задач?
Какое вычислительное средство можно выбратьдля
решения каждой из этих задач?
Если у вас имеется другой программируемый микро­
калькулятор (не MK-54), попробуйте составить алго­
ритмы для него.
Напишите соответствующие программы на Бейсике.
Если ваша персональная ЭВМ имеет трансляторы с
других языков программирования, попробуйте соста­
вить алгоритмы для них и написать на этих языках
программы. Наконец, составляя алгоритмы, позаботь­
тесь о том, чтобы получить минимальное время счета
по ним (это наиболее существенно, если вы програм­
мируете для микрокалькулятора).

5. Извлечение корня

Вот нехитрая задача, требующая, однако, некоторых
дополнительных исследований ([2], задача 119) .^
Однажды в разговоре с профессором Саймоном
Грейтхедом, человеком весьма эксцентричного склада
ума, я как-то упомянул об извлечении кубического
корня.
— Поразительно,— сказал профессор,— какое не­
вежество проявляют люди в столь простом вопросе!
Создается впечатление, что в извлечении корней со
времен, когда единственными корнями были корни,
извлекаемые с помощью лопат, вил и садового совка,
мир никуда не продвинулся. Например, никто, кроме
63


меня до сих пор не обнаружил, что для извлечения
кубического корня из какого-нибудь числа достаточно
лишь найти сумму его цифр.
МПЖРТ псякий
Извлечь кубическии корень из 1 может всякии.
хЛ й£ пример и подкрепляет высказанное мной
утвепждениеон слишком тривиален и мы его рассматпиватТ не будем. Предположим, что требуется из­
влечь кубический корень из 512. Находим сумму цифр,

раВЯУш>1сказалТпредположение, что здесь мы имеем дело
C "^≡^
профессор.— возьмем
наугад другое число, скажем4913. Сумма его цифр
пявна 17 а 17 в кубе равно 4913.
p я не’осмелился возражать ученому, но ПОПР°“У
читателей найти все остальные чис?а’У*от°^ ^ел
ческий корень совпадает с суммой цифр. Этих чисел
такмало что их буквально можно пересчитать

”° Bepom"o,nepBoe, что приходит на ум, так это такой
алгоритм:

fe:=0
------- > α k: = k + 1
⅛: = k∙k∙ k
5:=сумма цифр (⅛)
если s = k
то напечатать b, k
все
БП
----------- - α

(1)

Однако любой исполнитель этого алгоритма обречен
считать бесконечно. Тем не менее даже θy≡""
задачи сказано, что искомыечисла существуют в весьма
нейльшомколичестве. Значит, существует кекоторыи
поедел в наращивании чисел k, сверх которого вы
числения следует прекратить, так как суммавдфручщ
сел ⅛3 никогда уже не будет совпадать с k . Выявить
этот предел и уяснить причины, порождающие такую
Хацию.оказывается несложно, тем более что у нас
в пуках например, все тот же MK-54, который поможет
в РсчитанныеР секунды получить необходимые оценки.
Вся суть в том, что для получения этих оценокнадо
осмелиться покинуть область натуральных чисел и
64


расширить ее до множества чисел вещественных.
Тогда мы можем рассмотреть две вещественные
функции:
ш=

зг
ух

и

ς/ x
dW~

Гсумма цифр числа x, если x = [x]
(сумма цифр числа[х] + 1, еслих=#И,

где [x] — целая часть x.
Вторая догадка состоит в том, чтобы заметить на
оси Ох особые точки: 1, 9, 10, 99, 102, 999, 103, 9999, 104,
99999, 105, ... (почему?), в которых необходимо произ­
вести вычисления значений функций f(x) и S(x). Нас
интересует та область, в которой уравнение
^=S(x)

имеет натуральные решения. Нанося на координатную
плоскость точки с вычисленными координатами, полу­
чим схематично следующее.

Здесь звездочками нанесены отмеченные точки с ко­
ординатами (x, S(x)), а заштрихованная область — это
область, за пределами которой точек с координатами
(x, S(x)) (звездочек) быть не может. Пунктирной линией
нанесен график функции f(x). Таким образом ясно,
что звездочка может оказаться на пунктирной линии
только, если x≤105. Следовательно, если уравнение
V* = s(x)
3—2740

65


имеет натуральное решение x, то 1 <x< 105, а значит,
натуральное значение k = ^x обязано удовлетворять
двойному неравенству
1 ≤ k ≤ 46.
Поэтому для микрокалькулятора алгоритм (1) сле­
дует изменить, скажем, таким образом:
Λ0: = 46

£: = 0

—>- α k: = k + 1
b: = k-k>k
S: = cyMMa цифр (b)
если S = k
то Rx: = b
C∕Π
Rx-k
C∕Π
все
FL0________
--------------- α
------- >• γ Rχ∖ = 1«--------------------------------C∕Π
БП
----------- V
Для реализации на Бейсике получим:
для k от 1 до 46
нц
В: = k • k • k
S: = cyMMa цифр (В)
если
S=k
то PRINT В, К
все
кц

(2)

(3)

Правда, преобразовать в соответствующие про­
граммы алгоритмы (2) и (3) еще невозможно. Для
этого нужно описать их подробнее. Вот как будут
выглядеть эти алгоритмы, окончательно подготовленные
для программирования.
66


Ал гоp иτм

алг извлечение корНя (цел R4f b)
арг R4
рез R4, b
нач
L0: = 46
^4:=0
-------- > α S: = 0

Соответствие с (2)

Вели­ Ре­
чина гистр
~^4~^~~Γ^
b

b

L0

0

~~S~^

с

L0: = 46
k.≈Q

I
I

S

^

I
I

"
.

£< τ^ τft

s

Q^C⅛? ц Ц
° °i
I
I

.

l

ц и *

Q£Q£Q£

k: = k + 1

i

||

..
⅛O

I
I

----- >- Δ а: = e
Rx: = а— 10
Fx≥0
______________ τ^------------ 1
Rxt≈α∕∖Q <—∣

e:=[^x]
Rx: = e • 10
Rx: = а — Rx
S; ≡ S ^- Rχ
БП
-----------------Δ
—► а S: β S + о

Ях: = S - R4
Fx≈0________

"-У (I)

Распределение
регистров
памяти

Rx: = b <---------C∕Π
Rx: = R4
C∕Π
pτ
∩___________________________ l
i Lυ
- a

_ 1ι^
___________
-------- _ ______ _
r→- γ ΛΛ. -—
С/Г[
БП
------ V

e

d

b-.≈k∙k∙k
а

а

S: = сумма
цифр
(¢)

если S-k
то Rx:=b
~C∕Π
Rx'.≈k
C∕Π
все
FL0
__________ a__________

γ Rx-. = 1
C∕Π
БП
__________ ?__________

кон

3*

67


для k от 1 до 46
нц
S: = 0
B:=k-k-k
A:=B
пока A ≠0
нц
S: = S + остаток (Л, 10)

Л:=[А/10]
кц
если S = k
то PRINT В, К
все

кц
И наконец, приведем соответствующие программы
для МК-54 и на Бейсике.
Номер
команды

Команда

Код

Комментарии

00
01
02

4
6
x→Π0

04
06
40

L0: = 46

03
04

0
x→∏4

00
44

^4: = 0

05
06

0
x→ΠC

00
4[

S: = 0

07

K∏→x4

Γ4

‰: = #K(4)

08

∏→x4

64

Rx: = #4

09
10
11
12

Bf
Bf
×
×

0E
0E
12
12

Rx: ≈ #4 ×
× ^4 - £4

13

x→∏d

4Γ

e: = Rx

14

x→∏b

4L

b: = Rχ

15
16

∏→xd
x→∏a

6Γ
4—

а: — e

α

Δ

68


Продолжение
Номер
команды

σ

Команда

Код

Комментарии

17
18
19

1
0

01
00
11

^x: = а — 10

20
21

Fx≥0
41

59
41

Fx≥0
σ

22
23
24
25

∏→xa
1
0

6—
01
00
13

Rx- = ю

26
27
28
29

x→∏9
K∏→x9
∏→x9
x→∏d

49
Γ9
69
4Γ

e: = [Ях]

30
31
32

1
0
x

01
00
12

‰: = e • 10

33
34
35

∏→xa

6—
14
11

‰: = а — Rx

36
37
38

∏→xc
+
x→∏c

6[
10
4[

S: = S + Rx

39
40

БП
15

51
15

БП
Δ

41
42
43
44

∏→xc
∏→ ха
+
x→∏c

45
46

∏→x4

64
11

Rx: = $ - R4

47
48

Fx = 0
53

5E
53

Fx = 0
ω

49

∏→xb

6L

Rx: = b

50

C∕Π

50

чтение b

51

∏→x4

64

Rx: = R4

52

C∕Π

50

чтение R4

S: = S + a

69


Продолжение
Номер
команды

Команда

Код

Комментарии

ω

53
54

FL0
05

5Γ
05

FL0
α

У

55
56
57
58

1
c∕π
БП
55

01
50
51
55

1-й признак
останова
Останов

Результат счета
Время

в

12.03

пуск

12.03
12.06
12.11
12.11
12.16
12.17

1
512
4913
5832
17576
19683

12.29

Λ4 = S

1
8
17
18
26
27

сτоπ

5 REM ГЛАВА 2л ПАРАГРАФ 5
lΘ REM ИЗВЛЕЧЕНИЕ КОРНЯ
20 FOR K=1 ТО 46
30 S=0
40 B=K*K*K
50 A=B
60 IF A=0 THEN J00
70 S≈S+A-INT<Azl0>*10
80 A=.IHT<Azi0>
90 GO ТО 60
100 IF S<>K THEN 120
110 PRINT Вл'л'лК
120 NEXT К
130 END


1. Только ли игры
Точно так же как существует круг чтения, расчитанный на любителей решать различные головоломки и
просто трудные задачи, так в будущем, по-видимому,
возникнет литература (фрагменты этого чтения в том
или ином виде появляются в различных научно-попу­
лярных журналах), рассчитанная на любителей решать
трудные алгоритмические задачи (иначе
разгады­
вать трудные алгоритмы). Что привлекает в кроссворде
многочисленных любителей его? Вероятно,возможность
проверить свои познания как в общедоступных областях
знаний (литература, искусство, музыка, география,
история и τ. д.), так и в узкоспециальных (математика,
физика, химия, биология и τ. д.), а также и свои
способности восстанавливать в памяти достаточно
большое количество разнородных фактов в кратчайшее
время. А вспомните, с каким огромным удовольствием
наблюдаем мы за поединком телезрителей и клуба
знатоков. Он возбуждает у нас страсти сродни спор­
тивным.
^
, _
Нам кажется, что как только наше общество в более
или менее достаточной степени насытится персональной
вычислительной техникой, а значит, станет уже доста­
точно программирующим, возникнет потребность в до­
ступных пониманию, простых по формулировке задачах
алгоритмического происхождения, содержащих неко­
торые тонкости на стадиях поиска алгоритма для их
решения и (или) интересных в том смысле, что
процесс поиска их решения способен возбудить у
участников такого поиска дух соревновательности. Оче­
видно, накопление таких задач — творчество коллек­
тивное, массовое и эти массы сидят сегодня, в основном,
за школьными партами и нуждаются в том, чтобы им
прививали вкус к решению задач на программирование.
71


Где искать такие задачи? Частично мы попытались
ответить на этот вопрос в главах 1 и 2. Однако не
следует упускать еще одной хорошей возможности^
состоящей в отыскании игровых мотивов в обычных
учебных задачах, в создании разумного баланса между
игрой и делом.

2. О задачах школьного курса информатики, или
Когда сделаны уроки

Рассмотрим несколько задач из [7], помеченных
звездочкой — значит отнесенных к задачам повышен­
ной трудности (далее в скобках дается порядковый
номер задач в [7]).
J (29*). Дана целочисленная таблица Л[1:1000].
Найдите наименьшее число k элементов, которые нужно
выбросить из последовательности А [1], А [2], ..., А [1000],
чтобы осталась возрастающая последовательность.
Если вы ее уже решили, то ответьте на вопрос. Удов­
летворяет ли вас полученный алгоритм? Точнее, удов­
летворяет ли вас тот результат, который дает этот
алгоритм? Сможете ли вы составить алгоритм, дающий
больше информации: например, какая же при этом
(хотя бы одна) наиболее длинная возрастающая после­
довательность элементов таблицы останется и на каких
местах в таблице стоят эти элементы? Соответственно,
конечно, вы узнаете, какие элементы таблицы нужно
выбросить.
Приведем алгоритм решения этой задачи.
алг задача 29* (цел таб Λ[1:1000], цел k)
арг А
рез k
нач цел i, j, цел таб L[1:1000]
для i от 1 до 1000
нц
L[/]: = 999
кц
для i от 1 до 1000
нц
для / от i + 1 до 1000
нц
если A [i] < А [/]
72


то если L [j] > L [/] — 1
то L[j]: = L[z]- 1
все
все
кц
кц
&: = L[1]
для i от 2 до 1000
нц
если k > L [/]
то k: = L [z]
все
кц

кон
Этот алгоритм описан в [9] с той лишь разницей, что
вместо L[i] там пишут «количество лишних [z]>> (что
упрощает разгадку алгоритма). Но писать L [z] удобнее,
если мы хотим затем перевести этот алгоритм на Бейсик.
Если вы хорошо поняли приведенный алгоритм, то
изменить его так, чтобы получить ответ на поставленные
нами вопросы совсем несложно. Напишите соответст­
вующую программу на Бейсике.
2 (39*). Некоторые натуральные числа могут быть
представлены в виде суммы кубов целых неотрица­
тельных чисел: например 9 = 23 + 13, 27 = 33 + 0. Со­
ставьте алгоритм, отыскивающий наименьшее нату­
ральное число, имеющее два разных таких представ­
ления. (Представления 9 = 23 + 13 = 13 + 23 считаются
одинаковыми.)
Алгоритм решения этой задачи вы также найдете в
[9]. Мы же не ставим себе целью обсуждать ее подобно
предыдущей задаче. Обратим внимание на другое: эта
задача из теории чисел, где можно найти массу подоб­
ных (более или менее сложных) задач. Формулировка
каждой из них проста и вызывает интерес. В качестве
иллюстрации приведем несколько задач, описанных
выдающимся польским математиком В. Серпинским
(далее в скобках дается порядковый номер задачи в [8] ).
1 (229). Найдите наименьшее натуральное число,
большее 2, являющееся одновременно суммой двух
квадратов натуральных чисел и суммой двух кубов
натуральных чисел.
73


2 (234). Найдите наименьшее натуральное число
n > 1,для которого сумма квадратов последовательных
натуральных чисел от 1 до n была бы квадратом
натурального числа.
3 (109). Найдите наименьшее натуральное число n,
для которого n4 + (n + 1)4 есть составное число.
4(103). Найдите все числа вида 2n-l, где n —
натуральное число, не большие миллиона и являющиеся
произведениями двух простых чисел.
5 (101). Найдите пять наименьших натуральных чи­
сел n, для которых каждое из чисел n, n + l, «4-2
является произведением двух различных простых чисел.
6 (99). Найдите пять наименьших натуральных чи­
сел n, для которых число n2 + 1 является произведением
трех различных простых чисел, и найдите такое нату­
ральное число n, для которого число n2 4- 1 является
произведением трех различных нечетных простых чисел.
7 (98). Найдите пять наименьших натуральных чи­
сел n, для которых число n2 — 1 является произведением
трех различных простых чисел.
8 (95). Найдите пять простых чисел, являющихся
суммами двух биквадратов (четвертых степеней) нату­
ральных чисел.
9 (40). Для каждого натурального числа S ≤ 25,
а также для числа S = 100 найдите наименьшее нату­
ральное число ns, имеющее сумму цифр, равную S,
и делящееся на S.
10 (34). Найдите наименьшее натуральное число n,
такое, что n не делится на 2n-2, но n делится на
3π-3.
11 (33). Найдите наименьшее натуральное число n,
такое, что n делится на 2n — 2, но n не делится на
3n-3.
12 (32). Найдите два наименьших составных числа
n, таких, что n делится на 2n — 2 и n делится на
3n-3.
Какое вычислительное средство пригодно для реше­
ния каждой задачи? Как выглядят алгоритм, состав­
ленный для этого средства, и соответствующая ему
программа?
Решения некоторых задач мы прокомментируем.
Задача 1 (229) может быть решена на микрокальку­
ляторе.
Вместо подробных указаний по составлению алго­
ритма и его сборке мы дадим краткие комментарии.
74


Комментарии

Ал гор итм

алг задача 1 [229] (цел #2, R3t R4, R5, R6)
арг R6
рез R2, R3t R4, R5, R3
нач
t
R6: = 2

п: =2_________

©

0£

i<

1
1

8

0.

/: = 0
/: = 0

О О

.

.ll

⅛ 4г uS
Q≤ Q^ С£

n: = n + 1

β

а: = ∕3 — n

если ∕^5≥ n то a
i i = i 4“ 1

x: = i3 4- ∕3 — n

если

i3 4- ∕3 < n
то γ

если i3 4- j3 ≠ n
то β

R2.-l^4 <----------------------------------

R2:=j

R3.-iW

R3: = i

I

----- - φ Rχ- ≡= RK(4)
Rx: = R4
a. = R4∙R4-R5
Fx < 0
_______________________
- a

→- гр Rx: = RK(5)

v
<----------

Fx≥0______________________
--------- ф
Fιс = 0 <
......... .........
-------- ( P
D∩∙ — 7 ^----------------------------------—

l----- >- ω Rx: = RK(ty
БП
1----------- ω

^ __________ ^ _____________________ _______

Rx: = R5
Rx: = R5 • R5 + a

_____________________

I

о о

^r ⅛

0ζ <*

I

__________ ?-

Fx≥0____________________
________ У
F X____
—nv ____________________________
* .

cQ.

→- γ Rx: = RK(5) <---------Rx: ≈R5
Rx:=R5-R5-R5 + a

/: = /+1
8______

—^β Rχ-,=RK(4)
Rx: = Я4
а: = R4 • R4 • R4 - R6
Fx<0___________________________
^ ..............
α
¾

i-∙≈β
Z: = 0
Γ≈∕ + i

а: = ∕2 — n

если jz^n то а
i:=i+ 1

х:=/24-/2 — л
если i2 + j2C∏
то гр
если i2 + j2 ≠ n
то φ

Чтение результата

n, j, i, R3, R2.
Здесь: j2^-i2 = ni
R3i + R23≈n.
75


Программа для МК-54
Номер
коман­
ды

Команда

Код

Комментарии

00
01

2
x→∏6

02
46

α 02 K∏→x6

76

Команда

Код

Комментарии

tf6:=2

31
32

∏→x5
x→∏3

65
43

R3.≈R5

Γ6

‰ = ^^(6)

33
34

0
x→∏4

00
44

R4: = 0

35

x→∏5

45

R5ι≈0

Γ4

Rx:=RK(4)

03
04

0
x→∏4

00
44

^4:=0

05

x→∏5

45

fl5:=0

Γ4

Rxι≈RK(4)

37

∏→x4

64

Rxι≈R4

Rx: = #4

38
39
40
41
42

Bf
×
∏→x6

a: = R4X
XR4-R6

x→∏a

0E
12
66
11
4—

43
44

Fx<0
02

5[
02

Fx<0
α

β 06 K∏→x4

V

Номер
коман­
ды

07

∏→x4

64

08
09
10
11
12
13
14

Bf
Bt
X
X
∏→x6

a: = fl4X
ХЯМ4-Я6

x→∏a

0E
0E
12
12
66
11
4—

15
16

Fx<≤0
02

5[
02

Fx ≤ 0
α

17 K∏→x5

Γ5

Rx: ≈RR(ty

Rx:=R3

18

∏→x5

65

19
20
21
22
23
24

Bf
Bf
×
×
∏→xa
+

0E
0E
12
12
6—
10

Rx:=R5X
XR5-R5 +
÷a

25
26

Fx≥0
17

59
17

Fx≥0
V

27
28

Fx=0
06

5E
06

Fx = 0
β

29
30

∏→∙x4
x→∏2

64
42

fl2:=fl4

φ 36 K∏→x4

Ψ 45 K∏→x5

Γ5 Rx: = ^^(5)

46

∏→x5

65

47
48
49
50

Bf
×
∏→xa
+

0E
12

51
52

Fx≥0
45

59
45

Fx≥0
ψ

53
54

Fx = 0
36

5E
36

Fx = 0
φ

55
56

7
x→Π0

07
40

RQ:=7

ГО

Rx:=RK(G)

ω 57 KΠ→x0

Rx:=R5
Rx:=R5X
XR⅛ + a

10

58

C∕Π

50

C∕Π

59
60

БП
57

51
57

БП
ω


Результат счета
Время

Результат

.______j

20.36
21.06

Пуск
n = 65
/=8
R3≈4
i≈1
R2 = 1

Посмотрим, как будет выглядеть алгоритм решения
задачи 1 (229), предназначенный для программирова­
ния на Бейсике. Для этого достаточно внимательно
изучить комментарии к алгоритму для MK-54. Получим
следующее:
^: = 2

77


все
если I∙I+J∙J^N
------------------- то φ
все
PRINT N, J, I, R3, R2
1

Этому алгоритму соответствует следующая про­
грамма:
18 REM ГЛАВА Зл ПАРАГРАФ 2/ ЗАДАЧА 1
28 N=2
3Θ N=N+1
40 J=θ
50 I≈θ
60 J=J+1
70 IF J*J*J>=N THEN 30
S0 I=I+1
90 IF I*I*I+J≡J≡J<N THEN 80
100 IF I≡I*I+J*.J*J<>N THEN 60
110 R2=J
120 R3=I
130 J=0
140 1=0
150 .J=J+1
160 IF J*:J>=N THEN 30
170 I≈I+1
180 IF I≡I+J≡J<N THEN 178
198 IF I*I+.J*J<>N THEN 158
288 PRINT "N≈"N∕4=4^J='J^R2='R2^R3≈,R3
218 END

Запись алгоритма решения задачи 1 (229) на алго­
ритмическом языке будет выглядеть несколько иначе:

алг задача 1 (229) (цел N, I, Ji R2, R3)
арг N
рез N. I. J, R2f R3
нач цел P
N:=2
P:=0
пока P≠2
нц
^:=^+l
/: = 1
/: = 1
P:=0
пока J*J*J<N и P = 0
нц
пока /*/*7 + ^*J*Z<^
78


нц

/: = /+1
кц
если I*I*l^J*J*J = N
то P: = 1
иначе J: = / +1
все

кц
если P = 1
то R2: = /
- R3: = /
/: = 1
/: = 1
пока J♦/<^ n_P= 1
нц
пока I*I + J*J<N
нц
/:=/+1
КЦ
если I*I+J*J≈N
то P: = 2
иначе J = J + 1
все
кц
все

кц
кон

Полученный алгоритм является структурированным.
На Бейсике ему соответствует такая программа:
10 REM ГЛАВА Зл ПАРАГРАФ 2л ЗАДАЧА 1
20 N=2
3Θ P=θ
40 IF P=2 THEN 343
50 N=N+1
60 W
70 J≡1
80 P≡≡0
90 IF J*J*J>=N THEN 190
100 IF P<>0 THEN 190
110 IF I*I≡H+J*J*J>=N THEN 140
120 I=I + 1
130 GO ТО 110

79


14Θ
15Θ
160
170
18Θ
190
200
210
220
230
240
250
260
270
230
290
300
310
320
330
340
350

IF I*I*I+J≡J≡J<>N THEN 170
P=1
GO T0 90
j=J+l
G0 T0 90
IF F,<>1 THEN 40
R2=∙J
R3≈I
I≈1
J=1
IF J*J>≈N THEN 40
IF P<>1 THEN 40
IF I$I+J*J>=N THEN 290
I=I+1
G0 T0 260
IF I^I+J^,J<>N THEN 32©
P=2
G0 T0 240
J≈J+1
G0 T0 240
PRINT ,N≈'N∕4=^b,J='J∕,R2=,R2∕zR3="R3
END

Как видим, эта программа значительно, более гро­
моздка по сравнению с предыдущей. Увы, Бейсик не
является языком структурного программирования,
а рассмотрение других языков в наши планы не
входит.
Совсем несложно подправить эти алгоритмы исоответствующие им программы (для МК-54 и на Бейсике)
так, чтобы получить любое требуемое количество чисел
с отмеченным в условии задачи свойством. Как это
сделать? Какое, следующее после 65, число получится?
Примечание. Слово «любое» не совсем точно. Точнее
(и мы об этом напоминали ранее) словосочетание
«любое допустимое», так как есть предел для представ­
ления целых чисел в ЭВМ. Для того чтобы заглянуть
за границы этого предела, требуются специальные
методы. Мы касались этой темы в главе 1.
Обратимся еще к одной задаче, например 5(101).
Алгоритм построим так, чтобы натуральное число, с ко­
торого калькулятор начнет поиск, вводилось с клавиа­
туры. Тогда мы можем указать любое достаточно
большое доступное нам (разумеется, без особых уси­
лий) число, относительно которого мы уверены, что
числа, не превосходящие его, отмеченным в условии
задачи свойством не обладают. Более того, если мы
вычислим несколько чисел, удовлетворяющих требуемому свойству, то в следующий раз мы можем продолжить
поиск таких чисел, начав с числа ^+l, где N, N+l,
80


N^2 — последняя, вычисленная нами, тройка. (Изучив
построенный ниже алгоритм, ответьте на вопрос: почему
необходимо будет начать с числа 7V+1?)
Очевидно, при^построении такого алгоритма придет­
ся постоянно обращаться к одной и той же процедуре
выяснения, является ли заданное число простым или же
оно имеет нетривиальные делители. Эту процедуру
удобно оформить в качестве подпрограммы. У нас она
будет работать так:
1) если отправленное в подпрограмму число оказа­
лось простым, в регистре x формируется число 1;
2) в противном случае — в регистре x формируется
число 0.
Подпрограмма размещается в алгоритме с метки κ.
Аналогично предыдущей задаче мы не описываем про­
цесс конструирования алгоритма, а ограничиваемся
комментариями к нему. (Более того, вероятно, вообще
заслуживает внимания такая постановка вопроса, когда
по данному алгоритму требуется определить задачу,
которую он решает. В случае коротких и поучительных
алгоритмов поиск ответа на этот вопрос мог бы вызвать
определенный интерес.)
Ллrоp иτм

алг задачιa 5(10!) (цел N, Я8, Я9, Ray Rb,
Rc, Rd)
арг N
рез R8, Я9, Ra, Rb, Rc, Rd

Распределение
регистров
памяти

вели­ ре­
чина гистр
N ~3

Коммен­
тарии

*

R8

8

Rd
Я4

d
~4

**

/

~6

***

S

5

IV*

Я1

1

VI*

I
нач цел Я0, R∖, R2, Я4, S, 1 вещ Rx
► Л Я4: — 7

/:=0
-----^β S:=0

W:=W+1
R∖.≈N

∏∏
------------- κ
Fx=0__________________________
*----------- β
D 11 .. —
-- A
pa
^
А
U
^_______________
_________ ∣

4—2740

- > γ ∏∏

V*

VII*

VIII* тг
Я0

0
IX*

81


Продолжение

Ал гоp иτм

Распределение
регистров
памяти

Fx ≠ 0
«-------- -------- Г“

S∙. = S÷1
*------если S ≈ 1
то R2: = Rl
^1: = ^1
БП
------------------ γ
все
если R2: ≈R∖
<--------------- то β
все
RR^).≈R2
^(4): = ^
/: = /+1
если /= 1
4--------------- TO β
все
если 1 = 2
то если Rb— R$ = 1
4-------------------------- ТО β
иначе БП
__________________..--...-.^^-.. ос
все
все
если Rd — Rb ≈ 1
то C∕Π
все
→- α Лl: = N-l
E»П
--------- /к
.κ Я0:=Я1√2÷1
→- ω RQ: = [^0—1]
если jR0≥2
τ<э если [Rl∕RG]≠Rl∕RG
-------------------------то ω
иначе Rx: = 0
В/0
все
все
Rx: = 1
В/0

КОН

82

Коммен­
тарии

X*
1;п
R2

2

XI*

xπ*

XIII*

XIV*

XV*
IV

XVI*

XVII*

[ ]

7

Rx

x

XVIII*

V


*) В целях экономии программной памяти число N
будет заноситься нами в регистр 3 вручную: ^x→∏3.
Затем пускаем микрокалькулятор на счет. Переменным
R8, R9, Ra, Rb, Rc, Rd отводятся регистры 8, 9, a, b, с, d,
соответственно.
**) Если каждое из чисел N, ^ +1 и ^ + 2 предста­
вимо в виде произведения точно двух различных
простых чисел, то регистры 8—d заполняются так:
1) в регистры 8 и 9 — один простой делитель числа N
и число N (обозначаемое R9), соответственно;
2) в регистры а и b — один простой делитель числа
N +1 и число N +1 (обозначаемое Rb), соответственно;
3) в регистры с и d — один простой делитель числа
N+2 и числоЛ^ + 2 (обозначаемое ЯсО.соответственно.
Это заполнение организуется косвенно через ре­
гистр 4 (см. ниже операторы RR(4):=R2 и RK(4): =
= N). Поэтому первоначально в регистр 4 заносится
число 7 (так как при косвенном обращении содержи­
мое регистра 4 увеличивается на 1).
***) 1 — параметр, при помощи которого организу­
ется контроль выполнения условий задачи Rb — R9 = 1
и Rd — Rb = 1 для чисел R9, Rb и Rd. Начальное зна­
чение / равно 0.
IV») S — параметр, отвечающий за выделение точно
двух различных простых множителей, дающих в произ­
ведении испытуемое число. Начальное значение S
равно 0.
V*) Чтобы получить следующее испытуемое число,
предыдущее следует увеличить на 1.
VI*) Испытывается копия числа, передаваемая
в регистр 1.
VII*) Переход к подпрограмме для испытания
числа #1.
VIII*) Если число N простое, τ. e. оно не представи­
мо в виде произведения двух нетривиальных делителей,
то подпрограмма формирует в регистре x число 1. По
этому признаку нужно получить новое число для испы­
тания — переход на метку β. В противном случае (под­
программа формирует в регистре x число 0) нужно
испытать первый полученный в подпрограмме дели­
тель RQ числа N. Если он будет простым, необходимо
испытывать второй делитель. Так как испытуемое число
подается в подпрограмму в регистре 1, выполняется
оператор#1:=7?0.
IX*) Вновь отправляемся к подпрограмме.
83


χ*) Теперь, наоборот, если делитель оказался со­
ставным (в регистре x число 0) надо возвратиться на
метку β и увеличить на 1 число N. Если же делитель
простой, увеличиваем параметр S на 1.
XI*) S = 1 — признак того, что первый делитель —
простое число и нужно его сохранить; затем вычислить
второй делитель и перейти к его испытанию (B∏γ).
5 = 2 — признак того, что второй делитель тоже про­
стой и необходимо перейти к сравнению двух простых
делителей числа N, дающих в произведении N.
X∏*) Если оказалось, что делители R2 и R∖ числа N
совпадают, необходимо перейти к испытанию числа, не­
посредственно следующего за N,— возврат на метку β.
В противном случае продвигаемся вниз по алгоритму.
XI∏⅛) Найденное число N и один соответствующий
ему простой делитель отправляются на хранение, а па­
раметр Z увеличивается на 1.
XIV*) Если / = 1, необходимо разыскать второе чис­
ло, представимое в виде произведения двух различных
простых множителей,— переход на метку β. В против­
ном случае продвигаемся вниз по алгоритму.
XV*) Если Z = 2, второе число найдено и нужно
выяснить, следует ли оно непосредственно за первым
(#6-^9=1). Если да — организуем поиск третьего
числа — переход на метку β. Если нет — переходим
на метку α.
Если Z≠2, значит Z = 3 и найдено третье число,
а разность между вторым и первым была равна 1.
Тогда продвигаемся вниз по алгоритму.
XVI*) Если мы дошли до этой серии команд, нам
остается вычислить разность между третьим (Rd) и вто­
рым (Rb) найденными числами. Если она равна 1, то все
условия задачи выполнены и необходимо остановиться
для чтения очередного результата, поочередно вызы­
вая на индикатор содержимое регистров 8-d. После
прочтения результата пускаем микрокалькулятор на
счет нажатием клавиши C∕Π.
Если Rd — Rb ψ 1, останов не произойдет (команда
C∕Π пропускается), и мы переходим к оператору, сле­
дующему за этой неполной развилкой (он помечен мет­
кой α).
XVII*) К оператору, помеченному меткой α, мы при­
ходим в одном из трех случаев: 1) из блока XV*; 2) из
блока XVI*; 3) и минуя блокХУЬ (когда Rd—Rb ≠ 1).
Но всякий раз, когда мы оказываемся здесь, ситуация
84


одна и та же: необходимо организовывать поиск
тройки чисел ^, Wψl, N + 2, каждое из которых есть
произведение двух различных простых чисел, заново.
Но при этом вполне может быть, что последнее испы­
тывавшееся (и уже раскладывавшееся в нужное произ­
ведение) число как раз и есть начало искомой тройки.
Если мы его пропустим при новом заходе, то пропустим
и искомую тройку. Чтобы этого не случилось, возвра­
щаемся на одно число назад (N: — N— 1) и только тогда
переходим к организации нового поиска (БПА).
XVIII*) Это упоминавшаяся нами еще до описания
алгоритма подпрограмма (вспомогательный алгоритм).
Очевидно, числа, большие чем [#l/2], не могут быть
делителями числа ^1, поэтому проверку претендентов
в делители надо начинать с числа [#l/2].
А теперь проследим составленный нами алгоритм
крупными блоками (см. второй столбец в коммента­
риях) :
I. Подготовка входных данных.
II. Поиск числа, имеющего нетривиальныеделители.
III. Отбор таких чисел, у которых имеется точно
два разных простых делителя.
IV. Выделение тройки непосредственно следующих
друг за другом натуральных чисел, каждое из которых
имеет два разных простых делителя.
V. Подпрограмма, определяющая простое (в ре­
гистре x формируется число 1) или составное (в ре­
гистре x формируется число 0) то число, которое нахо­
дится в регистре 1. Кроме того, если это число составное,
то в регистре 0 к моменту возвращения из подпро­
граммы находится первый вычисленный (и наиболь­
ший) делитель этого числа.

Программа для МК-54
Номер
коман­
ды

Команда

Код

Комментарии

Δ 00
01

7
x→∏4

07
44

R4: = 7

02
03

0
x→∏6

00
46

Z:=0

β 04
05

0
x→∏5

00
45

S:=0

Номер
коман­
ды

Команда

Код

Комментарии

06
07
08
09

∏→x3
1
+
x→∏3

63
01
10
43

W:=W+1

10

x→∏l

41

^1: = ^

11
12

∏∏
73

53
73

∏∏
κ

85


Продолжение

Номер
коман­
ды

Команда

Код

Комментарии

13
14

Fx = 0
04

5E
04

Fx = 0
β

15
16

Π→x0
x→∏l

60
41

^l: = ^0

17
18

∏∏
73

53
73

∏∏
κ

19
20

Fx ≠ 0
04

57
04

Fx ≠ 0
β

21

K∏→x5

Γ5

S:=S+1

22
23
24
25
26

∏→x5
1

65
01
11
5E
34

если S = 1
то

V

50
(
51
I
52

∏→xd
Π→xB

Fx = 0
70

6Γ
6L
11
01
11
5E
70

C∕Π

50

c∕π
Чтение ре­
зультата в
регистрах
R⅛-Rd

Γ3

^: = ^-l

БП
17

51
17

БП
У

34
35
36
37
38

∏→x2
∏→xl

62
61
11
57
04

если #2 =
p-=Λi
I
τ° β
все

39 ∏→x2
40 Kx→∏4

62
L4

RK(4): = R2

41 ∏→x3
42 Kx→∏4

63
L4

flK(4): = ^

43 K∏→x6

Γ6

/: = /+1

66
01
11
57
04

если / =1
|
го β
все

Π→xB
∏→x9
1

1

^a 70 K∏→x3

ω

4

БП
α

32
33

κ

oo

51
70

69

∏→x6
44
1
45
46
47 Fx ≠ 0
04
48i

Fx = 0
62

если / = 2
то |

БП
70

R{. = N∕Rl

Fx ≠ 0
04

01
11
5E
62

60
61

x→∏l

>

1

Комментарии

Fx ≠ 0
04

Я2:=Я1

о

Код

если Rb-R⅛≈
=1
то β

53
54
I
55
56
57
58
59

I

ОО

Команда

6L
69
11
01
11
57
04

i

63
61
42
13
41

∏→x3
∏→xl
x→∏2

86

z19
r

62
63
64
65
66
67
68

Fx = 0
34

27
28
29
30
31

о

Номер
коман­
ды

если Rd —
-Rb =
=1
то

Y

oo

71
72

БП
00

51
00

БП
Δ

73
74
75
76
77

2

02
13
01
10
40

W: =
= ^1∕2÷1

i

+
x→Π0

78 K∏→x0

79
80
81
82
83i

Γ0 ^0:=[^0-l]

'~60^
Π→x0
если βO≥2
02
2
то
11
59
Fx ≥ 0
96 oo
96
oo
,'


Продолжение
Номер
коман­
ды

Команда

84 ∏→xl
85 Π→x0
86
87 x→∏d
88 x→∏7
89 K∏→x7
90 ∏→x7
91 ∏→-xd
92
93 Fx = 0
78
94

Код

Номер
коман­
ды

Комментарии

61
60
13 если
4Γ Wθl≠
47
≠R∖∕R0
Γ7
то ω
67
6Γ
11
5E
78

оо
оо

Команда

Код

Комментарии

95

В/0

52

иначе
‰=0
В/0

96

1

01

Rx: = 1

97

В/0

52

В/0

Результат счета
Время

Результат

19.51

Пуск при N = 30
∏→xd
∏→xc

34
17
2

∏→xb
∏→xa

33
11
3

19.57

35
7
5

22.00

87
29
3

86
43
2

85
17
5

22.35

95
19
5

94
47
2

93
31
3

∏→x9
∏→x8

Теперь составим программу решения этой же задачи
на Бейсике. Вначале алгоритм. Очевидно, в данном слу­
чае удобнее всего придерживаться алгоритма, состав­
ленного для МК-54 (сохраняя даже обозначения). Вот
что получим:
DIM N (3)
DIM R1 (3)
DIM R2 (3)
K: = 0
PRINT' Введите начальное натуральное чис­
ло N'
INPUT N
PRINT' Сколько чисел с отмеченным свойством'
PRINT' Вы хотите получить?'
INPUT M
87


>A /:=0
L:=0
—>β S: = 0
^:=^+l
R1: = ^
GOSUB κ
если x ≠ 0
------ то β
все
^1:=7?0

c=±y GOSUB κ
если x = 0
------- то β
все
S: = S + 1
если S = 1
то R2:=R1
R∖∙.≈N∕Rl
GOTO γ
все
если R2 = R1
то β
все
I: = I
N(1): = N

Rl^: = Rl
R2(ty = R2
L:=L + i
если L = 1
<-------------- то β
все
если L = 2
то если N(2)— ^(l) = 1
----------------- τ0 β
----------------- иначе GOTO α
все
все
если ^(3) — ^(2) = 1
то PRINTN(l),N(2),N(3)
- PRINT R1 (1), R1 (2),
Rl(3)
88


PRINT R2(1), R2(2),
R2(3)
κ. = κ+∖
если К = M
-------------- ≈--------------------------------- то END
все
все
---- >α N:=N-l
------ GOTO Δ
----------->κ R0:=Rl/2+l
---- >ω R0:=[R0-l]
если R0 ≥ 2
то если [Rl∕R0]≠Rl∕R0
------------------- -------- то ω
иначе x: =0
--------------------------------------------- GOTO φ
все
все
x: ■ 1
- >φ RETURN
-------------- >END

10 REM ГЛАВА 3/ ПАРАГРАФ 2л ЗАДАЧА 3
20 DIM N(3)
25 DIM Rl<3)
30 DIM R2<3)
40 K≈θ
50 PRINT 'ВВЕДИТЕ НАЧАЛЬНОЕ НАТУРАЛЬНОЕ ЧИСЛО'
60 INPUT N
70 PRINT 'СКОЛЬКО ЧИСЕЛ С ОТМЕЧЕННЫМ СВОЙСТВОМ'
80 PRINT 'ВЫ ХОТИТЕ ПОЛУЧИТЬ?'
90 INPUT M
100 I≈Θ
110 L≈0
120 S=0
130 N=N+1
140 Rl=H
150 GOSUB 430
160 IF X<>0 THEN 120
170 Rl=RΘ
180 GOSUB 430
190 IF X=θ THEN 120
200 ⅛=y+l
210 IF S<>1 THEN 258
220 R2=R1
230 Rl=NzRl
240 GO ТО 180
250 IF R2=R1 THEN 128

89


260 I=I + 1
270 N<I)=N
280 Ri<I>=Rl
290 R2(I)=R2
300 L=L+1
310 IF L=1 THEN 120
320 IF L<>2 THEN 350
330 IF NC2)-N<1)=1 THEN 120
340 eo TO 410
350 IF N<3)-N<2)<>1 THEN 410
360 PRINT N<l>,N<2>,N<3>
370 PRINT Rl<lbRl<2).∙Rl<3>
380 PRINT R2<l)>R2<2),R2<3)
390 K=K+1
400 IF K=M THEN 510
410 N≈N-1
420 GO TO 100
430 R0=R1×2+1
440 R0=INT<R0-1>
450 IF R0<2 THEN 490
460 IF INT<R1×R0M>R1×R0 THEN 440
470 X=0
480 60 TO 500
490 X=1
500 RETURN
510 END

Примечание. Быстродействие микро-ЭВМ просто
несравнимо с быстродействием MK-54. Буквально счи­
танные минуты понадобились ДВК 2M, чтобы получить
следующую (при М-8) таблицу:
33 34 35
3 2 5
11 17 7
85 86 87
5 2 3
17 43 29

95
5
19

201 202 203
3
2
7
67 101
29

217 218 219
7
2
3
31 109 76

141 142 143
3
2
11
47 71
13

213 214 215
3
2
5
71 107 43

301 302 303
7
2
3
43 151 101

93
3
31

94
2
47

И наконец, если поставить себе цель получить по
этой программе максимально возможное количество
троек, непосредственно следующих друг за другом нату­
ральных чисел, представимых в виде произведения двух
различных простых множителей, то в программу не­
обходимо добавить строку:

135 IF N = 999999 THEN 510

Почему?
90


3. Можно ли играть в школьную теорему
В школьных учебниках по математике, физике,
химии много задач, которые можно с помощью микроЭВМ (например, ДВК-2М) обработать. И тот, кого
эта работа по-настоящему увлечет, извлечет из нее
немалую пользу для себя и принесет пользу другим.
Конечно, диапазон возможностей существенно расши­
рится, если ваша ЭВМ обладает графикой.
Зависимость между корнями и коэффициентами ал­
гебраического уравнения

xn + αιxn~1 + α2x"-2 +... + an-ix + an = 0,
где aι — произвольные комплексные числа, n — натуральное число, устанавливается формулами Виета.
(Франсуа Виет (1540—1603) —французский матема­
тик, «отец алгебры».) В школьной математике формулы
Виета изучаются для приведенного квадратного урав­
нения
x2 + px + ⅛ = 0,
(1)

В этом частном случае они имеют вид:

P=-(Xi+×2∖
⅛ = X1X2,

∕2∖
1 '

где x∣ и X2 — корни уравнения (1). С помощью фор­
мул (2) можно решать две взаимно обратные задачи:
1) по корням уравнения (1) определить его коэффи­
циенты и 2) по коэффициентам уравнения (1) опре­
делить его корни. Соответственно этому в школьном
учебнике [10] формулируются прямая и обратная теоре­
мы Виета.
По сравнению с 1) решение задачи 2) более трудо­
емко. Но если корни уравнения (1) являются целыми
числами и по абсолютной величине не превосходят
некоторое небольшое число (например, 10), то вычис­
лить их, используя равенство (2), можно и устно.
Примеры таких квадратных уравнений подобрать
легко, используя прямую теорему Виета. А тот, кто
будет их решать, должен использовать обратную
теорему.
Зададимся целью написать (с учетом сказанного)
для ДВК-2М (на Бейсике) программу-тренажер, позво­
ляющую эффективно отрабатывать навыки по исполь­
зованию формул Виета. Пользователь этой программы
91


будет иметь возможность довести свои умения в
использовании формул (2) до автоматизма, а вот
составитель получит несравненно больше — он глубже
постигнет алгоритмический характер программируемых
им задач и, естественно, будет совершенствоваться
в составлении сложных алгоритмов и программиро­
вании.
Как представляется нам такая программа в самых
общих чертах, видно из следующего алгоритма:

нач
1 сформировать уравнение
2 сформулировать задачу
3
произвести опрос
кон
Здесь и далее вдоль записи алгоритма мы будем ну­
меровать его команды, чтобы, с одной стороны, иметь
возможность учесть все одинаковые команды (им будет
присваиваться один и тот же номер), а с другой —
иметь точное представление о вложенности алгоритмов
в процессе их постепенного уточнения и детали­
зации.
Выясним, какие действия предполагает команда 1.
Точнее, команда 1 может восприниматься как заголовок
некоторого алгоритма, команды которого уточняют ко­
манду 1. Такая детализация вглубь будет продолжаться
до тех пор, пока мы не получим серию алгоритмов,
команды которых представимы в виде операторов для
ЭВМ (в нашем случае — операторов языка Бейсик).
Такие команды мы уже не будем нумеровать. В осталь­
ных случаях нумерация будет производиться по прин­
ципу вложенности, например: 3.1—первая команда
алгоритма, уточняющего команду 3, а 3.1.2— вторая
команда алгоритма, уточняющего команду 3.1. При
этом иногда нам будет удобно нумеровать не одну
команду, а серию команд; иногда и вовсе не произ­
водить нумерации или, нарушив принцип вложенности,
поставить использовавшийся уже номер. Мы думаем,
что читателю во всех таких случаях причины будут
ясны и без предварительных пояснений. Точно также
могут встретиться и некоторые нигде не прокомменти­
рованные пометки, если у нас возникнет подозрение,
что здесь и без того должно быть ясно (ибо много­
кратное повторение в мелочах начинает утомлять).
92


В завершение предстоит сборка основного алгорит­
ма из тех составляющих, на которые он будет разложен.
1. Сформировать уравнение.
нач
1.1 сформировать конечную случайную последо­
вательность S длины 1000 (S(∕)∈[0,l] )
1.2 запросить номер ∕≤ 1000 (Задумайте число
∕≤ 1000)

сформировать квадратное уравнение так:

1.3 сформировать из S(/) целое число В так, чтобы
∣S∣<10
Cl: = B
/: = /+1
1.4 если I > 1000
I
то /: = 1
все
1.3 сформировать из S(/) целое число В так, чтобы
∣B∣<10
C2:=B
k=I+i
1.4 если I > 1000
|
то I: = 1
все
P. = C∖+C2
Q: = Cl • C2
1.5 записать уравнение X2 — PX + Q = 0
кон

Здесь команды 1.1, 1.2, 1.3 и 1.5 нуждаются в даль­
нейшем уточнении. Команде ветвления 1.4 присвоен
номер затем, чтобы в дальнейшем выяснить, сколько
раз эта команда встречается в основной программе
и имеет ли смысл вынести ее в качестве подпрограммы.
Служит она для того, чтобы не допустить выхода
за пределы массива S.
Команда 1.2 предусмотрена для того, чтобы вы,
начиная упражнения в очередной раз, не начинали
с тех же уравнений, которые предъявлялись вам в пре­
дыдущий раз. Для этого требуется лишь задумать
новое число.
1.1 Сформировать конечную случайную последовательностьдлины 1000 (S(/) ∈ [0,1] ).
∂∂


Для этих целей в Бейсике существует стандартная
функция RND(X). Напишем фрагмент программы:
110 DIM S (1000)
120 FOR I = 1 ТО 1000
130 S (I)=RND (I)
140 NEXT I
Номера с 10 по 100 мы зарезервировали для
описания условий задачи. Поэтому номер первого опе­
ратора в приведенном фрагменте— 110.
1.2. Запросить номер ∕≤ 1000.

нач
PRINT' введите натуральное число I ≤ 1000'
/=?
застраховаться от ошибок при вводе / так:
/: = целая часть (|/|)
если / = 0
то 1= 1
иначе если I > 1000
1.2
1∙"∙ 1(1.4)
A∖ *• /
то I: = 1

все

все
кон
1.3. Сформировать из S(/) целое число В так, чтобы
∣B∣≤10. В алгоритме 1 команда 1.3 встречает­
ся дважды. Вы увидите, что для ее использования
необходимо реализовать достаточно большой алго­
ритм. Поэтому этот алгоритм лучше выделить
в качестве подпрограммы. Дадим ей имя ЦЕЛ
(S(7), В)
ЦЕЛ (S(I), В)
нач
1.3.1
сформировать из S(/) натуральное число
^<10
B: = K
/:=/+1
1.3.2
(1.4) если 7> i000

To/:=/+l
все
94


сформировать из S(Γ) натуральное число
A<10
M: = K
7z=7÷l
(1.4) если 7>1000

1.3.1

1.3.2

To/:=/+l

все
по четности числа M определить мно­
житель ⅛1 или —1 для числа В так:
N:=M/2
R: = целая часть (N)
если R = N

то L: = 1
иначе L: — — 1
все
B:=L-B

кон
В ЦЕЛ (S(/), В) дважды встречается команда 1.3.1.
Для того чтобы реализовать эту команду, необходимо
исполнить некоторый алгоритм, который мы ниже и при­
водим. Естественно, что этот алгоритм тоже будет вы­
делен в качестве подпрограммы, которую мы назовем
HAT (S(7), К)
1.3.1. Сформировать из S(7) натуральное число
K<10.
HAT (S(/), К)
нач

K: = S^
пока К ≤ 1
нц
A: = 10-A
кц
К: = целая часть (А)

кон

Очевидно (анализируя предыдущее), что можно вы­
делить в качестве подпрограммы и команду ветвления
1.4. Дадим ей имя ПЕРЕПОЛНЕНИЕ (/, 7)
98


1.4. ПЕРЕПОЛНЕНИЕ (/, I)
нач
если / > 1000
то /: = 1
все
кон

1.5. Записать уравнение X2 — PX + Q == 0.
В приведенном дальше алгоритме дано описание
частей, из которых состоит данное квадратное уравне­
ние, а также способа их построчной упаковки на экране
дисплея. Символ u_j означает пробел.
нач
в первой строке: ^_i 2
организация печати во второй строке такая:
если P>0
то если Q > 0
иначе X^L^ — L^PXL^ —
— L_J | Q| L__J = L_l0

все
иначе если Q>0
TO

X^JL_j + L_j|P|XL_j +
+ ^QL^ = L_jO

иначе X^∣ L_j + L_j |P|XL_j
^^Ш^-^()
кон

все

—

все

Итак, уточнение команды 1 завершено полностью.
Рассмотрим команду 2. Она не принесет нам больших
хлопот.
2. Сформулировать задачу.
нач
напечатать:
найдите корни этого уравнения,
используя теорему,
обратную теореме Виета
кон
Приступим теперь к уточнению команды 3.
3. Произвести опрос.
96


Ал гоpиτ м

Коммен­
тарии

нач

запросить ввод корней так:
Напечатать : введите значение первого корня XI:
X1=?
если XI = C1
3.1

то J: == 1
зап росить ввод второго корня
иначе если XI = C2

3.2

то J: = 2
запросить ввод второго корня
иначе V: = 1
повторить ввод

3.3

все
произвести анализ ответов: переключатель по V

3.1

*

**

***
IV*

все
V*

кон

Комментарии к алгоритму
*) Введем переменную J для того, чтобы зафикси­
ровать, с каким из хранящихся в памяти значением кор­
ня (C1 или C2) совпадает первое введенное с кла­
виатуры число. Если XI = C1, то присвоим J значение 1.
* ♦) Если XI = C2i то присвоим / значение 2. После
этого мы будем знать, с каким из С] (J = 1,2) сравнивать
второе введенное число.
***) Введем еще одну переменную V. Значение,
которое она приобретет в результате исполнения этого
алгоритма, должно дать нам точное представление
о том, какая сложилась ситуация после ввода корней:
V = 1 — первый корень вычислен неверно;
V = 2 — оба корня вычислены верно;
V = 3 — второй корень вычислен неверно, в то вре­
мя как первый корень вычислен верно и
совпал с Cl (/ = 1);
V = 4 — второй корень вычислен неверно, в то вре­
мя как первый корень вычислен верно и
совпал с C2 (J = 2);
V = 5 — оба корня вычислены верно и изъявлено
желание прекратить игру.
Случай, когда V присваивается значение 1, вы ви­
дите явно. Ясно, что остальные четыре случая возни­
97


кают после ввода второго корня. Поэтому мы должны
будем их предусмотреть, уточняя команду 3.1.
IV*) Повторить ввод — это сложная команда, в ре­
зультате исполнения которой должно быть дано пояс­
нение допущенной при вводе корней ошибки.
V*) В Бейсике существует оператор ON GOTO (его
называют переключателем), который позволяет осу­
ществлять переход к одной из указанных строк в зави­
симости от значения числового выражения. Формат
оператора ON GOTO
нс ON e GOTO HCι, HC2, ...» нск.
Здесь ON — имя оператора; e — переключающее ариф­
метическое выражение; GOTO — служебное слово;
нс/ — номер строки первого оператора i-й ветви.
Переключающее арифметическое выражение e обыч­
но стараются подобрать таким образом, чтобы оно при­
нимало значения 1, 2, ..., k, При выполнении оператора
ON вычисляется значение управляющего выражения e
и выделяется его целая часть i. Если i = 1, то управление
передается оператору πcι (τ. e. первой ветви), если
i = 2, то — оператору нс2 и τ. д. Если вычисленное зна­
чение i не попадает в интервал [1, k∖ то это считается
ошибкой и выполнение программы прекращается [11].
В нашем случае переключающим арифметическим
выражением будет служить V, а переключатель по V
должен действовать так (уточнение команды 3.3):
если V = 1, то перейти к повторному вводу первого
корня;
если V = 2, то перейти к формированию нового
квадратного уравнения;
если V = 3, то перейти к повторному вводу второго
корня с позиции, когда J = 1;
если V = 4, то перейти к повторному вводу второго
корня с позиции, когда J = 2;
если V = 5, то выйти на останов.
Больше мы ничего не можем сказать, так κaκ,πoκa
не написана вся программа, не известны номера тех
строк, с которых начинается каждая из перечисленных
пяти ветвей.
Перейдем к уточнению команд алгоритма 3 (напо­
мним, что команду 3.3 нам пришлось уточнитьвыше).
3.1. Запросить ввод второго корня.
Уточнение этой команды составит некоторый доста­
точно протяженный алгоритм, а сама команда встреча­
ется в алгоритме 3 дважды. Поэтому удобно уточняю­
98


щий ее алгоритм выделить в виде подпрограммы. Да­
дим ей имя ВТОРКОР (второй корень).

ВТОРКОР
нач
напечатать: введите значение второго кор­
ня X2:
X2 = ?
если / = 1
то если X2 = C2
то V: = 2
окончание
3.1.1
иначе V: =3
повторить ввод
3.1.2(3.2)
все
иначе если X2 = C1
тоУ:=2
окончание
иначе V: = 4
все
повторитьввод

3.1.1
3.1.2 (3.2)

все

кон

Нсуточненной в алгоритме 3 остается лишь команда
3.2. Она же дважды встречается и в алгоритме 3.1.
Поэтому мы выделим уточняющий ее алгоритм в ка­
честве подпрограммы с именем ПОВТОРНЫЙ ВВОД.
Затем дважды в алгоритме 3.1 встречаем команду
ОКОНЧАНИЕ. Вероятно, целесообразно выделить
одноименную подпрограмму, уточняющую и это предпи­
сание.
3.1.1
. Окончание.
ОКОНЧАНИЕ

нач
напечатать:
хотите ли вы повторить упражнение?
Если нет — введите число 0,
если да — число, отличное от 0.
H=?
если н = ∩
99


то V: = 5 (признак выхода из игры)

все

кон
3.1.2

(3.2) Повторить ввод.

ПОВТОРНЫЙ ввод
нач
напечатать:
НЕВЕРНО.
по теореме, обратной теореме Виета, нужно отыс­
кать такие числа X∖ и X2, чтобы
'XI +X2 = ,P'/
'X∖∙X2 = 'Q'.'
Это и будут искомые корни.
Повторить ввод.

кон
Примечание. В записи
'Xl+X2 = ,P7
'XI ∙X2='Q'/

буквы P и Q не окружены апострофами. Здесь взяты
в апострофы с двух сторон:
в первой строке: 'X∖ +X2=, и ',',
во второй строке: 'X∖ ∙X2=' и '.,.
Это означает, что мы хотим, чтобы вместо P и Q в соот­
ветствующих местах выводились соответствующие этим
буквам числовые значения. Тогда в каждом конкретном
примере может быть дана конкретная подсказка.
Осуществим, наконец,сборку всего алгоритма. Так
как все его составляющие части пронумерованы, а все
вспомогательные алгоритмы имеют имена, это несложно
выполнить. Начнем алгоритм с описания задачи. Если
некоторая строка выделяется как комментарий в буду­
щей программе, мы начинаем ее соответствующим
оператором Бейсика — REM.
Возникает также желание, чтобы любой, кто завер­
шит эту игру, мог бы по окончании узнать о том, как
он работал: какое количество уравнений им решено и
сколько допущено при этом ошибок. Удовлетворить
столь законное любопытство несложно. Для этого вве­
дем два счетчика — E (переменная, в которой будет
накапливаться количество решенных уравнений) и Z
(переменная, в которой будет накапливаться количество
100


допущенных при этом ошибок). Первоначально прида­
дим E и Z одно и то же значение 0. Затем надо преду­
смотреть, чтобы всякий раз перед подачей нового урав­
нения E увеличивалось на 1 и всякий раз, когда
совершается ошибка, чтобы Z увеличивалась на 1.
Естественно, надо предусмотреть также и то, чтобы, вы­
ходя на останов, программа выводила бы предваритель­
но на экран дисплея значения E и Z. Соответствую­
щие вставки в основной алгоритм мы поместим в ра­
мочки, чтобы читатель не искал их в предыдущем
тексте, а видел бы, что это новые, предусмотренные
нами дополнительно, вкрапления.
Еще одно замечание. Мы не будем в основном
алгоритме выделять подпрограммы служебными сло­
вами нач и кон. Вместо этого каждая подпрограмма
будет начинаться комментарием, содержащим ее имя,
а завершаться оператором Бейсика RETURN, который
должен завершать в Бейсике любую подпрограмму.
Для того чтобы читателю было легче следить за тем,
как это (уже достаточно длинный) алгоритм переведен
на Бейсик, мы пронумеровали его строки соответственно
тому, как будут пронумерованы операторы Бейсика.

ИГРАЕМ В ТЕОРЕМУ ВИЕТА
нач
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170

напечатать:
теорема, обратная теореме Виета:
если числа XI и X2 удовлетворяют
условиям XI + X2 = —P и XI • X2 = Q,
то они являются корнями уравнения:
Lj2
X ι__ | |__ | + I__ I PX I__ I 4~ I—I Q ^∣ - ।—10.
Выполним несколько упражнений
на применение этой теоремы
Минуточку.
Я подготовлюсь.
DIM S (1000)
FOR I = 1 ТО 1000
S(I) = RND (I)
NEXT I
напечатать: введите натуральное число ∕≤
<1000.
/=?
REM застраховаться от ошибок при вводе
/ так:
101


180
190
200
210

7: = целая часть (111)
если 7 = 0
то I: = 1
иначе ПЕРЕПОЛНЕНИЕ (7, 7)
все

220
230

REM E—количество решенных уравнений
REM Z — количество ошибок при вводе
Xi и X2
E: = 0, Z∙. = 0_______________________________________

240
250

260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420

^EM сформировать квадратное уравнение
так: <-------——-----------------------------------—
E:=E+1

ЦЕЛ (S (Г), В)
C∖. = B
/:=/+1
ПЕРЕПОЛНЕНИЕ (7, 7)
ЦЕЛ (S(7), В)
C2:=B
k=I+l
ПЕРЕПОЛНЕНИЕ (7, 7)
P: = C∖ + C2
Q: = Cl-C2
REM записать квадратное уравнение так:
В первой строке: i_i2
REM организация печати во второй строке
такая:
если P>0
то если Q > 0

TO X ι—i ι—i — i__ ∣ PX ∣__ ∣ ^4 - 1—I Q I__ I = 1__ I 0
иначе X t_j u_j — u_i PX u_j __
— ∣—11 Q| ∣—∣ = ।__∣0

430

все
иначе если Q > 0
то A'L_JL_, + ^|P|X^ +
+ I__ I Ql__ I = I__ l0
иначеХцц + и^|Р|Хц —
-- I__ I | Q | 1__ I = L_J 0
все

440
450
460

все
102


470
480
490
500
510

520
530
540
550
560
570
580
590

напечатать:
найдите корни этого уравнения,
используя теорему,
обратную теореме Виета.
REM запросить ввод корней так:
напечатать: введите значение первого кор­
ня XI *------------ -----------------------------------X1 = ?
если XI = C1
то к = 1
ВТОРКОР *---------------------------иначе если XI = C2
то к = 2
ВТОРКОР *-------------иначе V: = 1

| Zι=Z÷l |

600
610
620

все ПОВТОРНЫЙ ВВОД
все
ПЕРЕКЛЮЧАТЕЛЬ ПО V: V = 1--------V = 2----------V = 3-----V=4 ^

V = 5 ---------630
640
650
660
670
680
690
700
710
720
730
740
750
760
770

REM ∏ О Д ∏ P О Г P A M M Ы
REM подпрограмма ЦЕЛ (S (Z), В)
HAT (5 (/), X)
B. = K
I∙. = ι + ι
ПЕРЕПОЛНЕНИЕ (7, ^
HAT (S(7), X)
M: = X
k=I+∖
ПЕРЕПОЛНЕНИЕ (7, 7)
N:=M/2
R: = целая часть (X)
если R = N
то L: = 1
иначе L: = — 1

780

все
B.=L∙B
103


790
800
810
820
830

RETURN
REM подпрограмма HAT (S (I), K)
K'.-S(Γ)
пока К < 1
нц

K: = 10-K

840
850
860
870
880

890
900
910
920

930
940
950
960
970
980

кц
K^. — целая часть (К)
RETURN
REM подпрограмма ПЕРЕПОЛНЕНИЕ (I,I)
если / > 1000
то I: = 1
все
RETURN
REM подпрограмма ВТОРКОР
напечатать: введите значение второго кор­
ня X2.
X2 = ?
если / = 1
то если X2 — C2
то V: = 2
ОКОНЧАНИЕ
иначе V: = 3
I Z: = Z+1 '

990

1000
1010
1020
1030
1040

все
ПОВТОРНЫЙ ВВОД
иначе если X2 = СТ
то V: = 2
ОКОНЧАНИЕ
иначе V: = 4
|Z:=Z+1

1050
1060

ПОВТОРНЫЙ ход

все

все
RETURN
REM подпрограмма ОКОНЧАНИЕ
напечатать:
1090 Хотите ли вы повторить упражнение?
1100 Если нет — введите число 0,

1070
1080

104


1110
1120
1130
1140
1150
1160

1170
1180
1190
1200
1210
1220
1230
1240
1250

1260
1270
1280 кон

если да — число, отличное от 0.
H=?
если H = 0

то V: = 5
все
RETURN
REM подпрограмма ПОВТОРНЫЙ ВВОД
напечатать:
неверно
По теореме, обратной теореме Виета,
нужно отыскать такие числа XI и X2,
чтобы
'Xl+X2='P'/
'XI ∙X2='Q'/
Это и будут искомые корни.
Повторить ввод
RETURN
напечатать:
'Число решенных вами уравнений—,E ⅛---'Число допущенных при этом ошибок—'Z

Теперь легко осуществить переход от описанного на­
ми выше алгоритма к соответствующей ему программе
на Бейсике.
Программа на Бейсике
5 REM ИГРАЕМ В ТЕОРЕМУ ВИЕТА!
10 PRINT 'ТЕОРЕМА* ОБРАТНАЯ ТЕОРЕМЕ ВИЕТА'
20 PRINT 'ЕСЛИ ЧИСЛА XI И X2 УДОВЛЕТВОРЯЮТ'
30 PRINT 'УСЛОВИЯМ Xl+X2= ~P И XlX2=Q.∏'
40 PRΓNT 'ТО ОНИ ЯВЛЯЮТСЯ КОРНЯМИ УРАВНЕНИЯ!'

50 PRINT ' 2'
Ь0 PRINT 'X + PX + Q = 0'
70 PRINT 'ВЫПОЛНИМ НЕСКОЛЬКО УПРАЖНЕНИЙ'
80 PRINT 'НА ПРИМЕНЕНИЕ ЭТОЙ ТЕОРЕМЫ'
Э0 PRINT 'МИНУТОЧКУ '
100 PRΓNT 'Я ПОДГОТОВЛЮСЬ
ПО ШМ S<1000)
1РЙ F∩R 1 = 1 ТО 1000
130 S<I)=RND(D
140 NEXT I
150 PRINT 'ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО I<1ΘΘ0'
160 INPUT I
170 REM ЗАСТРАХОВАТЬСЯ ОТ ОШИБОК ПРИ ВВОДЕ I ТАК!
180 I=INT<ABS<D)
130 IF I<>0 THEN 210
200 1=1 x G0 ТО 220
210 O∏SUB 870
220 REM E- КОЛИЧЕСТВО РЕШЕННЫХ УРАВНЕНИЙ

105


230
240
250
26Θ
270
288
290
300
310
320

REM Z - КОЛИЧЕСТВО ОШИБОК ПРИ ВВОДЕ XI И X2
E=θ 4 Z=θ
REM СФОРМИРОВАТЬ КВАДРАТНОЕ УРАВНЕНИЕ ТАК:
E=E+1
GOSUB 640
Cl=B
I=I+1
GOSUB 870
GOSUB 640
C2=B

330 ι=ι÷ι

340 GOSUB 870
350 P=Cl+C2
360 Q=Cl*∙C2
370 REM ЗАПИСАТЬ КВАДРАТНОЕ УРАВНЕНИЕ TAK≡
380 PRINT ' 2'
390 REM ОРГАНИЗАЦИЯ ПЕЧАТИ ВО ВТОРОЙ СТРОКЕ ТАКАЯ
400 IF P<=θ THEN 440
410 IF Q<=Θ THEN 430
420 PRINT ЛХ - 'P'X + 'Q, = 0'
425 GO ТО 470
430 PRINT ЛХ - ЛРЛХ - 'ABS<Q)' = 8Л
435 GO ТО 470
440 IF Q<=θ THEN 460
450 PRINT 'X + ЛАВЗ<Р)ЛХ + ЛСГ = 0'
455 GO ТО 470
460 PRINT ЛХ + 'ABS<P)'X - 'ABS<Q)' ≈ 0Л
470 PRINT 'НАйДИТЕ КОРНИ ЭТОГО УРАВНЕНИЯЛ
480 PRINT 'ИСПОЛЬЗУЯ ТЕОРЕМУЛ
490 PRINT ЛОБРАТНУЮ ТЕОРЕМЕ ВИЕТАЛ
500 REM ЗАПРОСИТЬ ВВОД КОРНЕЙ TAK≡
510 PRINT∙'BBEAHTE ЗНАЧЕНИЕ ПЕРВОГО КОРНЯ Х1Л
520 INPUT XI
530 IF X1<>C1 THEN 568
540 J≈1
550 GOSUB 910
555 GO ТО 620
560 IF Xl<>C2 THEN 598
570 J=2
580 GOSUB 910
585 GO ТО 620
590 U=1
600 2=2+1
610 GOSUB 1160
620 ON U GO TO 510/250.*550/580.*1260
630 REM ПОДПРОГРАММЫ
64И REM ПОДПРигНйПМЯ UtJI (UUbB)
650 GOSUB 800
660 B=K
670 I=I+1
680 GOSUB 870
690 GOSUB У00
700 M=K
710 I=I+1
720 GOSUB 800
730 N=M/2
740 R≈INT<N)
750 IF RON THEN 770
760 L≈1 ч GO ТО 780
770 L=-1
780 B=L*B
790 RETURN
800 REM ПОДПРОГРАММА HAT<S<I)/K)
810 K=S<I)
820 IF K>≈1 THEN 850
830 K=lΘ≡K

106


84Θ GO TO 820
850 K≈INT<K>
860 RETURN
870 REM ПОДПРОГРАММА ПЕРЕПОЛНЕНИЕ<Ы>
880 IF I<=100Θ THEN 900
890 1=1
900 RETURN
910 REM ПОДПРОГРАММА BTOPKOP
920 PRINT 'ВВЕДИТЕ ЗНАЧЕНИЕ ВТОРОГО КОРНЯ X2'
930 INPUT X2
940 IF .J<>1 THEN 1610
950 IF X2<>C2 THEN 980
960 U≈2
970 GOSUB 1080
975 GO TO 1070
980 U=3
990 Z≈Z+1
1000 GOSUB 1160
1005 GO TO 1070
1010 IF X2<>C1 THEN 1040
1020 U=2
1030 GOSUB 1080
1035 GO TO 1070
1040 U=4
1050 Z=Z+1
1060 GOSUB 1160
1070 RETURN
1080 REM ПОДПРОГРАММА 0 K 0 H 4 A H И E
1090 PRINT 'ХОТИТЕ ЛИ ВЫ ПОВТОРИТЬ УПРАЖНЕНИЕ?*
1100 PRINT 'ЕСЛИ НЕТ - ВВЕДИТЕ ЧИСЛО θ∕'
1110 PRINT 'ЕСЛИ ДА - ЧИСЛО/ ОТЛИЧНОЕ ОТ 0’.'
1120 INPUT H
1130 IF H<>0 THEN 1150
1140 U=5
1150 RETURN
1160 REM ПОДПРОГРАММА ∏ 0 В T 0 P H Ы й В В 0 Д
1170 PRINT 'НЕВЕРНО'
1180 PRINT 'ПО ТЕОРЕМЕ/ ОБРАТНОЙ ТЕОРЕМЕ ВИЕТА/'
1190 PRINT 'НУЖНО ОТЫСКАТЬ ТАКИЕ ЧИСЛА XI И X2/'
1200 PRINT 'ЧТОБЫ'
1210 PRINT 'Xl+X2='P'/'
1220 PRINT 'XlX2='Q'.'
1230 PRINT 'ЭТО И БУДУТ ИСКОМЫЕ КОРНИ'
1240 PRINT 'ПОВТОРИМ ВВОД'
1250 RETURN
1260 PRINT 'ЧИСЛО РЕШЕННЫХ ВАМИ УРАВНЕНИЙ - 'E
1270 PRINT 'ЧИСЛО ДОПУШЕННЫХ ПРИ ЭТОМ ОШИБОК - 'Z
1280 END


1. Решение логических задач
методом характеристических уравнений

Существует ряд научно-популярных книг, посвя­
щенных решению логических задач (в том числе и с
применением ЭВМ). Упомянем здесь, в частности, [12],
[13], [14]. Мы же ставим перед собой значительно более
скромную цель: отталкиваясь от методов и идей, зало­
женных в указанной литературе, построить одну част­
ную схему программирования для решения логических
задач. Читателя, заинтересовавшегося программирова­
нием логических задач и желающего самостоятельно
экспериментировать в этом направлении, мы отправ­
ляем к упомянутым книгам.
Решим следующую задачу ([12], с. 74, задача 1).
Пятеро друзей.
Пятеро друзей решили записаться в кружок люби­
телей логических задач: Андрей (А), Борис (Б), Вик­
тор (В), Григорий (Г), Дмитрий (Д). Но староста
кружка предложил им выдержать вступительный экза­
мен. «Вы должны приходить к нам по возможности
больше вечеров, однако в разных сочетаниях, соблю­
дая следующие условия:
1. Если А приходит вместе с Д, то Б должен
присутствовать.
2. Если Д отсутствует, то Б должен быть, а В пусть
не приходит.
3. А и В не могут одновременно ни присутство­
вать, ни отсутствовать.
4. Если придет Д, то Г пусть не приходит.
5. Если Б отсутствует, то Д должен присутствовать,
но это в том случае, если не присутствует В. Если же
В присутствует при отсутствии Б, то Д приходить не
должен, а Г должен прийти».
108


Сколько вечеров и в каком составе друзья могли
прийти?
Задание. Решите задачу при измененном указа­
нии 5: «Если Б отсутствует, то Д должен присутство­
вать, но только в том случае, если не присутствует В.
Если же В присутствует (независимо от присутствия
или отсутствия Б), то Д приходить не должен, а Г дол­
жен прийти».
Прежде чем приступать к решению этой задачи, на­
помним, что наша конечная цель — построение неко­
торой схемы программирования для решения логи­
ческих задач. Поэтому с самого начала надо догово­
риться о способе обозначений, который должен быть
единым для всех задач. В нашей задаче действующие
лица — Андрей, Борис, Виктор, Григорий и Дмитрий.
Их пять,и мы условились обозначать их А, Б, В, Г, Д,
соответственно. В другой задаче речь может пойти
о лампочках, переключателях, станках и τ. д. Число этих
«персонажей» может быть другим. Поэтому условимся,
что в каждой задаче имеется свое линейно упорядочен­
ное множество «персонажей» P. Его элементы обозна­
чаются так: P(1), P(2), P(3), .... Поэтому, прежде чем
приступить к решению задачи, нужно построить таблицу
соответствия, аналогичную той, которую мы приводим:
P(D

P(2)

P(3)

P(4)

P(5)

Л

Б

В

Г

д

Затем нужно формализовать условия задачи. Разбе­
ремся в этом подробнее.
1. Если А приходит вместе с Д, то Б должен при­
сутствовать.
Будет весьма удобно (и вы вскоре это обнаружите),
если повествовательное предложение ≪A приходит» мы
обозначим той же буквой А. Аналогично: «Д прихо­
дит» — Д, «Б присутствует» или (что то же самое) «Б
приходит» — Б. Тогда структура предложения 1 выри­
совывается четче:
Если (А и Д), то Б.
(2)
Скобки, которые мы здесь употребляем, не являются
(пока!) лишними. Действительно, если в (2) скобки
опустить:
(3)
Если А и Д, то Б,
109


то полученная запись (3) мысленно может быть (воз­
можно) воспринята и так:
Если А и (Д, то Б).
(4)

С самого начала относительно (4) необходимо уточ­
нение о том, как понимать запись в скобках: «Д, то Б».
Очевидно (другого и не придумаешь), как: «Если Д, то
Б». Тогда из (4) имеем:
Если А и (если Д, то Б).
(4')
Сравним теперь (4') и (2). В случае (2) мы имеем дело
с повествовательным предложением, в котором что-то
утверждается. В случае же (4') повествовательное
предложение не получилось. Сформулировано лишь не­
которое условие (говорят еще — посылка), но нет ника­
кого заключения. Запомним: записи, не отражающие
(не передающие) содержание каких-либо повествова­
тельных предложений, нас вовсе не интересуют. Та­
кие записи не исчерпываются записями типа (4).
К ним относятся также восклицательные и вопро­
сительные предложения, а также различные опре­
деления.
Обратимся вновь к записи (2). Она сконструиро­
вана из трех букв (А, Б, Д) и двух связок: «и» и «если....
то ...». Договоримся о следующих символьных обо­
значениях:
и

если ..., то ...

Л

... →-...

Тогда из (2) получим:
(AΛΛ)→B.

(5)

(6)

Запись (6) представляет собой совершенно точный
«каркас» предложения 1. Может оказаться, что некото­
рое предложение сильно отличается от 1 по форме
(настолько, что может быть сказано совершенно
иначе, например:«И Б является тотчас же, лишь соизво­
лят быть и А и Д»), но стоит разложить это последнее
на атомы, не поддающиеся уже более делению и пред­
ставляющие собой элементарные повествовательные
предложения, а затем сконструировать из них «каркас»
исходного предложения, как вы увидите, что получи­
лось точь в точь (6). Значит, (6) несет в себе то
но


характерное, что нельзя изменить, не изменив самой
сути предложения.
Теперь перенесем наш анализ в иную плоскость.
Рассмотрим предложение А: «А приходит». Относи­
тельно его можно выделить в точности две ситуации:
а) А действительно приходит и б) А на самом деле
не пришел. В случае а) утверждение А оказывается
истинным, а в случае б) — ложным и третьего не
может быть.
Под высказыванием в математической логике по­
нимают повествовательное предложение, относи­
тельно которого имеет смысл утверждать, истинно оно
или ложно, но ни то и другое одновременно.

Таким образом, предложение А является высказы­
ванием. Аналогично, высказываниями являются предло­
жения Б и Д. Как видим, истинностное значение вы­
сказывания ситуативно.
Истинностные значения, описанные выше, удобно
обозначать символами 0 и 1, используя следующее
соответствие:
истинно

ложно

1

0

Теперь перейдем к анализу предложения АДД.
Относительно его возможны уже 4 ситуации, которые
получаются комбинированием всевозможных ситуаций
для А и для Д. Вот таблица этих комбинаций:
А

д

1
0
1
0

1
1
0
0

Других комбинаций быть не может.
Но вопрос, который здесь возникает, зна­
чительно сложнее. А именно: возможно ли
и как однозначным образом заполнить
истинностными значениями 0 и 1 послед­
ний столбец следующей таблицы:
А

Д

1
0
1
0

1
1
0
0

АЛД

(8)

111


Если мы получим положительный ответ на сформули­
рованный вопрос при таком подходе, то АДД— вы­
сказывание. В противном случае — нет. Однако, увы,
искать напрямую ответ на этот вопрос тщетно. Мы мо­
жем заполнить таблицу (8), опираясь на свою интуицию
и здравый смысл. Скорее всего, у каждого из вас полу-

должно быть так. Хотя и сомнения в данном случае тоже
врядли будут возникать. Другой пример, в котором воз­
можны разные варианты, мы увидим несколько позже.
Так как же здесь быть? Вспомним обычную ариф­
метику. Вряд ли кто-нибудь смог бы сказать, каким
числом можно заменить запись 125×3, если бы он не
знал определение арифметической операции «умноже­
ние» и правило, по которому производится умножение
целых чисел (для чисто формального выполнения этого
действия достаточно одного правила). Точно так же
обстоит дело и в математической логике. Изначально
нужно знать определение того действия, которое мы
хотим выполнить. Это действие называют конъюнкцией
двух высказываний (иначе — логическим умножением).
Логическую связку Д также называют конъюнкцией.
Определяется логическое произведение (конъюнкция)
двух высказываний X и Y следующей истинно-функ­
циональной таблицей:

держанию, которое было использовано при построении
таблицы (9). Таким образом, логическое произведе­
ние (конъюнкция) двух высказываний X и Y — это
такое высказывание, обозначаемое X^Y, цстинностное
112


значение которого определяется таблицей (10). Кро­
ме того, если смотреть на X и Y как на переменные,
принимающие свои значения в множестве {0, 1), то таб­
лице (10) соответствовала бы следующая простая
арифметическая таблица:
X

Y

X∙Y

1
0
1
0

1
1
0
0

1
0
0
0

(10')

Обозначим D = {0, 1}. Таблицами (10) и (10') опреде­
ляется одна и та же двоичная функция F(X, Y) из D2
в D, где

D2 = D×D = {(1, 1), (0, 1), (1, 0), (0, 0)}.
Далее уже ясно, что необходимо еще одно опре­
деление для X→Y. Вот оно.
Импликацией высказываний X и Y называется вы­
сказывание, обозначаемое X→Y, истинностное значе­
ние которого определяется следующей таблицей:

X→~Y. Таблица (11) также не противоречит интуитив­
ному содержанию, приписываемому связке «если ...,
то ...». Логическую связку → также называют импли­
кацией.
Если X и Y рассматривать как переменные с об­
ластью определения в D, то таблице 11 соответствует
следующая арифметическая таблица:
X

Y

∖-X+XY

1
0
1
0

1
1
0
0

1
1
0
1

(11')

Таким образом, таблицами (11) и (lΓ) определя­
ется одна и та же двоичная функция F (X, Y) из D2 в D.
Γ>-2740

113


Итак, оглянемся назад. Мы уже знаем, что АДД —
конъюнкция высказываний А и Д, a (AΛΛ)→B
(см. (6)) — импликация высказываний АДД и Б. Вы­
сказывание (6) является сложным, его истинностное
значение зависит от истинностных значений трех вы­
сказываний А, Д и Б. В математической логике (как и
в арифметике) действие, стоящее в скобках, выполня­
ется в первую очередь, поэтому истинностное зна­
чение высказывания (6) определяется следующей таб­
лицей по истинностным значениям высказываний
А, Д и Б:
А

д

АЛД

Б

(АДД)^Б

1
0

1
i

1
0

1
1

1
1

1
0

о
о

0
0

1
1

1
1

1
0

1
1

1
0

0
0

0
1

1
0

0
0

0
0

0
0

1
1

(12)

Если смотреть на А, Д и Б как на переменные,
принимающие свои значения во множестве D, то этой
таблице соответствует двоичная функция F (А, Д, Б)
oττpex переменных (функция из D3 в D, где D3 =
= D*×D).
Вернемся к условиям задачи и попытаемся отве­
тить на вопрос: полностью ли формализовано нами усло­
вие 1?
Чтобы понять смысл этого вопроса, сместим пол­
ностью акцент на тот факт, что выражение (6) может
восприниматься как некоторая формула, которая задает
двоичную функцию F (А, Д, Б) от трех переменных:
F(A, Д, B) = (AΛΛ)→B.
Тогда, используя таблицу (12), мы можем сказать,
например, что F(0, 1, 1)=1, a F(1, 1, 0) = 0 и τ. д.
При таком толковании становится ясно, что в усло­
вии 1 требуется, чтобы
£(А,Д,Б) = 1,
(13)
ИНаЧе
(AΛΛ)→B = 1.
, (13')
114


Другими словами, все решения уравнения (13'),и толь­
ко они, дают истинностные значения соответствующих
высказываний, удовлетворяющие условию 1.
Полагаем, что суть дальнейшего до некоторой степени читателю
уже понятна: каждое из условий задачи будет заменено нами
логическим уравнением типа (13,)∙ Отметим еще, что логическое
уравнение (13) мы можем заменить (используя (10') и (lΓ)) сле­
дующим эквивалентным ему арифметическим уравнением:
1~А.Д + А.Д.Б=1,

(13")

Очевидно настало время прервать основную нить повествова­
ния и дать определение всем основным, использующимся в клас­
сической логике, логическим связкам. Это уже описанные конъ­
юнкция (Л — «и») и импликация (→ — «если ..., то ...»), и новые —
дизъюнкция (V — «или»; иначе дизъюнкцию называют логическим
сложением), отрицание (~∣ — «не») и эквиваленция (~ или ÷÷).
Каждое даваемое нами определение будет сопровождаться двумя
таблицами: первая — основная и вторая — арифметическая. Итак:
1. Отрицанием высказывания X называется высказывание, обо-

Таким образом, каждой из таблиц (14) определяется одна
и та же двоичная функция F(X) из D в D.
2. Эквиваленцией двух высказываний X и Y называется высказы­
вание, обозначаемое X++Y или X~Y, истинностное значение кото­
рого определяется следующей таблицей:
X

Y

X^Y

X

Y

1 - (X - У)2

1
0
1
0

1
1
0
0

1
0
0
1

1
0
1
0

1
1
0
0

1
0
0
1

(15)

Таким образом, каждой из таблиц (15) определяется одна и та
же двоичная функция F(X, У) из D2 вО.
3. Дизъюнкцией (логической суммой) двух высказываний X и
Y называется высказывание, обозначаемое XyY, истинностное зна­
чение которого определяется следующей таблицей:
X

Y

xyγ

X

У

X+Y — XY

1
0
1
0

1
1
0
0

1
1
1
0

1
0
1
0

1
1
0
0

1
1
1
0

(16)

115


Таким образом, каждойиз таблиц (16) определяется одна и та
же двоичная функция F{X, У) из D2 в D.
Примечание. Каждое из сформулированных определении хо­
рошо согласуется с интуитивным представлением о„ соответствующей
связке, употребляемой в повседневной разговорной практике. Неко­
торое уточнение можно сделать в случае связки «или». Эта связка
может употребляться и в разделительном смысле (разделительное
или — либо).
Таблица истинности для нее выглядит так:
X

У

X либо У

1
0
1
0

1
1
0
0

0
1
1
0

Еще раз подчеркнем, что мы будем воспринимать «или» в том
соединительном смысле, который описывается таблицей (16), и упо­
треблять для его обозначения символ дизъюнкции V∙
Дадим еще одно определение. Мы уже упоминали, что запись (6)
может восприниматься как некоторая формула, определяющая
двоичную функцию:
F (А, Д, Б) = (АДДНБ.

Точнее, формулой логики высказываний (коротко — формулой) на­
зывают выражение, имеющее один из следующих видов:
1) 1, 0, X, где X — любая переменная со значениями во множестве
D = $, if
2) V, (FΛQ), (FVQ). (f→Q)> (F**Q), где F и Q-некоторые формулы логики высказываний.
Вот один пример на составление формулы.
((A→B)Λ((CΛD)V^AΛB)))-φop^
так как ее можно
получить следующим образом:
а) А и В — формулы;
б) (A→B)—φoρмyлa;
в) ∏A — формула;
г) ("1АДВ) — формула;
д) С и D — формулы;
e) (СДВ)-формула;
ж) ((СДВ)У(~ИДВ)) — фоРмУла;
з) ((A→β)Λ((CД£>)VUΛΛB))) — φopмyлa.
Отсюда, в частности, видно, что если строго следовать определению
в употреблении скобок, то получается громоздкое, трудно читаемое
выражение. Поэтому принимаются следующие соглашения по эконо­
мии скобок: внешние скобки можно опускать; можно расставить
скобки, учитывая силу связок, в согласии с убыванием которой
связки упорядочиваются так: η , А» V, ^> ^∙ Используя эти
соглашения, приведенную формулу, можно записать проще:
(A→B)A(CΛDV∏ΛΛB).
Соответственно формула (6) перепишется так:
АДД+Б.
И наконец, совершенно ясно, что всякая формула порождает соот­
ветствующую двоичную функцию.

116


Итак, составим логические уравнения,
ствующие условиям задачи:
1) AΛΛ→B=I;
2) ∏Λ→BΛ∏B = 1;
3) AΛB = 0;
∏AΛ∏B = 0;
4) Λ→∏Γ=1;
5) ηB→(ηB→Λ) = l;
∏BΛB→∏ΛΛΓ=1.

соответ­

(17)

Дальнейшее понятно — нужно отыскать такие ком­
бинации значений для А, Б, В, Г и Д, которые удовлетво­
ряли бы одновременно всем без исключения состав­
ленным логическим уравнениям. Эти комбинации и да­
дут нам решение задачи. Проверьте, например, что
такой будет комбинация
А

Б

В

Г

д

0

1

1

0

1

Значит,друзья могли, в частности, прийти в следующем
составе: Борис, Виктор и Дмитрий. Таким образом,
отыскав все возможные комбинации, мы ответим на во­
прос задачи. Однако для этого надо проверить 32 слу­
чая. Вообще говоря — 2" случаев, где n — число ло­
гических переменных. (Почему?) Поэтому с ростом tι
ручной перебор практически неосуществим и его есте­
ственно поручить машине.
Кроме того, имеется способ заменить составленную
нами систему логических уравнений одним равносиль­
ным ей логическим уравнением, которое называют ха­
рактеристическим. Для этого нужно просмотреть все
правые части уравнений и если у какого-либо уравне­
ния правая часть — нуль, то отрицанием левой части
она приводится к единице. Так условие 3) перепишется
следующим образом:
3') Π(AΛB) = 1;
Π(∏AΛ∏B)=1,
а система (17) заменится следующей эквивалентной
ей системой:
117


AΛΛ→B = 1,
∏Λ→BΛ∏B = 1,
η(AΛB) = l,
Π(ηAA∏B) = l,
(17')
Λ→∏Γ=1,
∏B→∏B→Λ) = 1,
ηBΛB→∏ΛΛΓ = ι.
Затем составляется характеристическое уравнение. Для
этого образуют конъюнкцию левых частей системы
(17') и приравнивают ее к единице.
Примечание. Получаем формулу вида
FιΛFtΛF3Λ-ΛFk.
Спрашивается, в каком порядке нужно выполнять
здесь действия. Оказывается, что это не имеет, как
и при умножении в обычной арифметике, абсолютно
никакого значения. Поэтому отсутствие скобок в запи­
санной формуле законно. Этот факт легко устанавли­
вается с помощью истинностных таблиц. Так для трех
сомножителей имеем:
Fl

F2

Fb

{Fx^F2}^F3

^lΛ(^2Λ^3)

1
0
1
0
1
0
1
0

1
1
0
0
1
1
0
0

1
1
1
1
0
0
0
0

1
0
0
0
0
0
0
0

1
0
0
0
0
0
0
0

Аналогичное замечание справедливо и для fe-членной
дизъюнкции.
В нашем примере будем иметь:
(AΛΛ→ Б) Λ (∏Λ→BΛ3B)Λ3(AΛB) Λ
Λ∏(∏AΛ3B) Λ (Λ→3Γ) Λ ∏B→(∏B→Λ)) Λ (18)
Λ (∏BΛB→mΛ∏=l.

Получено характеристическое уравнение, равно­
сильное системе (17,).
Обоснование ([12J, с. 72).
Пусть некоторая комбинация значений для А, Б,
В, Г и Д является решением системы уравнений (17').
При подстановке в характеристическое уравнецйе она
118


обращает каждый сомножитель конъюнкции в единицу.
Следовательно, и конъюнкция равна единице.
Верно и обратное — каждое решение характеристи­
ческого уравнения (обращающее конъюнкцию в еди­
ницу), обращае! в единицу все сомножители конъ­
юнкции. Следовательно, удовлетворяет системе урав­
нений (17').
Вывод: чтобы ответить на вопрос, поставлен­
ный в задаче, нужно найти все решения характе­
ристического уравнения (18).

Теперь мы вплотную подошли к вопросу о том, как
поручить машине решение ур^авнения (18). При этом
мы хотим иметь некоторую общую схему, которая
годилась бы для любой задачи типа той, которую мы
решаем.
Левая часть уравнения (18) представляет собой дво­
ичную функцию F (А, Б, В, Г, Д) от пяти переменных.
Машина должна просчитывать значения функции на
каждом наборе значений этих переменных и выде­
лять те наборы, при которых значение функции
равно 1. (Впрочем, эту часть можно и опустить.)
Поступим следующим образом. Допустим, что
в искомой программе имеется пять подпрограмм:
для η : α∣ Z = 1 -X∖RETURN,
дляД:а2 Z = X*Y∖RETURN,
для V=∞3Z = X + Y-X*Y∖RETURN,
для →: a4 Z = 1 — X + X*Y∖RETURN,
для ÷>: a5 Z = 1 - (X - Y)**2∖RETURN,
где a, — номер строки, содержащей д-ю подпрограмму.
Тогда мы сможем составить программу решения урав­
нения F(A, Б, В, Г, Д) = 1, не преобразуя каждое уравнениесистемы (17z) потипу (13") инепереводяуравненение (18) в эквивалентное ему арифметическое урав­
нение. Схема может быть совсем иной. Используя
таблицу соответствия (1), зададим программу вычис­
ления значений двоичных функций, стоящих в левых
частях уравнений системы (17'), следующим образом:
βo K = 0
β1 X = P (1) ∖Y = P (5) ∖GOSUBa2∖X = Z∖Y = P (2) ∖
GOSUBa4∖K = К + 1 ∖S (К) = Z
119


Здесь вычисленное значение функции, стоящей в
левой части первого уравнения системы (17'), пере­
дается под номером Λ = A+1 на хранение в спе­
циально зарезервированный массив S. Аналогичные
пересылки организуются и при каждом последующем
вычислении. Получим:
β2
X = P(5)∖GOSUBα1∖Zl=Z∖X = P(3)∖
GOSUBαι∖X = P (2) ∖Y=Z∖GOSUBa2∖X = Z1 ∖
Y = Z∖GOSUBa4∖K = К + l∖S (К) = Z
β3
X = P(l)∖Y = P(3)∖GOSUBa2∖X = Z∖
GOSUBaι∖K = К + l∖S (К) = Z
β4
X = P(l)∖GOSUBaι∖Zl=Z∖X = P(3)∖
GOSUBaι∖X = Zl∖Y = Z∖GOSUBa2∖X = Z∖
GOSUBa1∖K = K+ l∖S (К) = Z β5
X = P(4)∖GOSUBaι∖X = P(5)∖Y = Z∖
GOSUBa4∖K = K+ l∖S (К) = Z
β6
X = P (3) ∖GOSUBa1∖X = Z∖Y = P (5) ∖
GOSUBa4∖Zl = Z∖X = P (2) ∖GOSUBa1∖X =
= Z∖Y = Zl∖GOSUBa4∖K = K+ l∖S (К) = Z
β7
X = P(2)∖GOSUBa1∖X = Z∖Y = P(3)∖
GOSUBa2∖Zl=Z∖X = P (5) ∖GOSUBa,∖X = Z∖
Y = P (4) ∖GOSUBa2∖X=Z 1 ∖Y = Z∖COSUB a4∖
K = K+l∖S(K) = Z
β8
F=1
β8 + 1 FOR T = 1 ТО К
β8÷2 F = F*S(T)
β8 + 3 NEXT T
Здесь β, — номер соответствующей строки. В стро­
ках β8, β8 + 1, β8 + 2, β8 + 3 организовано вычисле­
ние значения F логического произведения, стоящего
в левой части уравнения (18), по вычисленным выше
значениям S(A) его сомножителей. Затем следует
организовать печать заданного набора значений пе­
ременных P{Γ) (/=M) и соответствующего ему
значения F.
Ясно, что фрагмент программы, заключенный в
строках βι — β7,Heo6xoAHMθ для всякой новой задачи
записывать заново. Эта работа аналогична составле­
нию системы уравнений (17,)∙ Все остальное
должно составить содержание головной программы.
Это:
1. Организация перебора всевозможных комби­
наций значений логических переменных.
2. Подпрограммы дляп, Λ. V. →^> *÷∙ ^.
120


3. Фрагмент ββ, ββ + 1, ββ + 2, βs + 3 вычисления
значения F.
4. Организация печати результата.
Организация перебора всевозможных комбина­
ций значений.логических переменных хорошо иллю­
стрируется следующей блок-схемой:
pp)-=o

b—------- --------------------P/2)-0

ΣΣE≡-------- - ----

P/3)*0

K^-------------------------------------PfaF=O

~F=-----------PfS):-0

F--F∣Pβj, P(2f, Pf3), P/4), PβJ)

По такому принципу составлялись все истинно­
стно-функциональные таблицы в этом параграфе
(для примера см. (12)). Теперь осталось свести
121


все сказанное воедино, обобщая его на произвольное
число используемых в задаче логических перемен­
ных. Понятие «произвольное», конечно, относи­
тельно. Оно ограничено в приведенном далее алго­
ритме длиной массивов P и S. Однако, заменяя
BcτpoκeDIMP (100), S (100) число 100, например,на
1000, мы можем эту грань при необходимости су­
щественно отодвинуть. Получим следующий алго­
ритм:
DIM P(100), S(100)
-----------------GOTO ω
aiZ: = l—X\RETURN
a2Z: = X*Y\RETURN
a3 Z: = X+Y-X*Y\RETURN
a4 Z: = l-X+X*Y\RETURN
a5 Z: = 1 - (X - Y) **2∖RETURN
----- ----- >- ω PRINT' введите количество логических пе­
ременных'

INPUT N
/:-0
---------- >- φ для / от / + 1 до N
нц
P P(/): = 0
КЦ

βo ^:=o
GOSUB F
β8 F: = 1
βo + 1 для T от 1 до К
нц
β8 + 2

ββ + 3

F: = F*S(T)

кц
ПЕЧАТЬ РЕЗУЛЬТАТА
для / от N до 1 шаг— 1
нц
если P(Γ) < 1

то P(Z): = P(^+1
---------------------- ---------- GOTO φ
все

кц
122


-----------------GOTOψ
ПОДПРОГРАММА F
-------------->- ψ END
Этому алгоритму отвечает следующая программа на
Бейсике:
10 DIM P(100), S(100)
20 GOTO 80
30 Z = 1 -X∖RETURN
40 Z = X*Y∖RETURN
50 Z = X÷Y-X*Y∖RETURN
60 Z=l-X⅛X*Y∖RETURN
70 Z = 1 - (X - Y) **2∖RETURN
80 PRINT' введите количество логических перемен­
ных N'
90 INPUT N
100 1 = 0
(19)
110 FOR J = I÷1 TO N
120 P(J) =0
130 NEXT J
140 K = 0∖GOSUB 300
150 F = I
160 FOR T = 1 ТО К
170 F = F∙S(T)
180 NEXT T
190 REM 200—230: печать результата
200 FOR I = 1 TO N
210 PRINT P(T);
220 NEXT T
230 PRINT'F = 'F
240 FOR I = N ТО 1 STEP — 1
250 IFP (I) > = 1 THEN 280
260 P(I)=P(I) + 1
270 GOTO 110
280 NEXT I
290 GOTO 5000
300 REM подпрограмма F
5000 END
Уточнения
1. В этой программе отсутствует подпрограмма
вычисления значений логических сомножителей в левой
части характеристического уравнения (18). Такая под­
программа составляется по условиям каждой конкрет­
ной задачи в отдельности и добавляется к программе
(19). Сделать это несложно. Нужно иметь две таблицы:
123


1) таблицу соответствия для переменных (1);
2) приведенную ниже таблицу соответствия для
адресов подпрограмм:
η

л

V

→-

→

зо

40

50

60

70

Таблица (20) стабильна. Таблица (1) составляется
по условиям каждой конкретной задачи в отдельности.
После этого составляется система логических урав­
нений (17'). С нее, с учетом таблиц (1) и (20), легко
списывается система строк (в нашем примере копи­
рующая βι — β?) искомой подпрограммы. Эта система
строк всегда начинается с номера 300 (так, что при
слиянии этой подпрограммы с головной программой
(19) в последней комментарий в строке 300 стирается),
а заканчивается оператором RETURN.

Вот что получим для данного примера:
300 X = P (1) ∖Y = P (5) ∖GΘSUB40∖X = Z∖Y = P (2)
301 GΘSUB60∖K = K+l∖S(K)=Z
310 X = P(5)∖GOSUB30∖Zl=Z∖X = P(3)∖GΘSUB30
311 X = P(2)∖Y = Z∖GOSUB40∖X = Zl∖Y = Z∖
GOSUB60
312K = K+l∖S(K)=Z
320 X = P (1) ∖Y = P (3) ∖GOSUB40∖X = Z∖GΘSUB30
321 K = K+l∖S(K) =Z
(21)
330 X = P(l)∖GOSUB30∖Zl=Z∖X = P(3)∖GΘSUB30
331 X = Z1 ∖Y = Z∖GΘSUB40∖X = Z∖GΘSUB30
332 K = K+l∖S(K) =z
340 X = P (4) ∖GOSUB30∖X = P (5) ∖Y = Z∖COSUB60
341 K = K÷l∖S(K) =Z
350 X = P (3) ∖GOSUB30∖X = Z∖Y = P (5) ∖GΘSUB60
351 Zl=Z∖X=P(2)∖GΘSUB = 30∖X = Z∖Y = Zl (21)
352 GΘSUB60∖K = K+l∖S (К) = Z
360 X = P (2) ∖GOSUB30∖X = Z∖Y = P (3) ∖GΘSUB40
361 Z1 = Z∖X = P (5) ∖GΘSUB30∖X = Z∖Y = P (4)
362 GΘSUB40∖X = Z1 ∖Y = Z∖GOSUB60∖K = К +1
363 S(K)=Z
370 RETURN
124


2. Программа (19)может быть записана однажды
на магнитной ленте или диске. Если ею необходимо
воспользоваться, ее надо загрузить в оперативную па­
мять микро-ЭВМ. Затем по условиям задачи (см. π. 1)
составить подпрограмму, аналогичную (21).
Помните: первая строка этой подпрограммы всегда
должна иметь номер 300; вся подпрограмма должна
укладываться в строках с 300 по 5000. Донабрав
с клавиатуры эту подпрограмму к программе (19),
можно запускать всю полученную таким образом про­
грамму на счет.
3. Строка программы с номером 210 имеет вид:
210 PRINT P (T);
Благодаря точке с запятой, завершающей эту строку,
все значения P(T) (T = 1, N) будут напечатаны одной
строкой, а не в столбец. Эта строка будет завершаться
значением F (см. оператор 230 PRINT'F = 'F). На­
пример, строка результата, соответствующая уже упо­
минавшейся комбинации
А

Б

В

Г

Д

0

1

1

0

1

будет выглядеть так:
01101 F=1.
Распечатав весь результат счета, выпишем только те
строки, которые завершаются равенством F = 1. На­
боры значений, предшествующие таким равенствам,
дадут искомый в задаче ответ.
Ответ: 01101 F = 1
11010F= 1
11000F=l
11001 F= 1.
Во всех остальных случаях F = 0.
Таким образом, друзья могли приходить четыре ве­
чера в таком составе:
1) Борис, Виктор и Дмитрий;
2) Андрей, Борис и Григорий;
3) Андрей и Борис;
4) Андрей, Борис и Дмитрий.
4. Выполните самостоятельно сформулированное в
задаче задание.
125


5. Приведем целиком всю соответствующую этому
примеру программу:
3 REM ГЛАВА 4/ ПАРАГРАФ 1
10 DIM P<lΘΘ)∕S<lΘΘ)
20 60 TO 8Θ
30 Z=l-X x RETURN
4Θ Z≈XW x RETURN
50 Z≈X+7-X*? x RETURN
60 Z=l-X÷X*V x RETURN
70 Z=i-<X-V>^2 x RETURN
80 PRINT 'ВВЕДИТЕ КОЛИЧЕСТВО ЛОГИЧЕСКИХ ΠEPEMEHHMXS N,'
90 INPUT N
100 1=8
110 FOR J=I+1 TO N
120 P<J)=0
130 NEXT J
140 K=θ x GOSUB 300
150 F=1
160 FOR T=1 ТО К
170 F=F⅛S<T)
180 NEXT T
190 REM 200 - 2305 ПЕЧАТЬ РЕЗУЛЬТАТА
200 FOR T≡1 TO N
210 PRINT P<T>;
220 NEXT T
230 PRINT 'F='F
240 FOR I=N ТО 1 STEP -1
250 IF P<I)>=1 THEN 280
260 P<I>≈P<I)+1
270 GO ТО 110
280 NEXT I
290 GO ТО 5000
300 X=P<1> x V≈P<5) x GOSUB 48 x X=Z x V≈P<2)
301 GOSUB 60 x K=K+1 x S(K)≈Z
302 K≈K+1 x S<K>=Z
310 X=P<5) x GOSUB 30 x Zl=Z x X=P<3) x GOSUB 30
311 X=P<2) x V=Z x GOSUB 40 x X≈Z1 x V,=Z x GOSUB 60
312 K=K+1 x S<K)≈Z
320X=P<1) x V=P<3) x GOSUB 40 x X=Z x 60SUB 3θ
321 K=K+1 x S<K>=Σ
322 K≈K+1 x SCK)=^
330 X=P<1) x GOSUB 30 x Zl=Z X X=P<3) x GOSUB 30
331 X=Z1 x V=Z X GOSUB 48 x »2 ∖ GOSUB 30
332 K=K+1 x S<K)=Z
340 X≈P<4) x GOSUB 30 x X=P(5> x V≈Z x GOSUB 60
341 K=K+1 x S<K)=Z
350 X=P<3> x GOSUB 30 x X≈Z x ,√=P(5) x GOSUB 60
351 Zi=Z x X=P<2> x GOSUB 30 x X=Z x 9=Z1
352 GOSUB 60 x K=K+1 x S<K)≈Z
360 X=P<2> x GOSUB 30 x X=Z x 7=P<3) X GOSUB 40
361 Zl≡Z x X≈P<5) x GOSUB 30 x X=Z x V=P<4)
362 GOSUB 40 x X=Z1 x Y=Z x GOSUB 60 x K=K+1
363 S<K)≈Z
370 RETURN
5000 END

В заключение сделаем еще одно важное примечание относительно составления системлогическихуравнений (17) и (17,).
126


Примечание. Обратимся к условию 3) задачи. Рас­
суждая непосредственно по тексту этого условия,
заменим его системой двух логических уравнений:
fAΛB = 0,
∏AΛ^B = 0,

которую впоследствии заменим эквивалентной ей си­
стемой
p(AΛB) = l,
1 η∏AΛ∏B) = l.

Последняя система эквивалентна одному логическому
уравнению
Π(AΛB)Λ∏(∏AΛ^B) = 1.

(Проверьте себя и, не заглядывая назад, ответьте: по­
чему?) Однако, в случае условия 3) можно было
рассуждать иначе (и возможно кто-то так и рассуждал)
и заменить его одним логическим уравнением
A^∏B = 1.

Не вызывает ли противоречий такая ситуация? Нет.
Если всякий раз вы рассуждали правильно, то убе­
диться в этом можно, построив следующую таблицу
истинности (в ней два последних столбца тождест­
венны) :
А

В

A÷÷∏B

η(AAB)Λ∏(ηAΛ∏B)

1
0
1
0

1
1
0
0

0
1
1
0

0
1
1
0

2. Повторим кратко схему, изложенную в π. 1

Для этого решим еще одну задачу.
Автоматизированный участок ([12], с. 76, задача 9).
На автоматизированном участке цеха стоят 5 стан­
ков, действия которых скоординированы следующим
образом.
Если работают первый и третий станки, то чет­
вертый не работает при условии, если подключен пятый
станок. Если же первый станок подключен без третьего
или выключен пятый станок, то четвертый обязательно
127


подключен. Если пятый станок работает вместе со вто­
рым при выключенном первом станке, то включен
третий станок. Если выключены второй или пятый
станки, то одновременно выключен и четвертый.
1. Мы наблюдаем работу первого и четвертого
станков. Что можно сказать о состоянии остальных
станков, скрытых за перегородкой?
2. Можно ли в данной системе остановить для
ремонта одновременно третий и четвертый станки,
оставив хотя бы один из остальных станков вклю­
ченным?
Пусть P — множество станков, которые стоят на
автоматизированном участке цеха:
P = {P(7)∣∕∈Γ5}.

При таком обозначении отпадает необходимость в таб­
лице (1) из π. 1 (ведь станки не имеют персональных
имен, их можно просто пронумеровать). Удобно сле­
дующее соглашение:

P{I} = «Станок P(/) включен».
Примемся сразу же за составление системы логи­
ческих уравнений (по типу системы (17) из π. 1), опи­
сывающих условие задачи.

P(1)AP(3)→(P(5)→ΠP(4))=1,
P(i) Л ∏P(3) V WW(4) = 1,
n7А
P(5)ΛP(2) Л ∏P(l)→P(3) = I,
(17)
lP(2)V^(5)→lP(4)=l.
Напоминаем, что, составляя (и читая) эти уравне­
ния, нужно постоянно учитывать силу связок, в согласии
с убыванием которой связки упорядочиваются так:

Д Л, v, →, ÷>Так как в правых частях этих уравнений стоят
только единицы (в противном случае нужно было бы
к такому виду системы перейти — см. в π. 1 переход от
системы (17) к системе (17z)), мы можем сразу при­
ступать к составлению подпрограммы F. Для этого
нужно иметь перед глазами таблицу (20) из π. 1, отра­
жающую соответствие между именами стандартных
подпрограмм и их адресами в головной программе.
Для удобства пополним таблицу (20) сведениями о
входных и выходных параметрах стандартных под­
программ.
128


∏

Л

у

→

^

30

40

50

60

70

Входные
параметры

∏x

XΛY

xyγ

X→Y

X++Y

Выходной
параметр

z

z

z

z

z

(20)

Подпрограмму начинают строкой с номером 300.
Учитывая силу связок и таблицу (20), преобразуем си­
стему (17) в искомую подпрограмму F.
Слив эту программу с головной программой (19)
(из π. 1), получаем программу для решения задачи
об автоматизированном участке.

3. Игра Фомина

Применение ЭВМв сфере обучения дает большие
возможности для использования игровой компоненты.
Сказанное относится, естественно, и к области изучения
самих основ алгоритмизации и программирования. По­
нятие алгоритма близко понятию правил игры,и поэтому
программирование игр позволяет в наиболее доступной
форме усваивать практические навыки программирова­
ния вообще.
Существует достаточное количество источников, из
которых можно почерпнуть массу интересных игр, на­
пример [15], [16]. В качестве примера мы разберем
в этом параграфе игру Фомина [15]. Подозреваем, что
у читателя может возникнуть неудовлетворенность в
способе подачи информации на экране дисплея. Но
мы не задаемся здесь целью достичь максимальных
удобств, так как это жестко ориентировало бы нас
на определенную инструментальную базу и, возможно,
повлекло бы привлечение средств, выходящих за рамки
Бейсика. С другой стороны, это увлекло бы нас в сто­
рону от основной темы. Поэтому читателю, у которого
такая неудовлетворенность возникнет, мы советуем:
изучите возможности вашей ЭВМ и поправьте дело;
от этого выиграет игра, выиграете и вы.
Игра Фомина — это игра Фомина-2 ([15], с. 11,
усложненный вариант предшествующей ей игры Фо­
мина-1). Вот ее условие.
129


К началу игры имеется К групп предметов. Пер­
вая группа содержит N(1) предметов, вторая — ^(2)
предметов, третья — Λr(3), ..., ^-я группа — N(K)
предметов.
Играют двое. Ход любого из них состоит в раз­
дроблении каждой группы, состоящей более, чем из
одного предмета, на две меньшие группы. Ходы вы­
полняются до тех пор, пока во всех группах не оста­
нется по одному предмету.
Победителем считается тот, кому удалось выпол­
нить последнее разбиение.
Эта игра имеет беспроигрышный алгоритм, отра­
женный в следующей блок-схеме [15]:

Основная идея алгоритма состоит в том, чтобы ста­
вить все время соперника перед необходимостью разби­
вать группы, среди которых наибольшая содержит
2n — 1 предметов.
Оказывается, что при таком стечении обстоятельств
ваш соперник будет всегда находиться в положении,
когда:
130


1. Окончить очередным ходом игру нельзя (если вы
ее не окончили своим ходом, то в большей группе
больше одного предмета — 2n-l ≠ 1, τ. e. n ^ 1), так
как при разбиении группы из 2rt- 1 (n ≠ 1) предметов
на две в одной из, частей обязательно будет больше
одного предмета.
v
2. Разбивая наибольшую из групп, если в неи 2 — 1
предметов, на две, ваш соперник не сможет получить
в большей из частей разбиения такого количества пред­
метов, которое выражалось бы числом вида 2n — 1,
а разбивая каждую из оставшихся групп на две,
он не сможет ни в одной из частей деления полу­
чить такое количество предметов, которое выража­
лось бы числом вида 2n — 1 и в то же время превы­
сило бы большую из частей деления наибольшей
группы.
Возьмите, например, две группы из 7 и 6 предметов
(7 = 23 — 1) и попробуйте их разными способами делить
на две части каждую. Вы не добьетесь, чтобы в большей
из частей деления число предметов выражалось числом
вида 2Л — 1.
Обратно, делая ответный ход, вы всегда сумеете
поставить соперника в исходную ситуацию.
Описанный факт устанавливается в [15] методом
математической индукции.
Программируя эту игру для ЭВМ, поставим себя на
место машины, а соперника будем называть игроком.
Далее изменим алгоритм игры так, чтобы машина 1)
предоставляла возможность выбора первого хода игро­
ку и 2) во время игры пристально следила за игроком
до тех пор, пока тот не допустит отклонение от выигрыш­
ного алгоритма (неверный ход), а затем бы перехваты­
вала выигрышную стратегию игры. Позаботимся также
и о том, чтобы, когда игрок действует согласно выигрыш­
ному алгоритму (а такое может оказаться случайным),
машина полностью имитировала бы процесс вполне
осмысленной игры и тем самым никоим образом не
указывала бы своим поведением игроку на тот факт,
что у него очередной ход был удачным (что могло быть,
повторяем, делом случая), τ. e. скрывала бы свое «на­
строение».
В самом общем виде алгоритм для ЭВМ можно
представить так:

131


А л r6 p и τ м

ИМЯ: игра Фомина

Объявить массивы, необходимые для ведения
игры: N — массив для запоминания
групп предметов, U и V — массивы,
в которых запоминаются части произво­
димых разбиений.
Напечатать условия игры.
Дать игроку возможность выбрать начальные
условия игры: количество групп ^ и κδличество предметов в каждой группе ^(/).
Предоставить возможность выбора первого
хода игроку.
1 Описать игровую ситуацию (количество групп
и количество предметов в каждой груп­
пе).
Ход игрока
А: = 0 — признак хода игрока.
Проверить корректность хода.
2 Зафиксировать изменение массива N
после хода.
1 Описать игровую ситуацию
Проверить условия завершения игры: либо
перейти к окончанию, либо дать ход
машине.
Ход машины
А: = 1 — признак хода машины.
Поиск максимального элемента M в мас­
сиве N.
Вычислить наименьшее T = 2", превосхо­
дящее либо равное M
T: = T-1.
Произвести ход:
1) либо имитировать ход (если
M = T),
2) либо ход расчетливый — по вы­
игрышному
алгоритму
(если
M≠T).
2 Зафиксировать изменение массива N
после хода.
1 Описать игровую ситуацию.
Проверить условия завершения игры: либо
перейти к окончанию, либо дать ход
игроку.
Блок окончания игры:

1) по признаку (Д =0 или А = 1)объявить выигрыш (игрока или машины),
2) по желанию игрока возобновить или
завершить игру.

132

Строки
программы

5
10—60

70—200
210—490

500—550

560; 1630—1780

570—840
580
680—830
840; 1380—1570
850; 1630—1780
860—890

900—1270
910
920—990
1000—1030

1040
1050
1060—1115

1120—1270
1110; 1270
1380—1570
1280; 1630—1780
1290—1320

1830—1930


Пронумеровав одинаковые части алгоритма, мы ви­
дим, что естественно было бы выделить некоторые из
них в качестве подпрограмм. Их первоначально оказа­
лось две. Кроме того, забегая вперед, отметим, что
удобно будет выделить еще две подпрограммы.
3. Подпрограмму, производящую произвольное раз­
биение одной группы — шаг произвольного разбиения
(1330—1370).
4. Подпрограмму печати (обозначим ее буквой ε) —
для печати игровой ситуации (1580—1620).
Справа вдоль записи алгоритма указаны номера
строк программы, в которых описана каждая отдельно
вынесенная здесь макрокоманда. Это нужно по двум
причинам:
1) для удобства чтения программы;
2) как выяснится позже, некоторые команды не
будут дополнительно разъясняться и детализироваться
(это, как правило, команды печати условий или про­
верки корректности отдельных действий) — они, на наш
взгляд, понятны при непосредственном чтении на Бей­
сике.
Длины одномерных массивов ^, U и V ограничим
числом 100, а в условии задачи потребуем, чтобы общее
число предметов во всех группах не превосходило число
100. Покажем на примере, как используются массивы
Nt U и V. Допустим, что изначально имелись три
группы: ^(l) = 7, ^(2)=l и ^(3) = 6. Следовательно,
^(4) = ^(5) = ... = ^(100) = 0. Пусть
далее
ходит
игрок. Как зафиксировать его ход? Укажем ему, что
вначале он должен определить разбиение первой груп­
пы. Для этого на экран выведем:
L=1
Введите U (1), V (1)
?
Пусть, например, последовал ввод пары чисел: 3, 4.
Тогда выведем на экран:
L=3
Введите U (3), V (3)
?
Допустим, игрок ввел: 3, 3.
Случай L = 2 был пропущен, так как во второй
группе лишь один предмет и она не подлежит делению.
Теперь вместо ряда
^l) = 7, ВД=1, ВД = 6
(1)
133


мы имеем ряд
t/(i)=3, v(i)=4,

щз)=з,

ад=1,

v(3)=3.

Его необходимо переписать так:
^l) = 3, W(2) = 4, ^3)≈1, ^4) = 3,
z9x
ад=з.
w
Эта перезапись осуществляется подпрограммой 2
(фрагмент 1380—1570), фиксирующей изменение мас­
сива N после хода. Приведем соответствующий ей
алгоритм и объясним его работу на примере.
пока ^(^≠0
нц
если ^(/) ≠ 1
τoN(ty≈U(Γ)
для J от К + 1 до / + 2 шаг—1
нц
(3)
N(J): = N(J-l)
U(J): = U(J - 1)
V(Z): = V(J-1)
кц
N(I+l)-.≈V(I)
t/(/+l): = 0
V(/+l): = 0
K: = K+1
Γ. = I+∖
все
/:=/+1
кц
Каким образом с помощью этого алгоритма осу­
ществляется после хода переход от ряда (1) (K = 3)
к ряду (2) (К = 5) ? Выпишем состояние массивов N,
U и V, соответствующее ряду (1) после хода:

K=3

134

^

и

V

1
2
3

7
1
6

3
0
3

4
0
3

4
5

0
0

0
0

0
0


Далее исполнение алгоритма (3) можно разбить на
три этапа, которым соответствуют следующие состояния
массивов N, U и V:

пока Λ^(∕)≠0
нц
кц
Ясно, что после завершения процедуры перехода от
(1) к (2) состояния массивов U и V нужно изменить
на начальные (заполнить массивы нулями) — фрагмент
программы 1530—1560.
Подпрограмма 4 вызывается лишь из подпрограм­
мы 1. Просмотрев внимательно подпрограмму 1, вы уви­
дите, что печать групп осуществляется в ней блоками —
по 20 групп в каждом (если такие имеются) и не более
20 в последнем.
Проста, наконец, и подпрограмма 3 — шаг произ­
вольного разбиения (короче — имитация шага).
1330 REM ИМИТАЦИЯ ШАГА
1340 RANDOMIZE
135


1350 U(I) =INT((N(I)-1)*RND + 1)
1360 V(I)=N(I)-^(I)
1370 RETURN
Оператор RANDOMIZE помещается перед первым
использованием функции случайных чисел (функция
RND) в программе. При выполнении функции RND опе­
ратор RANDOMIZE изменяет начальное значение
случайного числа таким образом, что та же самая про­
грамма, выполняемая второй раз, дает другие резуль­
таты. Далее, выражение (M(7)-1)*RND + 1 использу­
ется для генерации случайного числа в открытом
интервале (1, M(7)). Затем переменной U(Γ) присваи­
вается целая часть этого числа, a V(7): = A(7)-U(/).
Опишем, наконец, алгоритм осуществления хода
ЭВМ (фрагмент 900—1270). Во всем остальном чита­
тель легко разберется, сравнивая общее описание про­
граммы в целом и некоторых выделенных нами ее частей
с приведенным далее текстом программы.
Ал гоp иτ м

А: = 1

Комментарии

Признак хода
ЭВМ

Af: = A(l)
если К φ 1
то /: — 2
пока I ≤ К
нц
если Λf < N(Γ)
|
τoM: = ^(7)

Поиск макси­
мального эле­
мента M в мас­
сиве N

все
кц
все
T: = 1
пока T<M
нц
P T∖ = T*2

кц
Λ = 7,-1
если M = T
то для / от 1 до А

136

Вычисление ,
наименьшего
T = 2n,
пре­
восходящего
либо
равно­
го M

T: = 2"-l

ИМИТАЦИЯ
; ХОДА ЭВМ7


Комментарии

Ал го p итм

нц

если N(I) ≠ 1
|
то подпрограмма: имитация шага
все
кц

иначе T: = (T + l)/2-l

если T = 0
|
то T: = 1
все
Я: = 0
для / от 1 до К

*
(см.
меч.)

при-

** (см.
меч.)

при-

*** (см. примеч.)

нц
если ^(/) ≠ 1
то если ^(/) ≠ M
то подпрограмма: имитация
шага
иначе если R = 0
го R = 1
U(I)=T
Vy) = N(I) — T
iиначе подпро­
грамма:
—* α имитация
шага
если U(/) > T
Ч.^ " _"" II —
1 тл
IV гуVΛ

‰^ ...

IV* (см. примеч.)

РАСЧЕТЛИ­
ВЫЙ ХОД
ЭВМ

все
если V(/)> 7
II
тл
ы
lv ЧА»

все
все

все
все
кц
все

Примечание. Если M^T (T = 2n—1, где и —
фиксированное неотрицательное число, такое, что
2rt"1<M≤2n), то ЭВМ должна действовать по вы­
игрышному алгоритму. Для этого любая группа, не
137


являющаяся максимальной и одноэлементной, разбива­
ется на две части произвольно. Пусть теперь ЭВМ нахо­
дит первую максимальную группу. (Таких групп может
быть несколько, например, в ряду ^(l) = 9, Λf(2) = 6
Λf(3) = 9, ^(4) = 7 их две: N(l) и ^(3).) Тогда эту
группу она должна разбить на две, причем так,
чтобы в одной из частей разбиения было ровно 2n~l
предметов.
*) Легко видеть, что если M ≠ 2, то при выполне­
нии оператора T: = (7, + l)/2-1 мы получаем тре­
буемое: Γ = 2"-1-l.
κ
з^Если же, в частности, Λf = 2, то n = 0 иГ =
= 2"
1 = 0. Но группу из двух предметов можно
поделить только на две одноэлементные группы. По­
этому для этого исключительного случая предусмотре­
на развилка

если T = 0
то T: = 1
все

Если каждую из максимальных групп разбивать так
же,как и первую, то наблюдательный игрок это заметит
и получит подсказку к разгадке алгоритма выигрышной
игры. Поэтому мы решили каждую последующую мак­
симальную группу разбивать произвольно, но следить
лишь за тем, чтобы ни одна из полученных частей
разбиения не превосходила число T≈2n~l~l, так как
по выигрышному алгоритму соперник должен получить
такой набор групп, среди которых в максимальной
2n — 1 элементов. С этой целью в алгоритме преду­
смотрен переключатель R и встроены два цикла α.
***) Пока R = 0 — максимальные группы не встре­
чались.
При первой встрече с максимальной группой раз­
биваем ее нужным образом.
IV*) R присваиваем значение 1. По этому признаку
при всякой новой встрече с максимальной группой ЭВМ
будет имитировать некоторые произвольные разбиения.
Программа игры Фомина на Бейсике
3 REM ГЛАВА 4,ΠAPAΓPAΦ 3
5 PRINT 'ИГРА ФОМИНА3
10 DIM N<lΘlMJ<101>,U<101>
20 FOR 1=1 ТО 101
30 N<D=0
40 ∪<I>=Θ

138


50 U<D=O
60 NEXT I
78 PRINT ' К НАЧАЛУ ИГРЫ ИМЕЕТСЯ К ГРУПП ПРЕДМЕТОВ/'
80 PRINT 3 ОБЩЕЕ КОЛИЧЕСТВО КОТОРЫХ НЕ ДОЛЖНО БЫТЬ БОЛЬШЕ 10θ.∙,
90 PRINT ' ВЫ ИГРАЕТЕ СО МНОЙ'
100 PRINT •’ХОДИМ ПО ОЧЕРЕДИ'
110 PRINT 'ХОД СОСТОИТ В РАЗДРОБЛЕНИИ КАЖДОЙ ГРУППЫ/'
120 PRINT 'СОСТОЯЩЕЙ БОЛЕЕ ЧЕМ ИЗ ОДНОГО ПРЕДМЕТА/'
130 PRINT 'НА ДВЕ МЕНЬШИЕ ГРУППЫ.'
140 PRINT 'ХОДЫ ВЫПОЛНЯЮТСЯ ДО ТЕХ ПОР/ '
150 PRINT 'ПОКА ВО ВСЁХ ГРУППАХ НЕ ОСТАНЕТСЯ'
160 PRINT 'ПО ОДНОМУ ПРЕДМЕТУ.'

170 PRINT 'ПОБЕДИТЕЛЕМ СЧИТАЕТСЯ TOT/'
180 PRINT 'КОМУ УДАЛОСЬ ВЫПОЛНИТЬ ПОСЛЕДНЕЕ РАЗБИЕНИЕ.'
190 PRINT 'ДЛЯ ПРОДОЛЖЕНИЯ ВВЕДИТЕ ЛЮБОЕ ЧИСЛО'
200 INPUT С
210 PRINT 'УКАЖИТЕ ЧИСЛО ГРУПП К'
220 INPUT К
230 IF K<=0 THEN 260
240 IF K>=1Θ0 THEN 260
250 IF K=INT<K) THEN 300
260 PRINT 'ВЫ ОШИБАЕТЕСЬ ПРИ ВВОДЕ Ks'
270 PRINT 'K='K
280 PRINT 'ПОВТОРИТЕ ВВОД'
290 GO ТО 210
300 PRINT 'УКАЖИТЕ ЧИСЛО ПРЕДМЕТОВ N<I> В КАЖДОЙ ГРУППЕ'
310 PRINT 'ОБЩЕЕ КОЛИЧЕСТВО ПРЕДМЕТОВ НЕ ДОЛЖНО БЫТЬ > 100'
320 FOR 1=1 ТО К
330 INPUT NCI)
340 IF N<I><=0 THEN 360
350 IF N<I>=INT<N<I>> THEN 398
360 PRINT 'ОШИБАЕТЕСЬ: NCΓ)='N<I>
370 PRINT 'ПОВТОРИТЕ ВВОД N<'I'>'
380 GO ТО 330
390 NEXT I
400 S=0
410 FOR 1=1 ТО К
420 S≡S+N<I)
430 NEXT I
440 IF S<=100 THEN 500
450 PRINT 'ОБЩАЯ СУММА ПРЕДМЕТОВ У ВАС'
460 PRINT 'ПРЕВЫСИЛА ЧИСЛО 100'
470 PRINT 'S≈'S
480 PRINT 'ПОВТОРИМ ВВОД"
490 GO ТО 300
500 PRINT 'РЕШИТЕ САМИ/ КОМУ ИЗ НАС'
510 PRINT 'СДЕЛАТЬ ПЕРВЫЙ ХОД'
520 PRINT 'ЕСЛИ ВАМ/ ВВЕДИТЕ ЧИСЛО 8/'
530 PRINT ''ЕСЛИ МНЕ - ЛЮБОЕ ОТЛИЧНОЕ ОТ 0 ЧИСЛО'
540 INPUT А
550 IF A<>0 THEN 900
560 GOSUB 1630
570 REM ХОД СОПЕРНИКА
580 A=0
590 PRINT 'ВАШ ХОД'
600 PRINT 'ВВОДИТЕ ПОСЛЕДОВАТЕЛЬНО ПАРЫ ЧИСЕЛ/'
610 PRINT 'УКАЗЫВАЮЩИЕ ВЕЛИЧИНУ ЧАСТЕ.й/'
620 PRINT 'НА КОТОРЫЕ ВЫ РАЗБИВАЕТЕ УКАЗАННУЮ ГРУППУ L'
630 FOR L=1 ТО К
640 IF N<L>≈1 THEN 830
650 PRINT 'L = 'L
660 PRINT 'ВВЕДИТЕ U<'L')∕U<'L')'
670 INPUT U(L)/U(L)
680 REM ПРОВЕРКА КОРРЕКТНОСТИ ХОДА
690 IF U<L)<≈Θ THEN 780

139


788
710
720
730
740
750
760
770
780
790
800
810
815
820
838
848
850

S≈TNT<U<L>>
IF S<>U(L) THEN 800
IF U(L)<≈Θ THEN 780
S≡INT<U<L)>
IF S<>U<L) THEN 800
IF U<L)+U<L>=N<L> THEN 838
PRINT 'U<'L')+UCL'X>N<'L')'
GO TO 810
PRINT 'ОТРИЦАТЕЛЬНОЕ ЧИСЛО!'
GO TO 810
PRINT 'ДРОБНОЕ ЧИСЛО!'
PRINT 'ПОВТОРИТЕ ВВОД'
№ив \^V?TBB4AtTE НА Cn№IWWM Г P 0 В X Ю С И T X А Ц И Ю
GOTO 6⅛^
NEXT L
GOSUB 1380
GOSUB 1630

860 FOR 1=1 ТО К
870 IF N<I)<>1 THEN 300
880 NEXT I
890 60 ТО 1830
300 КЕМ ХОД МАШИНЫ
910 A=1
915 PRINT 'МОЙ ХОД'
920 M=N<1)
930 IF K=1 THEN 1000
940 1=2
950 IF I>K THEN 1000
960 IF M>=N<I) THEN 980
970 M=N<I)
980 I=I+1
990 60 ТО 950
1000 T=1
1010 IF T>=M THEN 1040
1020 T=T*2
1030 GO ТО 1010
1040 T=T-1
1050 IF M<>T THEN 1120
1060 REM ИМИТАЦИЯ ХОДА
1070 FOR 1=1 ТО К
1080 IF N<I)=1 THEN 1100
1090 GOSUB 1330
1100 NEXT I
1110 GOSUB 1380
1115 GO ТО 1280
1120 REM РАСЧЕТЛИВЫЙ ХОД
1130 T=<T+l>z2-l
1135 IF τ=0 THEN T=1
1140 R=0
1150 FOR 1=1 ТО К
1160 IF N<Γ)=1 tHEN 1260
1170 IF N(I)=M THEN 1190
1180 GOSUB 1330
1185 GO ТО 1260
1190 IF R<>0 THEN 1230
1200 R=1
1210 U(I>=T
1220 U<I)=N<I)-T
1225 GO ТО 1260
1230 GOSUB 1330
1240 IF U<I)>T THEN 1230
1250 IF U<I)>T THEN 1230
1260 NEXT I

140


127Θ GOSUB 1380
1280 GOSUB 1630
1290 FOR 1=1 TO K
1300 IF N<I)<>1 THEN 570
1310 NEXT I
1320 GO TO 1830
1⅛ РЕМИМИТАНИЯ^АГА
1340 RANDOMIZE
.
17.5A ll<I)≈INT( <N<I>-l>≡RND+1)
1360 U<I)=N<D~U<I)
1370 RETURN
13R0 REM ИЗМЕНЕНИЕ МАССИВА M
1385 1=1
139A IF N<I)≈Θ THEN 1530
1400 IF N<D≈1 THEN 1510
1410 N<D=U<D
_ <
1420 FOR J=K+1 TO 1+2 ⅛TEP ~1

1430
1440
1450
1460
1470
1480
1490
1500

N<J)=NGJ-1)
U(J)=U<J-1>
U<J)=M<J-1>
NEXT J
N<I + l)=U<D
U<I + D=0 × U<I+1)≈0
K≈K+1
I≈I+1

1510 I=I+1
1520 GO ТО 1390
1530 FOR 1=1 ТО 100
1540 U<I)=0
1550 OCI>=Θ
1560 NEXT I
1570 RETURN
1580 REM ЭПСИЛОН
1590 FOR I=J TO S
1600 PRINT 'N<'I')='N<I>';
1610 NEXT I
1615 PRINT
1620 RETURN
С И T У A
1630 PRINT ' И Г P 0 В А Я
1640 J=1
1650
1660 IF S>=K THEN 1730
1670 GOSUB 1580
1680 J≈S+1
1690 S=S+20
1700 PRINT 'ДЛЯ ПРОДОЛЖЕНИЯ ВВЕДИТЕ ЛЮБОЕ ЧИСЛО
1710 INPUT С∣
1720 GO ТО 1660
1730 S=K
1740 GOSUB 1580
1750 PRINT 'ДЛЯ ПРОДОЛЖЕНИЯ ИГРЫ
1760 PRINT 'ВВЕДИТЕ ЛЮБОЕ ЧИСЛО'
1770 INPUT С
1780 RETURN
1830 REM ОКОНЧАНИЕ
1840 IF A=0 THEN 1870
1850 PRINT 'ВЫ ПРОИГРАЛИ'
1860 GO TO 1880
1870 PRINT 'ВЫ ВЫИГРАЛИ'
1888 PRINT ХОТИТЕ ЛИ ВЫ ПОВТОРИТЬ ИГРУ?
_.
1890 PRINT ЕСЛИ ДАл ВВЕДИТЕ. ЧИСЛО 0л'
1900 PRINT ЕСЛИ НЕТ - ЛЮБОЕ ОТЛИЧНОЕ ОТ 0 ЧИСЛО
1910 INPUT В
1920 IF B=0 THEN 5
1930 END

U

И

Я'

141


Примечание. В этом параграфе мы рассматривали
программирование игр как занятие, прежде всего полез­
ное для усвоения практических навыков программи­
рования. Этот тезис оправдывается тем, что: 1) программировать игры интересно и 2) понятие алгоритма
близко понятию правил игры. В качестве примера нами
была рассмотрена игра Фомина, беспроигрышный алго­
ритм для которой известен [15]. Таким образом, мы
не утруждали себя поиском выигрышной игровой стра­
тегии в этой игре. Тем самым (намеренно) мы опустили
очень важный аспект процесса алгоритмизации при
программировании игр. Нас сдерживало несколько об­
стоятельств — это и ограниченный объем книги, и нали­
чие доступных пониманию широкого круга читателей
источников, где этот вопрос изучается отдельно и на
большом количестве примеров, и нежелание размывать
основную канву повествования, положенную в книгу в
целом. Однако сейчас, дописывая последние строки, мы,
очевидно, обязаны отметить этот факт и, более того,
указать читателю на важность и перспективу ма­
тематического программирования игровых ситуаций.
К настоящему времени теория игр выросла в самостоятельное научное направление, обнаружились ее
связи с теорией вероятностей, теорией графов, τeopeтическим программированием. Первые работы по теории игр принадлежат Цермело (1871—1953, немецкий
математик) и Борелю (1871 —1956, французский
математик) и относятся к началу XX века. В 1928 году
фон Нейман (1903—1957, американский математик)
доказал основную теорему теории игр (теорему о минимаксе). А появление и широкое распространение
быстродействующих электронных вычислительных машин, обеспечивающих возможность эффективного решения громоздких игровых задач, привлекло к теории
игр внимание широкого круга специалистов.
Теория игр представляет собой совокупность мате­
матических методов анализа и оценки конфликт­
ных ситуаций. Поэтому она находит широкое примене­
ние как к планированию военных операций и управ­
лению военной техникой, так и к самым разнообраз­
ным задачам планирования народного хозяйства и
управления производством, к анализу различных эконо­
мических и социальных явлений. Естественно также, что
общая теория игр проливает свет и на процесс алго­
ритмизации решения занимательных игровых, задач.
142

⅛

1
I
|
»;
l'
^
⅛
j
i
]
?
⅛


ЛИТЕРАТУРА
1. Дьяконов В. ∏. Справочник по расчетам на микрокаль­
куляторе.— M., 1985.— 224 с.
2. Дьюдени Г. Э. 520 головоломок.- M., 1975.—344 с.
3. Брудно А. Л., Каплан Л. И. Олимпиады по программиро­
ванию для школьников.— M., 1985.— 96 с.
4. Кибернетика. Микрокалькуляторы в играх и задачах.—
M., 1986.— 160 с.
5. Данилов И. Д. Секреты программируемого микрокалькуля­
тора.— M., 1986.—160 с.
6. Трохоменко Я. K., Любич Φ. Микрокалькулятор, ваш ход! —
M., 1985.—224 с.
7. Основы информатики и вычислительной техники. Пробное
учебное пособие для средних учебных заведений: В 2 ч./Ершов A. ∏.,
Монахов В. M., Кузнецов A. A., Гольц Я. Э., Лапчик M. ∏., Лескневский A. C., Первин Ю. A., Смекалин Д. O.; Под ред. A. ∏. Ершова
и В. M. Монахова.
8. Серпинский В. В. 250 задач по элементарной теории чисел.—
M., 1968.—160 с.
9. Изучение основ информатики и вычислительной техники:
Метод, пособие для учителей и преподавателей сред. учеб, за­
ведений: В 2 ч./Ершов A. ∏., Монахов В. M., Витиньш M. B.,
Гольц Я. Э., Икауниекс Э. A., Кузнецов A. A., Лапчик M. ∏., Лесневский A. C., Павлов С. И., Первин Ю. A., Смекалин Д. O., Фрейвалд P. B.; Под ред. A. ∏. Ершова и В. M. Монахова. Ч. 2.— M.,
1986.— 207 с.
10. Алгебра: Учеб, пособие для 7 кл. сред. шк./Макарычев Ю. H.,
Миндюк H. Γ., Муравин K∙ C., Суворова С. Б.; Под ред. А. И. Maρκyшевича.— M., 1982.—254 с.
11. Кетков Ю. Л. Программирование на Бейсике.— M., 1978.—
158 с.
12. Шапиро С, И. Решение логических и игровых задач (логико-психологические этюды).— M., 1984.— 152 с.
13. Шапиро С. И. Решение логических задач на ЭВМ. Курск,
1977.—44 с.
14. Касаткин В. H. Логическое программирование в занима­
тельных задачах.— Киев., 1980.— 80 с.
15. Касаткин В. H., Владыкина Л. И. Алгоритмы и игры.— Киев,
1984.—80 с.
16. Веселая 3. Игра принимает всех.— Мн., 1985.—176 с.
17. Романовский T. Б. Микрокалькуляторы в рассказах и играх.—
Мн., 1987.— 192 с.
18. Перегудов M. A., Халамайзер А. Я. Бок о бок с компьютером.— М., 1987.— 192 с.
19. Блох А. Ш., Павловский А. И., Пенкрат В. В. Микрокаль­
куляторы в школе: Пособие для учителя.— Мн., 1986.—100 с.
20. Пухначев Ю. B., Данилов И. Д. Микрокалькуляторы для
всех.— M., 1986.— 192 с.
21. Дьяконов В. ∏. Справочник по алгоритмам и программам
на языке Бейсик для персональных ЭВМ.— M., 1987.— 239 с.
22. Бойко А. Б. Игры С микрокалькулятором.— M., 1987.— 48 с.
23. Программирование на языке БЕЙСИК-плюс для CM-4/Ceмик В. ∏., Монцибович Б. P., Непочатых Д. ∏. и др.-M., 1982.—
245 с.


ОГЛАВЛЕНИЕ
Предисловие.........................................................................................................

d

Г л а в а 1. Как разделить с остатком
1.
2.
3.
4.
5.
6.
7.
8.
9.

Какую задачу мы будемрешать.................................................................... 5
Велико ли число 219δ7.............................................................................................. θ
Гипотеза, высказаннаяалгоритмом............................................................. 8
От алгоритма к программе, а от нее к проверке гипотезы 10
Вопросов стало еще больше, или Новая гипотеза
1Л
16
Две задачи, имеющие одно и то же решение .
17
Алгоритм, который решает задачу..............................
19
Когда полезно усложнить алгоритм..............................
24
Для микро-ЭВМ нет проблем............................................

Г л а в а 2. Головоломки Генри Дьюдени
1.
2.
3.
4.
5.

О чем эта глава ..........................................................................
Три различные цифры...........................................................
Цифры и кубы.................................................................................
Особое число.......................................................................................................
Извлечение корня................................................................................................

Г л а в а 3. Учение с увлечением
1. Только ли игры.......................................................................................
•
2. О задачах школьного курса информатики, или Когда
сделаны уроки ................................................................................................
3. Можно ли играть в школьную теорему.....................................

Г л а в а 4. Игра и логика
1. Решение логических задач методом характеристических
уравнений..............................................................................................................
2. Повторим кратко схему, изложенную в π. 1..............................
3. Игра Фомина.......................................................................................................
Литература.........................................................................................................................................

108
127
129
143

Учебное издание

Бейда Анатолий Алексеевич
Королев Сергей Арсеньевич
ИГРОВЫЕ ЗАДАЧИ И ЭВМ
Книга для учащихся
Зав. редакцией Б. А. Кимбар. Редактор Г. И. Бондаренко.
Мл. редактор Л. H. Я с н и ц к а я. Обложка художника А. А. Ь oгуша. Художественный редактор Г. И. Красинский. Техни­
ческий редактор M. P. К а л и б e p о в а. Корректор 3. H. Г p и ш e л и.
ИБ № 2953
Сдано в набор 26.06.89. Подписано в печать 09.10.90. Формат 84Х1087з2.Бумага
тип. № 1. Гарнитура литературная. Высокая печать с ФПФ.Усл. печ. л. 7,&6. Усл.
κρ.-oττ. 7,98. Уч.-изд. л. 6,43. Тираж 25 000 экз. Заказ 2740. Цена 1 p.
Издательство «Народная асвета» Государственного комитета БССР по печати. 220600,
Минск, проспект Машерова, 11. Минский ордена Трудового Красного Знамени полиграфкомбинат MΠΠO им. Я. Коласа. 220005, Минск, Красная, 23.

144