Текст книги "Программирование игр и головоломок"

Автор книги: Жак Арсак

сообщить о нарушении

Текущая страница: 16 (всего у книги 16 страниц)

6. Комбинаторные задачи

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

Действительно ли вам что-то еще нужно сообщать? Тогда я немного уточню способ поддержания части от 1 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a₁, a₂, …, а_р. Вы последовательно заменяете элемент а_р элементами а_i, где i направлен по убыванию. Вы последовательно получите

a₁, a₂, …, а_р-1, а_р,

a₁, a₂, …, а_р, а_р-1,

a₁, a₂, …, а_р-3, а_р-1, а_р, а_р-2.

По индукции, предположим, что в некоторый момент вы получили

a₁, …, а_i-1, а_i+1, …, а_р, а_i

после перемены мест элементов с номерами i, р.

На следующем ходе вы поменяете местами а_i-1 и последний член, который равен а_i. Эта форма остается неизменной, и первая часть, от 1 до р − 1, остается отсортированной в неубывающем порядке. В конце вы получите

a₂, a₃, …, а_р, a₁.

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

Это вы делаете только в случае необходимости. Незачем восстанавливать порядок, когда все закончено.

Процедура работает достаточно быстро для того, чтобы в случае неудачи иметь возможность испытать наличие решения для n − 1, а затем для n + 1. Таким образом, по прошествии 45 с для каждого кандидата мы получаем в качестве результата

– решение, если оно существует,

– приближение о точностью до единицы, если это возможно.

Эта программа терпит неудачу крайне редко.

В выпуске от 8 марта 1984 года следующий розыгрыш не был найден ни кандидатами, ни Бертраном, ни кем– либо из присутствующих:

50 10 10 5 4 2 n = 767.

На моем микрокомпьютере нужно 18 с, чтобы обнаружить, что эта задача не имеет решения, а затем еще 5 с, чтобы получить

50 − 10 = 40 , 40 * 5 = 200, 10 − 2 = 8,

200 − 8 = 192, 192 * 4 = 768.

Для задачи

9 7 6 4 3 1 n = 795 через 6 с получается

4 * 9 = 36, 36 + 1 = 37, 37 * 7 = 259,

259 + 6 = 265, 265 * 3 = 795.

Наконец,

100 50 8 5 4 2 n = 631.

За менее чем 2 с получаем

50 − 4 = 46 , 46 * 2 = 92, 92 * 8 = 736,

100 + 5 = 105 , 736 − 105 = 631.

Я уже предлагал вам следующий пример:

100 75 50 25 10 10.

Для n = 370 особой трудности нет, потому что это – кратное десяти.

Компьютер сообщает мне

75/25 = 3,

50 − 3 = 47,

47 * 10 = 470,

470 − 100 = 370.

Это уже интересно, потому что это – совершенно не то решение, которое я собирался искать.

Чтобы найти 369, нужно образовать число, не кратное 5, – чего нельзя сделать с помощью какой-либо из трех операций +, −, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение:

50/10 = 5,

5 * 75 = 375,

375 − 10 = 365,

100/25 = 4,

365 + 4 = 369.

Обе представленные здесь программы не позволяют получить это решение. Действительно, оно записывается в виде

(50/10) * 75 + 100/25 − 10.

А число 368? Вы нашли для него решение? Я не сумел. Но Жак Бейгбеде сообщил мне, что он получил его делением на 25…

10 * 100= 1000,

1000 − 75 = 925,

925 * 10 = 9250,

9250 − 50 = 9200,

9200/25 = 368.

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

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

Программисты обманываются, поскольку они не берут на себя труд прояснить различные ситуации.

В строке 200 мы знаем, что цепочка а пройдена полностью, и исследованы все символы, не являющиеся пробелами. Если в цепочке b содержится еще какой-нибудь символ, не являющийся пробелом, то равенства цепочек нет. Все в порядке.

