Головоломка 33.

Есть карточный пасьянс, который более иди менее похож на эту задачу. Выберем из вектора его первый элемент и отложим его в сторону на запасное поле, Мы можем поместить на его место элемент m + 1, который и должен перейти на поле 1. Теперь поле m + 1 свободно. Туда можно перенести элемент, который должен его заполнить. Возьмем конкретный пример: n = 10 и m = 4. Элементы верхней части спускаются на 4 поля, а те, которые находятся в нижней части, поднимаются на 6 полей. Вот последовательные состояния вектора. Я не представляю здесь запасное поле, которое содержит элемент 1. Я помещаю в эти поля именно номера элементов в исходной конфигурации:

исходное положение:

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

Предлагая эту задачу профессиональным программистам, я очень редко получал такое решение, потому что им не удавалось выяснить, что мы действительно перемещаем таким образом все элементы (в этом можно убедиться, подсчитывая число движений) и нет ли опасности дважды переместить один и тот же элемент, так что конечное состояние оказалось бы неправильным[25].

Чтобы навести себя на правильный путь, заметьте, что если верхние элементы спускаются на 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.

Красиво, не правда ли?

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

Головоломка 35.

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

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