Программирование игр и головоломок - Жак Арсак

«А lʼoccasion du 14 juillet, les hommes remplaceront les cruches dans les chambres».

Моя Программа сообщает мне, что наиболее длинная последовательность букв, которая встречается одновременно в одном и том же порядке в обоих отрывках, это набор

JETEOERLARNLECREDASLSAME

Вы можете проверить, что эти буквы действительно встречаются в обеих фразах (во второй из них они подчеркнуты). Но вручную невозможно проверить, что этот набор — самый длинный из возможных. Если вы не можете доверять вашей программе, не пишите ее…

Если вы сожалеете, что я злоупотребил названием, которое напоминает совсем о другом, а именно, об игре Армана Жаммо: найти наиболее длинное слово, которое можно образовать из 9 данных букв, то я не запрещаю вам исследовать также и эту игру. Но тут я вижу два препятствия. Во-первых, с точки зрения процесса ее создания есть очень мало того, что требуется обнаружить или открыть (если не пришлось открывать какой-нибудь словарь Скраббля). Далее, нужно ввести в компьютер настоящий словарь, что предполагает большой объем хранения и чудовищный труд отстукивания по клавишам, совершенно лишенный интереса…

?*** Головоломка 37. Белый прямоугольник.

Ах, ах! Тут-то я вас и поймал. Вы немедленно вообразили себе какую-нибудь не поддающуюся пересказу историю… Такое в книгах по информатике бывает редко, но бывает [SIK]. В своем сочинении о языке ЛИСП Лоран Сиклосси должен был использовать многочисленные примеры буквенных цепочек, и все составленные им цепочки одна смешнее другой. Это и вдохновило меня на предыдущую головоломку. Я предложил своему издателю перевести сочинение Сиклосси, что не должно было быть таким уж трудным, поскольку автор использует французские фразы, чтобы блеснуть учтивостью (иначе он бы говорил это по-латыни). Но Сиклосси, который превосходно владеет французским языком — несмотря на то, что он профессор информатики в Соединенных Штатах, — захотел изменить примеры к французской версии книги, используя «акрофонические перестановки» — перестановки букв или слогов, создающие слова с новым значением… Издатель не согласился, и французская литература потеряла прекрасное сочинение о языке ЛИСП… Если вы читаете по-английски и если вы хотите выучить ЛИСП, почему вам нельзя развлекаться, учась?

Здесь речь идет совсем о другом. Эта задача была предложена как одна из четырех тем на конкурсе программирования в АФСЕТ несколько лет назад. Вам дана прямоугольная решетка для кроссворда. Найдите белый (т. е. не содержащий вычеркнутых черных клеток) прямоугольник наибольшей площади, вписанный в решетку (квадрат есть частный случай прямоугольника).

На рис. 34 есть прямоугольник площади 8 в левом нижнем углу и есть квадрат площади 9. Это — хороший ответ. Программа, которую вы должны составить, должна читать размеры сетки (число строк и столбцов), затем— координаты черных полей и, наконец, давать прямоугольник наибольшей площади, например, указанием координат двух противоположных вершин.

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

Головоломка 38. Математическая композиция.

Ж.-К. Байиф [BAI], французский язык которого очень отточен, представил эту головоломку под названием «арифметическая композиция» в своей книге, из которой в ее и заимствую, Композиция состоит из четырех вопросов, связанных с вычислением площади. Один из вопросов относится к полной поверхности куба, сторона которого измеряется целым числом метров, Вот ответы учеников на различные вопросы:

Альбер 8 16 12 16 Бернар 12 16 12 18 Клод 12 18 12 18 Дени 16 18 12 20 Эрнест 8 16 10 16 Фернан 12 12 12 22 Гюстав 16 18 12 20 Анри 8 16 10 16 Исидор 16 12 12 20 Жюль 20 12 12 20

(Это — величины площадей в квадратных метрах, предложенные учениками.) Преподаватель ставит 5 за верный ответ и 0 за неверный ответ. Один-единственный из учеников получил 0. Кто оказался первым? Вне всякого сомнения, вы можете сказать больше. Эта головоломка кажется мне особенно подходящей для ее решения на компьютере…

?? Головоломка 39. Другая головоломка Давида Гриса.

Пусть дан вектор, образованный n целыми числами. Подпоследовательностью этого вектора называется набор элементов, в котором индексы идут подряд. Найти подпоследовательность с максимальной суммой. Если вы предпочитаете другую формулировку, то найдите индексы i, j, для которых величина

ai + ai+1 + … + aj−1 + aj

максимальна. Внимание: время вычисления не должно расти намного быстрее, чем n, когда n увеличивается…

Эта головоломка до некоторой степени напоминает головоломку о возрастающих подпоследовательностях, но она гораздо менее сложна. Подумайте: линейная зависимость от n! Да ведь это, грубо говоря, означает, что каждый элемент вектора рассматривается только один раз. Вам следует составить цикл

ДЛЯ i := 1 ШАГ 1 ДО n ВЫПОЛНЯТЬ … ВЕРНУТЬСЯ

И никаких циклов в этом цикле! В ответе вы получаете искомые индексы. Озадачивающе, не так ли? Я потерял на это немало времени. И тем не менее, какое простое решение!

Как вы находите?

Часть II. Первая помощь

У вас возникли затруднения, — вы не знаете, как приступить к игре или головоломке. Я не хочу предлагать вам готовое решение, иначе в чем будет удовольствие? Но, вероятно, нижеследующие указания наведут вас на правильный путь. Если бы я мог использовать дискетку вместо книги, я разложил бы эти указания на как можно большее число уровней, чтобы вы были в состоянии брать из них тот строгий минимум, который позволит вам продолжать решение. Но и в книге вы всегда можете прочесть только начало и — как только искра вспыхнет — отложить книгу и завершить решение самостоятельно.

Некоторые упражнения кажутся мне настолько очевидными, что я ничего про них не скажу. Но, конечно, это субъективная точка зрения: они могут не казаться очевидными вам. Может быть, потому, что вы не видите, в чем задача: разберите простые случаи вручную, В любом случае старайтесь сформулировать задачу с максимальной возможной полнотой, Если и после этого вы по- прежнему не видите, как вам ее охватить, поговорите с друзьями или с приятелями, Я умышленно не собираюсь сообщать вам все. Эта книга написана для того, чтобы вы стали программировать. Вам играть…

1. Случайные числа

Упражнение 2.

Нужно изучить поведение дробной части (x + a)8, когда x меняется от 0 до 1. Нарисуйте, хотя бы приближенно, кривую, представляющую эту функцию. Рассмотрите интервал на оси x, в котором значение функции меняется от некоторого целого числа до следующего за ним. Отметьте на кривой точку, в которой ордината равна этому целому, увеличенному на 0,5. Она разбивает область изменения x на два интервала. Равны ли между собой эти две половинки? Если одна из них больше другой — и если это одна и та же половинка для всех интервалов — то у вас больше шансов получать числа, меньшие (или большие, вам будет видно самим), чем 0,5.

Но что касается выбора a, то напомним, что следует избегать соотношения

дробная_часть ((x + a)8) = x,

иначе вы вместо случайной последовательности получите постоянную последовательность. Проверьте числа x = 0, x = 0,5 и x = 1.

Упражнение 4.

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

Почему не разделить интервал (0, 1) на 6 частей?

Или еще по-другому: почему бы не умножить выше случайное число на 6. Тогда оно окажется в интервале (0, 6), исключая 6. Если вы возьмете целую часть результата, то вы получите целое число от 0 до 5, включая границы, с равными вероятностями для каждого числа… Завершить следует вам, я уже сказал слишком много!