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

Пример

Вывод

Ввод

Пример

4 -19 -4 2 21 -23 15 6 -2 5

4 10

Проще всего в двойном цикле перебирать все пары с начальным и конечным номерами и для каждого интервала находить сумму чисел. Максимальная сумма даст ответ задачи. Оценим трудоемкость такого подхода. Двойной цикл в общем случае приводит к трудоемкости O (N ²), а общая трудоемкость составит O (N ³), что абсолютно неприемлемо.

Более рационально при первом проходе накапливать в массиве S частичные суммы, то есть определять величины S_i = X ₁ + X ₂ +…+ X_i. Тогда X_i+ X_i+1+…+ X_j = S_j - S_i-1. Такой подход обеспечивает трудоемкость O (N ²), что также не может нас устроить.

Оказывается, что существует линейный алгоритм с трудоемкостью O (N), который позволяет обходиться даже без массива, обрабатывая данные за один проход напрямую из файла [17]. Будем сохранять лучшую сумму элементов R на каждом шаге и соответствующий ей интервал индексов, а также текущую сумму элементов S. Если на очередном i -ом шаге встречается положительный элемент X_i, а S<0, то начнем отсчет с начала, положив S = X_i. В противном случае прибавим значение X_i к текущей сумме S. Сравним значения R и S. Максимальную из этих величин сохраним как лучшую сумму элементов R на i -ом шаге и перейдем к следующему шагу. Ниже приводится текст программы, реализующей этот алгоритм.

Program BentFile; { линейный алгоритм }

Var

N,i,j,X,R,S,Res: LongInt;

{R- максимальная сумма на предыдущем шаге, S-текущая сумма} Fin,Fout: text;

Ra,Rb,Sa,Sb,a,b: LongInt;

{диапазоны индексов, обеспечивающие максимальные суммы для R,S и общую максимальную сумму }

Begin

Assign(Fin,'input.txt');

Reset(Fin); ReadLn(Fin,N);

R:=-MaxLongInt; S:=0;

Sa:=1; Sb:=1; Ra:=1; Rb:=1; a:=1; b:=1;

For i:=1 to N do

begin

Read(Fin,X);

if (S<0) and (X>=0) then

begin

Sa:=i; S:=X

end

else S:=S+X;

Sb:=i;

if X>R then

begin

Ra:=i; Rb:=i; R:=X

end;

if S>R then

begin

Res:=S; a:=Sa; b:=Sb;

Ra:=Sa; Rb:=Sb; R:=Res;

end

else

begin

a:=Ra; b:=Rb; Res:=R;

end;

end;

Close(Fin);

Assign(Fout,'output.txt'); Rewrite(Fout);

WriteLn(Fout,Res);

WriteLn(Fout,a,' ',b);

Close(Fout);

End.

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

Счастливые билеты. Известно, что «счастливым» билетом называется билет, в номере которого сумма цифр первой половины номера равна сумме цифр второй половины номера. Номер может начинаться с 0. Найти количество счастливых номеров среди всех 2N-значных билетов (1 ≤ N ≤ 20).

Ввод из файла INPUT.TXT. Единственная строка содержит значение N (1 ≤ N ≤ 20).

Вывод в файл OUTPUT.TXT. В единственной строке выводится количество счастливых номеров.

Вывод в файл OUTPUT.TXT. В единственной строке выводится количество счастливых номеров.

Пример:

входные данные (input.txt)	выходные данные (output.txt)

Переборный алгоритм применим при значениях N до 3-4. Опишем два более эффективных способа.

Вариант 1

Рассмотрим первые N цифр. Максимальным числом из N цифр является M=10^N -1. Максимальная сумма цифр K = 9N.

Заведем массив C из K+1 счетчиков. В C_i будем хранить количество чисел из диапазона от 0 до M, имеющих сумму цифр i (0 ≤ i ≤ K). В цикле от 0 до M определим значения всех счетчиков.

Количество счастливых номеров, у которых сумма цифр каждой половины номера равна i составляет C_i ². Остается найти сумму квадратов счетчиков по всем значениям i от 0 до K. Алгоритм применим при значениях N до 6-7.

Вариант 2

Снова рассмотрим первые N цифр. Обозначим через F(I, J) количество чисел из I цифр с суммой цифр J. Выведем рекуррентные соотношения для F(I, J).

· F(1, J)=1 при J =0,..., 9, т. к. одной цифрой можно получить значение от 0 до 9;

· F(1, J)=0 при J =10,..., 9N, т. к. одной цифрой невозможно получить значение 10 и больше;

· F(I +1, J) = F(I, J) + F(I, J -1) +...+ F(I, J –L), L ≤ 9, J – L ≥ 0, где первому слагаемому соответствует цифра 0 в позиции I +1, второму – цифра 1 и т. д.

По этой формуле рассчитываются значения F(I, J) для

· I = 2, …, N;

· J = 0, 1, …, 9N.

Количество счастливых номеров, у которых сумма цифр каждой половины номера равна J, составляет F(N, J)². Остается найти сумму квадратов значений F(N, J) по всем J от 0 до 9N. Время счета при этом варианте минимально.

Заметим в заключение, что при больших размерностях нужна длинная арифметика. Вместо двумерного массива можно обойтись двумя одномерными массивами, поскольку при вычислении значений функции F(I, J) требуются только два последовательных шага по I.

При N=20 получен ответ 218768894829904122626725603838896148680. Время счета менее секунды.

Многие задачи легко программируются с помощью рекурсии. И в этом случае необходима оценка трудоемкости алгоритмов.

Вернемся для примера к задаче о черепашке, рассмотренной в разделе динамического программирования. Она сводится к нахождению кратчайшего пути из левого верхнего угла матрицы C размерности M×N, заполненной числами, в правый нижний. Путь состоит из переходов по матрице направо либо вниз. Ограничимся нахождением минимальной стоимости пути без определения самого пути.

Очевидным решением является написание следующей рекурсивной функции, находящей минимальную стоимость пути от клетки матрицы с координатами (i, j) до конца.

Function F(i,j: integer): longint;

Begin

if (i=M) and (j=N) then F:=C[M,N]

else

if i=M then F:=C[i,j]+F(i,j+1)

else

if j=N then F:=C[i,j]+F(i+1,j)

else

if F(i+1,j)<F(i,j+1) then F:=C[i,j]+F(i+1,j)

else F:=C[i,j]+F(i,j+1);

End;

Ответ дает значение функции F(1,1). Уже на матрице размерами 10×10 программа работает больше 20 секунд. Дело в том, что мы выполняем полный перебор путей, многократно пересчитывая значения функции для каждой клетки матрицы. С ростом размерности матрицы трудоемкость увеличивается экспоненциально.

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

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

Программирование бинарного поиска при всей очевидности постановки связано со многими нюансами. Хотя впервые двоичный поиск был опубликован в 1946 году, полное решение, обходящее все ловушки, было опубликовано только в 1962 году.

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

.

While (high-low) > Eps do

{low и high - левая и правая границы отрезка поиска

Eps – заданная точность}

begin

low3:=(2*low+high)/3;

high3:=(low+2*high)/3;

if F(low3)>F(high3) then low:=low3

else high:=high3;

end;

Res:=(high+low)/2; {результат}

Здесь все переменные имеют одинаковый вещественный тип, а F (x) определяет значения унимодальной функции.

Улучшенным вариантом троичного поиска является метод золотого сечения, в котором вычисленные значения функции используются на следующей итерации.

Дата добавления: 2014-01-11