В строке 300 цепочка а пройдена вплоть до некоторого символа, не являющегося пробелом, и этот символ еще не исследован. Цепочка b пройдена полностью, и в ней не содержится более ни одного символа, не являющегося пробелом. Следовательно, эти две цепочки различны. Можно было бы сказать, что дальнейшее движение по цепочке а бесполезно, но не приводит к ошибке. Но это неверно. Вы остановились на еще не исследованном символе, который не является пробелом. Если вы перейдете к следующему символу, не являющемуся пробелом, то данный символ вы потеряете. Если, как бывает в большинстве случаев, цепочка а совпадает с цепочкой b с точностью до пробелов за исключением единственного дополнительного символа в конце цепочки, то именно по этой-то причине и должен быть остановлен пробег цепочки а. Перемещаясь и не обнаруживая больше символов, не являющихся пробелами, мы получаем сообщение, что цепочки совпадают, а это неверно. Ясно, что программисты не принимали во внимание и не изучали именно этот случай. И никаких оснований поступать так нет. В этом и состоит преимущество логических рассуждений о тексте программы по сравнению с проверкой ее правильности с помощью тестирования.

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

Возьмем общую ситуацию:

а пройдена вплоть до i включительно;

b пройдена вплоть до j включительно;

обе части совпадают с точностью до пробелов.

ВЫПОЛНЯТЬ

  продвинуть i на следующий символ в а, не являющийся пробелом;

  продвинуть j на следующий символ в b, не являющийся пробелом;

  ЕСЛИ таких нет в а И таких нет в b ТО

  r := ИСТИНА;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ таких нет в a ИЛИ таких нет в b ТО

  r := ЛОЖЬ;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ a[i] ≠ b[j] ТО r := ЛОЖЬ;

  КОНЧЕНО КОНЕЦ_ЕСЛИ;

ВЕРНУТЬСЯ

Эта программа совершенно симметрична относительно а и b…

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

Нужно работать по модулю n. Удобнее всего пронумеровать элементы вектора от 0 до n − 1. Все элементы спускаются вниз на m по модулю n. Элемент, который переходит в 0, имеет номер m; элемент, который переходит в m, имеет номер 2m по модулю n; элемент, который переходит в 2m, имеет номер 3m по модулю n… Таким образом, мы получаем цепочку чисел, кратных m по модулю n. Весь вопрос в том, чтобы узнать, порождает ли последовательность чисел, кратных m по модулю n, последовательность всех целых от 0 до n − 1.

Это так, если m и n взаимно просты. В противном случае пусть с наибольший общий делитель m и n:

m = m'с, n = n'c,

n' * m = n' * m' * с = m' * n = 0 по модулю n.

Эта цепочка возвращается в 0 за n' = n/с операций. При этом пробегается не весь вектор, а только его элементы, сравнимые с 0 по модулю с.

Беря в качестве исходных элементов различных циклов последовательно целые числа от 0 до c − 1, вы разместите все элементы вектора, причем каждый из них будет перемещаться в точности один раз…

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

Рассмотрите более общую задачу, что заставит вас открыть одно из этих знаменитых «преобразований программы», столь полезных, когда желательно улучшить уже существующие программы. Обозначим через t и u два условия, а через a и b – две последовательности инструкций. Вот простой цикл:

ПОКА t ВЫПОЛНЯТЬ

  ЕСЛИ u ТО a ИНАЧЕ b

КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Последовательность операций следующая:

– проверяется условие t,

– если оно истинно, то проверяется u,

– если u истинно, то выполняется a, и все возобновляется.

Допустим, что условия t и u таковы, что я имею возможность проверить u, даже если проверка условия t дает значение ЛОЖЬ[29]29
  Вот пара условий, которая не обладает этим свойством: t: x ≠ 0; u: sin(1/x) > 0. – Примеч. ред.


[Закрыть]. Тогда, пока условия t и u истинны, в цикле выполняется а.

Вот другая последовательность, которая может встретиться:

– проверяется условие t,

– если оно истинно, то проверяется u,

– если u ложно, то выполняется b, и все возобновляется.

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

