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

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

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

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

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

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

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

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

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

Сумеете ли вы найти простое решение?

??** Головоломка 35. Самая длинная возрастающая подпоследовательность.

Пусть дана таблица a из n каких-либо чисел (но если это может доставить вам удовольствие — из натуральных чисел. Это неважно). Подпоследовательность этой таблицы есть последовательность чисел, выделенная в порядке возрастания номеров. Более точно, последовательность

a[i₁] a[i₂] a[i₃] … a[i_p]

есть подпоследовательность последовательности а, если i₁ < i₂ < … < i_p. (Числа идут в одном и том же порядке в таблице a и в ее подпоследовательности, но эта формулировка двусмысленна.)

Последовательность возрастает[18], если, кроме того,

a[i₁] ≤ a[i₂] ≤ a[i₃] ≤ … ≤ a[i_p].

Требуется выделить из a самую длинную возрастающую подпоследовательность. Вы имеете право использовать вспомогательные векторы.

Можно найти исследование этой задачи в нескольких книгах и на нее изведено немало чернил (да и мела тоже: я видел ее исследования в трудах международных семинаров). Кроме того, совершенно не одно и то же — довольствуемся ли мы определением максимальной длины и даже последнего члена самой длинной возрастающей подпоследовательности последовательности a (внимание: может случиться, что есть много таких подпоследовательностей одинаковой длины) или же мы хотим получить также список членов такой максимальной последовательности.

Иногда в условие вводят дополнительное ограничение: число требуемых операций должно быть порядка n * In(n). Я не уверен, что это действительное ограничение. Если вы найдете решение, то оно, скорее всего, будет обладать этим свойством.

??** Головоломка 36. Самое длинное слово.

Заглавие вводит в заблуждение… Однажды мы проводили экзамен у наших учеников в DEUG по составлению программы, которая сообщает, скрыто ли данное слово в данной фразе, иначе говоря, встречаются ли буквы данного слова в том же порядке в данной фразе. Так, в следующей фразе (взятой из «Ярмарки у скупцов» Жана Шарля):

«Je peux te donner lʼadresse dʼun excellent cireur de parquets: il se rend à domicile»

слово TONDEUSE скрыто (соответствующие буквы подчеркнуты), но ни слово GAZON (нет буквы G), ни слово DOMINATEUR (все буквы есть, но в неправильном порядке) не содержатся.

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

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

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

JETEOERLARNLECREDASLSAME

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

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

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

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