Программирование игр и головоломок
Шрифт:
Если сумма 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.
Для начала можно положиться на пробег вектора, начиная с его единственного первого элемента. В этот момент наилучший сегмент и наилучший заключительный сегмент — это одно и то же.
Эта программа осуществляет пробег вектора a один-единственный раз, что и было предписано в условии. Это очень просто, но это совершенно не очевидно.
Список литературы
Произведения, цитируемые в тексте
[ARS] Arsac J., Les bases de la programmation, Paris, Dunod, 1983.
[BAI] Baillif J.-C. Les casse — t`ete 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'ematique 'el'ementaire 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 ('ecriture de boucles de proggrammes).
Deuxi'eme livre de programmation (proc'edures, fichiers).
Pour aller plus loin en programmation (r'ecursivit'e, structures de donnees), Cedic — Nathan, Paris, 1982.
Taurisson A., Petitguillaume A.
A vous de jouer, Introduction `a la science de l’informatique, Modulo Editeur, Outremont, Qu'ebec, Canada.