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

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

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

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

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

Для столбца j нужно найти максимум этой величины, когда i 1меняется от 1 до n − 1 ( n — число строк), а i 2— от i 1+ 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 1, для которого S становится отрицательным. Тогда мы начнем пробегать строку S ( i 1+ 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.

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