Задача 16.
Дано положительное целое число К и К целых чисел А(1),...,А(К). Вычислить
а) наибольшее,
b) наименьшее,
c) наиболее близкое к нулю,
d) наиболее близкое к заданному числу Р возможное значение суммы
S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N),
где 1<=М<=N<=К.
Примечание. Число К столь велико, что числа А(1),А(2), ..., А(К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К2 даже простейших операций не хватает времени.
|
Решение задачи 16.
а) Пусть в переменной MaxEndingHere хранится сумма элементов максимального подвектора, заканчивающегося в позиции i-1. Для того, чтобы MaxEdingHere начала хранить сумму элементов максимального подвектора, оканчивающегося в позиции i, необходимо выполнить следующую операцию присваивания:
MaxEndingHere:=max(MaxEndingHere+A[i],A[i]);
а для того, чтобы найти максимальную сумму MaxSoFar элементов подвектора, встретившегося до позиции i, надо выполнить операцию
MaxSoFar:=Max(MaxSoFar, MaxEndingHere).
Программа:
MaxSoFar:=A[1];
MaxEndingHere:=A[1];
for i:=2 to K do begin
MaxEndingHere:=max(MaxEndingHere+A[i],A[i]);
MaxSoFar:=max(MaxSoFar, MaxEndingHere);
end.
b) Для поиска минимальной суммы мы можем сначала умножить все элементы массива A на -1, а затем искать, как и в пункте а, максимальную сумму.
c) Заведем массив C[0..k] такой, что C[i]=A[1]+ ... +A[i], C[0]=0. Заметим, что
S(M,N)=C[N]-C[M-1].
Сумма S(M,N) элементов вектора A[M]+ ... +A[N] равна нулю, если C[M-1]=C[N]. Исходя из этого соображения возьмем массив C, отсортируем его, затем найдем минимальную по модулю разность двух соседних элементов отсортированного массива (т.е. найдем два наименее отличающихся элемента массива C). Эта разность как раз и будет наиболее близким к нулю значением суммы S(M,N).
d) Как и в предыдущем пункте сформируем массив C, затем его отсортируем. Нам надо найти в этом массиве два элемента C[i] и C[j], значение разности которых наиболее близко к P. Пусть массив C упорядочен по неубыванию, и i и j - индексы текущих просматриваемых элементов массива C.
i:=1; j:=1;
MinSoFar:=abs(C[2]-C[1]-P); {Текущее значение минимальной разности}
while (i<=k) and (j<=k) do begin
if C[j]-C[i]>P
then i:=i+1; {увеличиваем вычитаемое}
else j:=j+1; {увеличиваем уменьшаемое}
if i<>j {если это не один и тот же элемент массива C}
then MinSoFar:=min(MinSoFar, abs(C[j]-C[i]-P));
end;
О применении аналогичных пунктам а)-d) методов решения задач - см. задачу 12 главы РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ И ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.
|