ПОКА t ВЫПОЛНЯТЬ

  ПОКА t И u ВЫПОЛНЯТЬ а ВЕРНУТЬСЯ

  ПОКА t И НЕ u ВЫПОЛНЯТЬ b ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

Мы перепишем программу для определения равнин, чтобы придать ей форму ПОКА, заключенного в скобки ЕСЛИ:

i := 1; р : = 0;

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ЕСЛИ a[i] = a[i − р]

    ТО x := a[i]; р := р + 1; i := i + 1

    ИНАЧЕ i := i + 1

  КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:

– нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);

– либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.

Тогда можно использовать наше преобразование:

i := 1; р := 0;

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ПОКА i ≤ n И а[i] = a[i − р] ВЫПОЛНЯТЬ

    x := а[i]; р := р + 1; i := i + 1

  ВЕРНУТЬСЯ

  ПОКА i ≤ n И а[i] ≠ a[i − р] ВЫПОЛНЯТЬ

    i : = i + 1

  ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i − р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.

Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.

Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j − р с

a[j] = a[j − р]

только пока j − р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j − р = i, или j = i + р.

Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.

Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i − р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р₀, а конечные значения i и р удовлетворяют соотношениям i − р = j − р₀, откуда р = i + р₀ − j:

i := 1; р := 0

ПОКА i ≤ n ВЫПОЛНЯТЬ

x := а[i]; j := i

  ПОКА i ≤ n И а[i] = x ВЫПОЛНЯТЬ

    i := i + 1

  ВЕРНУТЬСЯ

  р := i + р − j; i := i + p

  ПОКА i ≤ n И а[i] ≠ a[i − р] ВЫПОЛНЯТЬ

    i := i + 1

  ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

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

Может быть, это связано с ходом мыслей, который я приобрел, преподавая[30]30
  Прочтя весь этот ужас, я решил провести решение, основанное на методике из курса программирования механико-математического факультета МГУ.
  Каждой последовательности чисел {a₁, а₂, …, a_i} (i ≥ 1) сопоставим число lmax, равное максимальной длине равнинного участка этой последовательности. Очевидно, что lmax ({a₁}) = 1. Пусть мы знаем lmax ({a₁, а₂, …, a_i}). Как вычислить величину lmax ({a₁, …, a_i, a_i+1})? Добавление элемента a_i+1 к последовательности {a₁, а₂, …, a_i} не затрагивает равнинных участков этой последовательности, кроме, быть может, последнего. Если a_i+1 = a_i, то длина этого последнего участка – назовем ее llast ({a₁, …, a_i}) – увеличивается на единицу. Если величина llast ({a₁, …, a_i, a_i+1}) окажется при этом больше величины lmax ({a₁, а₂, …, a_i}), то это значит, что последний равнинный участок в последовательности {a₁, а₂, …, a_i, a_i+1} по крайней мере на 1 длиннее всех предыдущих, и, значит, lmax ({a₁, а₂, …, a_i, a_i+1}) = llast ({a₁, а₂, …, a_i, a_i+1}).
  Введем четыре величины:
  i – число рассмотренных членов последовательности,
  lmax – максимальная длина равнинного участка для рассмотренных элементов,
  llast – длина последнего равнинного участка для рассмотренных элементов,
  xlast – последний рассмотренный элемент последовательности (он равен а[i]).
  Теперь приведем без пояснений программу, которая вычисляет lmax ({a₁, …, a_n}) по индукции.
  i := 1; lmax := 1; llast := 1; xlast := a[1]
  нц покаi < n
   x := a[i + 1]
    если x = xlast то llast := llast + 1
    иначе llast := 1 кесли
    если llast > lmax то lmax := llast кесли
    xlast := x
   i := i + 1
   кц
  вывод lmax
  Подробнее об этой индуктивной методике можно прочитать в книге: А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков. – М.: Наука, 1988. – Примеч. ред.


[Закрыть].

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

Хорошенько учтите то, что вы знаете: обозначим через и таблицу, которая дает последние элементы наилучших возрастающих последовательностей для (всех возможных) длин от 1 до m.

