Для вывода на экран я не нашел хорошего рисунка, потому что у меня нет ни графического, ни полуграфического экрана — только алфавитно-цифровой. Каждому куску я сопоставил букву и вывожу куски на экран в виде подходящим образом расположенных пяти букв. Такой вывод показан на рис. 41.
Я представляю игру внутренним образом в виде цепочки символов по двум причинам:
— используемый мною язык (LSE) в используемой мною версии является одним из наиболее эффективных языков для работы с цепочками символов. Это почти также быстро, как если использовать таблицы. Я могу очень быстро найти первое свободное место, я могу очень быстро узнать, свободно ли поле (является ли символ на этом месте в цепочке точкой?);
— вывод мгновенный: я вывожу на экран три подцепочки на трех последовательных строках.
Остается еще установить немало деталей, касающихся представления кусков. Но вы же не ждете, что я за вас сразу и программу напишу?
Головоломка 27.
А эта программа простая. Вам нужно образовать выражение вида
a1◦a2◦a3◦…◦ap,
где операция, обозначенная ◦, означает либо сложение, либо вычитание. Есть p − 1 знак, каждый из которых может принимать два значения. Это дает 2p−1 возможных значений. Каким бы ни был способ, которым вы их перебираете, вам нужно перепробовать их все (по крайней мере в случае, когда число s таково, что решения нет).
Два знака «+» и «−», так что снова двоичная система. Вы можете воспользоваться этим замечанием при составлении программы. Меняем целое число от нуля до 2p−1. Для каждого из значений рассматриваем его двоичное представление. Ставим в выражении «+» на тех местах, где стоят нули, и «−» на местах, где стоят единицы. Но в этом таится опасность побудить некоторых написать программу на языке ассемблера, что было бы ошибкой (по моему мнению. Вы тогда сплутовали бы. Есть хорошие алгоритмы на развитом языке. Не меняйте условий задачи, выписывая алгоритм, который оказался бы необъяснимым).
Вы можете также — и это, конечно, более эффективный способ — поставить знаки «+» в начале выражения и исчерпать все комбинации с тем, что осталось, затем заменить последний знак «+» на «−» и т. д, С четырьмя числами вы получите последовательно:
+++
++−
+−+
+−−
−++
−+−
−−+
−−−
Состояние знаков хранится в таблице или в цепочке.
Заметьте, что рассматриваемая задача имеет простое рекурсивное решение. Достаточно испробовать две комбинации:
a1 + — любая комбинация, которая может быть составлена из p − 1 оставшихся шашек,
a1 − — любая комбинация, которую можно составить из оставшихся шашек.
Должно получиться:
s = a1 + — комбинация из n − 1 чисел или
s = a1 − — комбинация из n − 1 чисел.
Заметим, что разность нужно брать по абсолютному значению.
Таким образом, остается искать способ представления s + a1 или s − a1 помощью n − 1 оставшихся шашек. Такую процедуру легко написать. Таблица чисел может быть глобальной величиной. Чтобы сохранять только n − 1 чисел, кроме первого, достаточно сказать, что таблица рассматривается, начиная с индекса 2. Следовательно, нужна процедура, в которой в качестве параметров берутся:
индекс, начиная с которого должны рассматриваться числа,
сумма, которую нужно найти.
Итеративные формы программы, которые вы сможете написать, суть немедленные переводы на итеративный язык этой рекурсивной формы.
Головоломка 28.
Решение, набросок которого я привожу здесь, принадлежит не мне. Я нашел его вышедшим из-под пера Николь Брео Поликен и Оливера Герца в журнале «Персональный компьютер» (Lʼordinateur individuel) за март 1983 г.
Однако я должен сознаться, что это решение меня глубоко поразило. Программа была действительно очень хорошо написана на языке Паскаль и с большим мастерством были использованы свойства вложения процедур, которые давали возможность формальные параметры или локальные переменные некоторые из этих процедур рассматривать как глобальные параметры для других процедур.
Я переписал это решение практически без изменений на LSE83 (намного более структурированная форма LSE, соединяющая преимущества структурирования языка Паскаль с возможностями манипуляций с цепочками символов, имеющихся в LSE, и, сверх того, облегчением программирования сверху вниз), и результат немедленно оказался удовлетворительным. Все это служит прославлению авторов. Как же могло тогда случиться, что пояснения, которые авторы дают к своей программе, до такой степени недоступны пониманию, что мне потребовался большой труд, чтобы достичь понимания их метода? Там, действительно, есть две или три «хитрости», которые гораздо больше заслуживали комментария, чем тот факт, что из-за рекурсии результаты записываются в порядке, обратном порядку их получения…