const n = 8, m = 8; var A: array[1..n,1..m] of integer; i, j, sum, product: integer; isnotnull: boolean; begin randomize; writeln('Случайная матрица:'); for i:=1 to n do begin for j:=1 to m do begin A[i,j] := random(51) - 25; write(A[i,j]:5); end; writeln; end; sum := 0; for i:=1 to n do if A[i,n-i+1] < 0 then sum := sum + A[i,n-i+1]; writeln('Сумма отрицательных элементов побочной диагонали = ', sum); product := 1; isnotnull := False; for i:=1 to n-1 do for j:=2 to n do if (j > i) and (A[i,j] <> 0) then begin isnotnull := True; product := product * A[i,j]; end; if isnotnull writeln('Произведение ненулевых элементов в области выше главной диагонали = ', product) else writeln('Ненулевых элементов в области выше главной диагонали нет.', product); readln; end.
Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.
Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.
Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".
Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k]. Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.
Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2. Сортировку можно сделать за время T2(n) < b nlogn < bn^2 Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2
что-то типа этого:
const n = 8, m = 8;
var
A: array[1..n,1..m] of integer;
i, j, sum, product: integer;
isnotnull: boolean;
begin
randomize;
writeln('Случайная матрица:'); for i:=1 to n do begin
for j:=1 to m do begin
A[i,j] := random(51) - 25;
write(A[i,j]:5);
end;
writeln;
end; sum := 0;
for i:=1 to n do
if A[i,n-i+1] < 0 then
sum := sum + A[i,n-i+1];
writeln('Сумма отрицательных элементов побочной диагонали = ', sum); product := 1;
isnotnull := False;
for i:=1 to n-1 do
for j:=2 to n do
if (j > i) and (A[i,j] <> 0) then begin
isnotnull := True;
product := product * A[i,j];
end;
if isnotnull
writeln('Произведение ненулевых элементов в области выше главной диагонали = ', product)
else
writeln('Ненулевых элементов в области выше главной диагонали нет.', product); readln;
end.