Покажем сначала, что u_i < u_i+1. Предположим, что это не так: пусть существует такая последовательность длины i + 1, у которой последний элемент не больше u_i. Так как эта последовательность возрастает, то ее предпоследний элемент меньше u_i+1 и потому меньше u_i. Тогда, удаляя последний элемент этой последовательности, мы получили бы последовательность длины i с последним членом, меньшим u_i, что противоречило бы предположению, что u_i – последний элемент последовательности длины i с наименьшим возможным последним элементом.

Рассмотрим теперь следующий элемент x нашего вектора. Разместим его в упорядоченной таблице u. Может случиться, что x > u_m. Тогда элемент x можно присоединить к концу последовательности длины m; тем самым получилась бы (впервые) возрастающая последовательность длины m + 1, которая вследствие своей единственности была бы оптимальна.

Если x меньше u₁, то им следует заменить для построения новой наилучшей последовательности с длиной 1. Если же, наконец, оказывается, что u_i < x < u_i+1, то x можно присоединить к концу последовательности с длиной i + 1, чтобы получить последовательность с длиной i + 1, которая лучше уже известной, и поэтому u_i+1 следует заменить на х. Так как и упорядочена, то вы можете разместить в ней x с помощью дихотомического поиска.

Эта операция требует порядка log₂ m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log₂ n, что чрезмерно завышено.

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

Предположим, что вы уже прошли первую цепочку вплоть до индекса i − 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j₁ может быть поставлено в конце некоторого слова – скажем, слова длины р₁ – и даст слово длины р₁ + 1, которое окажется лучшим, чем предыдущее: действительно, если j₁ можно поставить после слова длины p₁, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р₁, но меньше положения последнего символа в слове длины p₁ + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j₂ > j₁. Его нельзя поставить в конце елова длины p₁ + 1, хотя j₂ и больше j₁, потому что это – другое появление того же символа, и их не нужно смешивать. Поэтому достаточно ограничиться по поводу этого появления символа обращением к таблице в ее части от p₁ + 2 до m.

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

Рассмотрим прямоугольник пробелов, вертикальная граница которого расположена в столбце j и располагающийся вправо от этого столбца в строках от i₁ до i₂. Его основание равно inf (l[i₁ : i₂]), а его площадь есть произведение этого основания на его высоту i₂ − i₁ + 1.

Для столбца j нужно найти максимум этой величины, когда i₁ меняется от 1 до n − 1 (n – число строк), а i₂ – от i₁ + 1 до n.

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

В центральном цикле любое введение нового члена может только уменьшить значение минимума.

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

Рассмотрим значения S для строк i и i' > i. Очевидно

S (i, j) = S (i, i' − 1) + S (i', j).

Если S (i, i' − 1) положительно, то S (i, j) > S (i', j) и строка i остается строкой, которая может содержать максимум.

Но если S (i, i' − 1) < 0, то S (i, j) < S (i', j).

Максимум нужно тогда искать либо среди S (i, j) для j < i', либо среди S (i', j) для j ≥ i'.

