Жак Арсак - Программирование игр и головоломок
Чтобы навести себя на правильный путь, заметьте, что если верхние элементы спускаются на m полей, то нижние элементы поднимаются на n − m полей.
Вы не видите? Есть n полей. Вы работаете в арифметике по модулю n. По модулю n все элементы спускаются на m полей. На этот раз вы должны найти решение, учитывая влияние на ход решения наибольшего общего делителя m и n…[26]
Головоломка 34.
Предположим, что мы уже проделали часть работы. Именно таким образом мы всегда должны начинать поиск решения. Мы ограничимся здесь случаем таблицы чисел, который предоставит нам полную возможность изучения различных стратегий и позволит вам записать несколько программ и сравнить их, не заставляя вас пускаться в манипуляции с более деликатными цепочками.
Следовательно, Предположим, что мы прошли таблицу до номера i включительно. Пусть в пройденной части мы нашли, что элемент со значением x повторялся p раз, и пусть это — максимальное число повторений.
Но нужно еще более уточнить ситуацию в точке остановки. У нас есть две возможности.
— Первая идея: мы останавливаемся в конце равнинного участка.
Если i = n, то мы прошли всю таблицу, узнали наилучший равнинный участок, и все закончено. В противном случае мы пробегаем следующую равнину и измеряем ее длину r. Если r ≤ p, то наилучшая равнина остается неизменной, а в противном случае именно последняя равнина и регистрируется заново как наилучшая, и мы возобновляем движение по таблице. Это просто, и это легко программировать. Запишите это решение, чтобы иметь возможность сравнить его с другими решениями.
— Вторая идея: мы останавливаемся в произвольной точке i. Мы оказываемся на некоторой равнине и уже нашли r элементов на этой равнине.
Если i = n , то проход таблицы завершен. Мы внаем наилучшую возможную равнину с p повторениями и равнину с r элементами на последнем проходе, Мы берем лучшую из этих двух, и все кончено.
В противном случае нужно продвинуться вперед на один элемент. Либо этот элемент равен непосредственно предшествующему элементу; мы все еще находимся на той же самой равнине, длина которой увеличивается. Либо он отличается от предыдущего; тогда оказывается пройденной равнина длины r, которую при r > p нужно зарегистрировать как наилучшую. С другой стороны, нужно сказать, что новый элемент находится на равнине, которая в данный момент имеет длину 1.
На первый взгляд, первая стратегия дает программу, содержащую два вложенных цикла: маленький внутренний цикл для прохода равнины и глобальный цикл для прохода всего вектора, равнина за равниной.
Вторая программа содержит только один цикл, пробегающий элементы вектора один за другим и в нужных местах исправляющий значение p. Следовательно, эта вторая программа лучше.
Но это не все. Не позволяйте обмануть себя видимостью. Обе эти программы пробегают вектор элемент за элементом. Если вы составляете вашу программу на Бейсике или LSE, используя операторы ПЕРЕЙТИ К, а не циклы ДЛЯ или FOR, то вы убедитесь, что эти два решения почти неотличимы, а второе решение требует двукратного написания теста, сравнивающего r и p, так что едва ли не чаще эта вторая программа оказывается хуже.
Но есть третья стратегия. Восстановим общую ситуацию: мы прошли часть вектора до номера i включительно и определили наилучшую равнину длины p с общим значением ее элементов, равным x. Точка остановки произвольна.
Известно, что нужно осуществить включение нового элемента. Поставим следующий вопрос: насколько этот новый элемент может изменить ситуацию? Ответ: если он оказывается принадлежащим равнине с длиной, большей p. Может ли он оказаться принадлежащим равнине с длиной, намного большей p? Нет, мы бы это уже заметили. Следовательно, новый элемент изменяет ситуацию, если он принадлежит равнине длины p + 1. Но такое может случиться, если он равен элементу, содержащемуся в p предыдущих полях.
В начале ничего не пройдено: i = 0, и нет ни одного повторения: p = 0.
i := 0; p := 0
ВЫПОЛНЯТЬ
ЕСЛИ i = n ТО КОНЧЕНО
КОНЕЦ_ЕСЛИ
i := i + 1
ЕСЛИ a[i] = a[i − p] ТО x := a[i]; p := p + 1
КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ
Красиво, не правда ли?
Но можно сделать лучше. Тщательно рассмотрите эту программу. Вы должны суметь обнаружить, что можно перескакивать через некоторое количество элементов без обращения к ним…
Головоломка 35.
Не позволяйте себе поддаться впечатлению от ограничений на сложность алгоритма. Вы не можете выделить все возрастающие подпоследовательности, чтобы найти лучшую из них, это было бы слишком длинно, и легко сделать что-нибудь попроще этого.
Воспользуемся снова той же самой техникой. Пусть мы прошли вектор вплоть до некоторой точки. Пусть мы получили соответствующие результаты, но, поскольку мы еще не знаем, в какой форме они нужны, мы оставим их на некоторое время неопределенными. В любом случае выглядит вероятным, что мы знаем наибольшую по длине возрастающую подпоследовательность пройденной части, без которой мы как будто лишены возможности добраться до конца вектора… Как и выше, поставим вопрос: насколько изменяет ситуацию появление нового элемента? Он может продолжить известную нам наиболее длинную последовательность, если он может быть поставлен в ее конец, и, следовательно, если он больше последнего элемента этой последовательности. А если зто не так, то эту наиболее длинную подпоследовательность он изменить не может. Но он может продолжить более короткую подпоследовательность, которая постепенно может стать более длинной, если она медленнее растет.
Рассмотрим, например, последовательность
4 5 3 8 2 6 1 7
Если ограничиться тремя первыми элементами, то наиболее длинная возрастающая подпоследовательность — это
4 5
Добавим четвертый элемент, 8. Он может быть присоединен к концу этой подпоследовательности и дает возрастающую подпоследовательность длины 3:
4 5 8
Следующий элемент — 2 — ничего не меняет. Следующий — 6 — не может быть присоединен к концу последовательности длины 3, но он может быть присоединен к концу последовательности длины 2 — последовательности 4 5 — чтобы дать другую подпоследовательность длины 3:
4 5 6
Эта последовательность меньше предыдущей, поскольку ее последний элемент меньше, и поэтому у нее больше шансов иметь возможность продолжаться. На самом деле, 7 может быть присоединено к ее концу, что дает максимальную возрастающую последовательность
4 5 6 7
Мы уже видим, что нужно уточнить понятие максимальной возрастающей подпоследовательности, определяя наилучшую из них: это — такая последовательность, у которой последний элемент — наименьший возможный. В этой строке наилучшая подпоследовательность длины 1 есть элемент 1, наименьший элемент последовательности. Таким образом, мы приходим к следующей идее: предположим, что мы знаем последний элемент наилучшей подпоследовательности длины k в пройденной части для любого значения k от 1 и вплоть до максимального значения m.
Новый рассматриваемый элемент изучается с точки зрения возможности его присоединения к концу подпоследовательности длины k, чтобы превратить ее в подпоследовательность длины k + 1. Покажите, что если это возможно, то эта новая последовательность лучше, чем предыдущая подпоследовательность длины k + 1. Может случиться также, что этот новый член оказывается меньше элемента, образующего подпоследовательность длины 1. Тогда он дает лучшую, чем предыдущая, подпоследовательность длины 1.
Таким образом, вы получаете алгоритм, в котором для любого элемента рассматриваемого вектора нужно искать в таблице последние элементы наилучших подпоследовательностей, и размер этой таблицы равен m. Покажите, что эта таблица упорядочена. Осуществите в ней поиск места рассматриваемого элемента вектора с помощью дихотомического поиска[27] и вы получите алгоритм порядка n In n.
Головоломка 36.
Вы можете вдохновиться решением предыдущей задачи. Нужно пробежать одну из двух цепочек символ ea символом. Предположим, что мы ее пробежали до некоторого i включительно. Нужно осуществить регистрацию лучших из наиболее длинных слов в порядке возрастания длин, содержащихся в пройденном куске рассматриваемой цепочки и во второй цепочке в целом. Как определить наилучшее слово длины k? Скажем, что это — такое слово, которое имеет наибольшие шансы оказаться продолжаемым, следовательно, такое слово, у которого положение последнего символа во второй цепочке минимально. Это приводит к рассмотрению того, насколько важно знать положение символов во второй цепочке и, следовательно, к заданию наилучших слов списком из положений в цепочке (например, с помощью конкатенации совпадающих с ними символов во второй цепочке).
