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

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

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

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

Примечания

1

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

2

Строго говоря, эти рассуждения применимы к любой программе, написанной на любом языке, если только эта программа не использует никакой внешней информации в качестве исходных данных. В качестве такой внешней информации удобнее всего использовать что-нибудь связанное с временем: число изменений напряжения в сети с момента последнего включения вашего компьютера или число секунд с момента его покупки, если ваш компьютер снабжен внутренними энергозависимыми часами (на литиевой батарейке), и т. п. Обычно, на каком бы языке вы ни работали, у вас есть возможность прочесть показания внутренних часов компьютера (посмотрите в документации, как работать с таймером). — Примеч. ред.

3

См. предыдущую сноску. — Примеч. ред.

4

«Пришлите побольше денег.»

5

«Помогите молодому человеку.»

6

«Нужно, лекция, ученик.»

7

S — первая буква слова «somme» (фр. сумма), P — слова «produit» (фр. произведение). — Примеч. ред.

8

Да и от языка, который вы используете. — Примеч. ред.

9

Повторим эти рассуждения чуть более подробно. Пусть

a1 = 2, ai+1 = ai² − 1 mod n,

b1 = 2, bi+1 = bi² mod s