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

a [ i 1] a [ i 2] a [ i 3] … a [ i p ]

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

Последовательность возрастает [18] Нужно было бы сказать «не убывает», но получилось бы совершенно не в стиле этой книги. — Примеч. ред. , если, кроме того,

a [ i 1] ≤ a [ i 2] ≤ a [ i 3] ≤ … ≤ a [ i p ].

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

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

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

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

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

«Je peux te d onner lʼa dr esse dʼ un excellent cireur de parquet s: il s erend à domicile»

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

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

«А lʼoccasion du 14 juill et, l es h omm es remp lace ro nt les cruch es dan s le sch ambr es».

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

JETEOERLARNLECREDASLSAME

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

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

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

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