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

3 2

4 4

5 5

6 2

7 1

Таким образом, нет последовательности из 5 целых, попарные разности которых порождают 10 первых натуральных чисел. Допустим теперь возможность повторений в последовательности разностей. Можно ли с помощью 5 членов породить — с помощью их разностей — 9 первых натуральных чисел?

Об этих последовательностях ничего не известно. Пусть дано число n членов последовательности; каково наибольшее число последовательных целых чисел, начиная с 1, которые можно получить с помощью попарных разностей членов последовательности?

Запрограммировать это не очень трудно. Но берегитесь чересчур долгих вычислений!

?** Головоломка 24. Прогулка королевы.

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

Случай «королевы» (ферзя) — немного другой. Эта фигура может перемещаться по горизонтали, по вертикали или по диагонали. Назовем «движением» перемещение на некоторое число полей в определенном направлении, Разрешается много раз проходить по одному и тому же полю. Но требуете пройти все поля эа наименьшее возможное число движений, причем, конечно, нужно вернуться на исходное поле. Так как число движений не дано, то не попытаетесь ли вы сначала проделать все вручную, чтобы угнать верхнюю границу…

???* Головоломка 25. Девушки ив пансиона Киркмана.

Пансион Киркмана — это колледж для девушек из высшего общества. Надзирательницей там — мисс Фармер. Каждую среду после полудня она сопровождает класс на прогулку. В своей нарядной униформе, в соломенных шляпках они медленно вышагивают по трое в три ряда. Мисс Фармер несговорчива: «Я не хочу маленьких компаний; вы должны располагаться так, чтобы не оказаться с той же подругой в вашем ряду до тех пор, пока вы не проведете этих прогулок со всеми остальными». На это наши девушки заявили, что поступать так очень трудно. Поэтому мисс Фармер решила сама организовать ряды. Для начала она веяла класс с 9 ученицами. Ей удалось быстро организовать ряды. У каждой ученицы было 8 подружек, и она должна была находиться с двумя новыми подружками каждую неделю, так что мисс Фармер предусмотрела цикл в 4 недели.

Затем мисс Фармер был поручен класс с 15 ученицами. Поэтому было необходимо ввести цикл в 7 недель для того, чтобы каждая ученица была за это время в одном ряду с 14 остальными. Тогда мисс Фармер поняла, в какое ужасное предприятие она оказалась вовлеченной.

Хотите ей помочь? Но заметьте: это вы сами пускаетесь в это ужасное предприятие. Всячески желаю, чтобы вашему микрокомпьютеру было больше нечего делать. Попытайтесь, если все предыдущее не будет отнимать долгие часы…

Эта задача принадлежит Т. П. Киркману и была впервые опубликована в Ladyʼs and Gentlemanʼs Diary за 1850 год. Для ее решения нужно пролить немало чернил, и вы можете рассмотреть значения, отличные от 9 и 15. Но выглядит вполне правдоподобным, что 15 — патологическое число, и Роуз Болл [BAL] предложил геометрический подход к решению, если число девочек не равно 15. Может быть, подход с точки зрения информатики позволит вам получить в этой задаче новые результаты…

*** Головоломка 26. Пентамино.

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

Все они приведены на рис. 31. Эти двенадцать шашек, каждая из которых имеет площадь 5, могут быть собраны в прямоугольник с площадью 60. Есть много решений для прямоугольника 6 × 10, а также 5 × 12. Меньше решений для прямоугольника 4 × 15 и только два для прямоугольника 3 × 20, если, конечно, не различать решения, отличающиеся только симметрией. Можете ли вы найти их за разумное время на вашем компьютере, проверив, что их действительно именно 2?

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

* Головоломка 27. Песенка почти спета.

Знаменитая игра Армана Жаммо уже была упомянута выше (игра 12). Но сейчас мы еще не описываем ее полностью; она довольно трудна для программирования. Вот другая форма, которую проще реализовать и которая еще не лишена интереса. Я верю также, что для любителей математических развлечений здесь есть что делать.

Возьмем случайным образом p двузначных чисел. Возьмем случайным образом также двузначное число s. Соединим эти p чисел между собой сложениями или вычитаниями. Все числа должны быть использованы. Можно ли таким образом получить число s?

При последовательных испытаниях компьютер будет работать быстро. Тогда вы можете попытаться увидеть, что происходит, когда мы заставляем меняться p. Если у вас мало чисел, то у вас и мало шансов получить Если вы берете много чисел (большое p), то, поскольку вы обязаны использовать их все, то у вас снова мало шансов прийти к цели. Мне кажется, что наиболее благоприятны значения p около 8 или 9. Но я не осмеливаюсь гарантировать этого полностью. Нужно быть уверенным в генераторе случайных чисел. Получаете ли вы тот же результат? Я не пытался получить его математическим рассуждением. Может быть, я и неправ. Если я действительно неправ, дайте мне знать об этом!

*** Головоломка 28. Песенка спета.

На этот раз дело идет именно об игре Армана Жаммо. Вам надлежит гадать вашему компьютеру шесть шашек, взятых среди 24; а именно, в набор входят:

по два раза — шашки от 1 до 10,

один раз — шашки 25, 50, 75, 100.

Затем вы задаете искомое число, скажем n, обязательно трехзначное. Требуется соединить значения шашек между собой с помощью четырех операций: сложения, вычитания, умножения и деления — чтобы получить число n. Не обязательно использовать все 6 шашек.

Если число n получить нельзя, то телевизионная игра допускает и числа, близкие к n, и тот, чье число ближе всего к n, и становится победителем.

Теоретически эта программа не должна быть трудной. Есть ограниченное число возможных комбинаций:

— есть 15 способов взять две шашки среди 6 и, самое большее, 4 способа соединить их между собой, следовательно, самое большое 60 комбинаций с двумя шашками. Но их уже гораздо больше для трех шашек. Испытать все комбинации за разумное время не представляется возможным.

Когда вы излагаете решение, вы берете две шашки из 6, соединяете их между собой одной из четырех операций (на самом деле можно считать, что только тремя, начинать с деления — это исключение). Есть 60 (или, скорее, 45) способов это сделать. После этого задача сводится к задаче с 5 шашками. При таком подходе решение кажется более достижимым.

Следовательно, попробуем. Самые большие упрощения возникают, если вы не ищете для данного числа приближенных значений. Компьютер выводит результат, если он его находит; в противном случае он сообщает, что он решения не нашел. Вы сами можете систематически проводить одну попытку за другой. Пусть pi, pj, pk обозначают три из 6 шашек. Вы можете искать решение в виде

pi * комбинация из 5 оставшихся шашек = n,

pj + pi * комбинация из 4 оставшихся шашек = n,

−pj + pi * комбинация из 4 оставшихся шашек = n,

±(pj ◦ pk) + pi * комбинация из 3 оставшихся шашек = n,

где ◦ означает одну из четырех разрешенных операций. Удивительным образом все это очень быстро и очень часто приводит к точному ответу. Никто на запрещает вам попробовать что-то лучшее…

В соответствии с заглавием примера попытайтесь поэтому для 6 шашек 10, 10, 25, 50, 75, 100 найти 370, 369, 368…

7. Обо всем понемногу

В этом разделе я объединил различные задачи, среди которых далеко не все являются головоломками, по той причине, что опыт показывает: средний программист в них достигает цели не бее труда. Для некоторых из них в различных книгах можно найти многочисленные решения, не всегда правильные, или — во всяком случае — не всегда хорошие, или слишком плохо объясненные. Условия этих задач могут показаться мало привлекательными. Но если в программировании вы любите именно трудности, не поддавайтесь первому впечатлению.