Программирование игр и головоломок

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

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

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

±(p_j o p_k) + p_i * комбинация из 3 оставшихся шашек = n,

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

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

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

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

* Головоломка 29. Дихотомический поиск.

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

Следовало бы уточнить (хоть это и не в моих правилах: обычно я предоставляю вам заботу об уточнении. В этой книге вовсе не я тот человек, который должен аккуратно работать…). Пусть a — таблица с n элементами, упорядоченная так, что

a[i] < a[i + 1] для 1 < i <= n,

и x — элемент, который нужно разместить. Его место

0, если x <= a[1],

i, если a[i] < x <= a[i + 1],

n, если a[n] < x.

Один сотрудник факультета Нотр-Дам де ла Пэ в Намюре изучил 18 программ, опубликованных различными авторами по всему свету и в каждой нашел хоть что-то, за что можно упрекнуть. Всякий раз, когда я получаю новую книгу по программированию (к счастью, я получаю не все), я смотрю, нет ли там случайно исследования этой задачи. Почти во всех случаях это так. Настоящий «ослиный мост» [16] информатики…

* Головоломка 30. Равенство «с точностью до пробелов».

16

«Ослиным мостом», дальше которого учащегося сдвинуть трудно, считалась в XII–XIII вв. в Парижском университете либо теорема о равенстве углов при основании равнобедренного треугольника, либо геометрическое доказательство теоремы Пифагора. — Примеч. пер.

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

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

А РОЗА УПАЛА НА ЛАПУ АЗОРА

АРГЕНТИНА МАНИТ НЕГРА

Попытайтесь получить правильную (это уж как минимум) и элегантную программу.

Головоломка 31. Анаграмма.

Еще одна головоломка, вопреки ее внешнему виду, Дело в том, чтобы сказать, являются ли две цепочки букв анаграммами друг друга (т. е. получаются ли они друг из друга перестановками букв). Эта задача имеет совершенно различный вид в зависимости от того, разрешите ли вы себе изменять обе цепочки или порождать новые цепочки, или нет. Выбор я предоставляю вам… Может быть, вы заметите, что различные решения следует оценивать в зависимости от соотношения между размерами цепочек и используемого алфавита. Подумайте о крайних случаях: алфавит из 26 букв и цепочка из 1000 символов; алфавит из 1000 символов (это вроде китайского…) и цепочка из 10 символов.

Головоломка 32. Анаграмма с точностью до пробелов.

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

??* Головоломка 33. Переставить две части вектора.

Вам дана таблица a с n элементами. Требуется переставить части с номерами от 1 до m и от m + 1 до n (рис. 33).

Порядок элементов в каждой ив частой должен быть сохранен [17] . Вы не должны использовать вспомогательную таблицу, Каждый элемент должен быть перемещен не более одного раза.

Это — довольно любопытная задача, которая была предложена мне Давидом Грисом, и которую он исследовал в своей книге [GRI] Это — один из редких случаев, когда я не смог вывести программу из гипотезы рекуррентности, как я это обычно делал [ARS]. В данном случае я сначала придумал программу (ничего особенного, вы ее, конечно, прекрасно составите). И только после того — именно после того — я смог показать, почему эта программа работает правильно.

17

Вот другая и, на мой взгляд, более правильная формулировка этой задачи: циклически сдвинуть элементы n– вектора на m позиций влево. — Примеч. ред.

* Головоломка 34. Задача о равнинах.

Вам дается упорядоченная таблица каких-то элементов, например, телефонный справочник (где фамилии расположены в алфавитном порядке. Здесь мы не учитываем имен). В таблице могут встретиться омонимы (иначе говоря, последовательности из совпадающих элементов), как в телефонном справочнике. Требуется найти наиболее длинные омонимы: больше ли МАРТЫНОВых, чем СЕМЕНОВых?

Я использовал для этой головоломки название, данное ей в книге Давида Гриса [GRI]. Если вместо того, чтобы веять для иллюстрации таблицу фамилий, вы берете

таблицу чисел, расположенных в неубывающем порядке, то такая таблица составлена иэ участков возрастания, подъемов и ровных участков, «равнин». Тогда нужно найти наиболее длинную равнину.

Эта задача оказывается не вполне одной и той же в зависимости от того, ищете ли вы только наибольшую длину равнины (что делает Д. Грис) или ищете одновременно и длину ряда омонимов и сам наиболее часто встречающийся омоним (что предлагаю вам я).

G этой задачей связана неприятная для меня история. Я намеревался продумать эту задачу в Нанси также, впрочем, как и Давид Грис. Я довольно легко обнаружил два решения, различные по духу, но не по виду, что поставило передо мной задачи преобразования программ (каким образом различные отправные точки могут привести, с точностью до нескольких манипуляций, к одной и той же программе). Как и рассказывает в своей книге Давид Грис, я очень гордился своими решениями, пока не обнаружил в той же книге Д. Гриса решение, принадлежащее Майклу Гриффиту: его решение намного проще…