Читать «Программирование игр и головоломок» онлайн - страница 132

где F —функция, определяемая условием F(x) = f(x), x ∊ [p, q]. Впрочем, все эти интегралы нам не понадобятся, так как у этой формулы есть гораздо более простой аналог для сумм: a_i + a_i+1 + … + a_j = b_j − b_i−1, где последовательность {b} определяется условием, что b_k − b_k−1 = а_k для любого k от 1 до n. Последовательность {b} легко построить: b₀ = 0, b_k+1 = b_k + a_k+1. Для последовательности {b} задача ставится так: найти такие i < j, что разность b_j − b_i максимальна. С этой задачей уже легче справиться. — Примеч. ред.

29

Вот пара условий, которая не обладает этим свойством: t: x ≠ 0; u: sin(1/x) > 0. — Примеч. ред.

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. — Примеч. ред.