Заметим, что S (i', i') = а[i'].

Мы собираемся пробежать строку S (1, …) вплоть до первого индекса i₁ , для которого S становится отрицательным. Тогда мы начнем пробегать строку S (i₁ + 1, …), и т. д.

Отсюда следует, что в каждый данный момент нужно знать максимальную подпоследовательность в уже пройденной части; эта подпоследовательность задается номером начала r, номером конца q и своей суммой m. С другой стороны, нужно знать наилучшую заключительную подпоследовательность S (k, i − 1), предполагая, что вектор пройден вплоть до поля i − 1. Обозначим через s значение суммы этой заключительной подпоследовательности. Пусть k – номер отроки, дающий этой сумме максимальное значение, а s – сумма всех членов, начиная с k.

Если сумма s положительна, то она и образует максимум на строке с номером k. При переходе к i число a[i] добавляется к s. Если s отрицательно, то новый элемент с номером i и становится оптимальной строчкой, и нужно взять s = а[i].

В этих двух случаях число s нужно сравнить с оптимумом m. Если s оказывается больше, то m нужно заменить на s. Попытаемся составить программу, исходя из того, что мы сейчас обсудим. Нужно уточнить предположение индукции.

Предположим, что вектор пройден от элемента 1 до элемента с номером i − 1 включительно. Мы знаем лучшую подпоследовательность в этой части: она идет от индекса r до индекса q включительно, и ее сумма равна m: m = S (r, q). С другой стороны, мы внаем наилучшую заключительную подпоследовательность, кончающуюся в i − 1, т. е. знаем такой индекс k, что сумма S (k, i − 1) максимальна среди заключительных подпоследовательностей, Значение суммы S (k, i − 1) равно s. Может случиться, что эта заключительная подпоследовательность является наилучшей возможной во всей пройденной части, и в этом случае имеем r = k, q = i − 1, s = m. В любом другом случае s ≤ m. Если i = n − 1, то весь вектор пройден и получен искомый результат r, q, m.

В противном случае нужно включить элемент a[i]. Если s отрицательно, то a[i] и образует (как единственный участник) наилучший заключительный отрезок; берем k = i, s = a[i]. В противном случае s ≥ 0 и сумма s + a[i] больше s и больше а[i], и это и есть сумма для наилучшего заключительного отрезка, который по-прежнему начинается с номера k. В этих двух случаях отрезок s становится наилучшим отрезком, если он оказывается больше m.

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

d := 1; f := 1; m := a[1]; s := m; i := 2

ПОКА i ≤ n ВЫПОЛНЯТЬ

  ЕСЛИ s < 0 ТО k := i; s := a[i]

    ИНАЧЕ s := s + a[i]

  КОНЕЦ_ЕСЛИ

  ЕСЛИ s > m ТО d := k; f := i; m := s

  КОНЕЦ_ЕСЛИ

  i := i + 1

ВЕРНУТЬСЯ

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

Список литературы

Произведения, цитируемые в тексте

[ARS] Arsac J., Les bases de la programmation, Paris, Dunod, 1983.

[BAI] Baillif J.-C. Les casse – tète logiques de Baillif, Paris, Dunod, 1979.

[BAL] Ball W.-W. Rouse, Mathematical recreations and essays, Macmillan and C°, London, 1963.

[BER] Berloquin P., Le jardin du sphynx, Paris, Dunod, 1981.

[ENG] Engel A., Mathématique élémentaire dʼun point de vue algorithmique, Paris, Cedic, 1979.

[GRI] Gries D., The science of programming, Springer Verlag, New York, 1981.

[KNU] Knuth D., The art of computer programming, Addison Wesley, 1969.

[KUEJ Kuenzi N.-J., Prielipp B. Cryptarithms and other arithmetical pastimes, School science and mathematics association, University of Wisconsin.

[LED] Ledgard H.-F., Proverbes de programmation, Paris, Dunod, 1978.

[PBBJ Berlioux P., Bizard Ph., Algorithmique, Paris, Dunod, 1983.

[POL] Pollard J.-M. A Monte Carlo method for factorization, BIT 15, (1975), p. 331—384.

[SIR] Siklossy L., Letʼs talk Lisp, Prentice Hall, Englewood Cliffs (N. Y.), 1976.

[SCH] Schwartz В. Mathematical solitaires and games, Baywood Publishing Company, 1978.

Для тех, кому нужно пополнить свое образование в программировании.

Arsac – Mondou О., Bourgeois – Camescasse, Gourtay M.

Premier livre de programmation (écriture de boucles de proggrammes).

Deuxiéme livre de programmation (procédures, fichiers).

Pour aller plus loin en programmation (récursivité, structures de donnees), Cedic – Nathan, Paris, 1982.

Taurisson A., Petitguillaume A.

A vous de jouer, Introduction à la science de lʼinformatique, Modulo Editeur, Outremont, Québec, Canada.