Алгоритмическая игра
Здесь алгоритм - не средство, а объект игры.
ПРАВИЛА. Два участника игры (A и B) должны написать программу на
BASIC (можно и на другом языке) из N пронумерованных строк, причем N -
четное.
В распоряжении итграющих по одной булевой переменной A и B; обе в
начале игры равны логическому нулю (FALSE).
Играющие поочередно каждым своим ходом должны заполнить любую
строку одним из двух возможных операторов:
- для играющего А:
A = not(A)
или
if A goto K
- для играющего B:
B = not(B)
или
if B goto K
Здесь K - номер строки в пределах от 1 до N.
На других версиях BASIC булевы переменные можно заменить на
числовые:
if A = 0 then A = 1 else A = 0
и
if A = 1 then K
Если в результате прогонки написанной программы A будет равно B, то
выигрывает участник A, если A <> B, то участник B. Поэтому в целях
судейства программу следует замкнуть оператором:
N+1 print "Выиграл "; : if A = B then print "A" tlse print "b"
Предлагаемая игра способна не только скрашивать досуг. Дело в том,
что программы, где много операторов перехода, таят в себе риск
зацикливания. Мастерство программиста заключается, в частности, в том,
что он вовремя замечает "предрасположение" составляемой им программы к
зацикливанию и изменяет ее, чтобы избежать этого недостатка. Такую
зоркость и помогает воспитывать предлагаемая игра. Ввоспитательных целях
в число ее правил введены такие. Если после очередного хода соперника
второй игрок заявит о "зацикленности" написанной к этому моменту
программы и это подтвердится, то заявивший выигрывает. Если это не под
тверждается (при большой программе и неповоротливой машине время такой
проверки можно ограничить), то заявившему засчитывается поражение. После
своих ответных ходов игроки теряют право на заявку о зацикливании. Но
если в конце игры программка все-таки зацикливается, то выигрывает тот,
кто делал первый ход.
Вот пример партии для игры в 4 строки, где выиграл B.
1 rem 1 A = not(A) 1 A = not(A) 1 A = not(A) 1 A = not(A)
2 rem 2 rem 2 rem 2 rem 2 if B goto 4
3 rem 3 rem 3 B = not(B) 3 B = not(B) 3 B = not(B)
4 rem 4 rem 4 rem 4 if A goto 1 4 if A goto 1
Игра не требует компьютера, хотя он может существенно упростить
судейство.
Предлагается также реализовать программу, преврващающую ЭВМ в
партнера. Следует помнить, что число вариантов игры для фиксированного N
составляет N! * (N^N). [ ! - факториал, ^ - степень].
А. Ермаков (Москва)