Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей очередная задача www.thl.narod.ru


Задача 3
Максимальная подматрица.
Дана матрица N*N из целых двузначных чисел. Требуется найти подматрицу с тем
условием, чтобы сумма чисел этой подматрицы была максимальной.
Входной файл (input.txt):

В первой строке содержится количество строк исходной матрицы.
В последующих N строках записана сама матрица.

Выходной файл:
Сумма найденной подматрицы.

Пример:
input.txt

-----начало файла-----
5
3 0 –7 14 20
–5 17 99 –99 0
11 –1 5 0 10
-9 10 34 78 –53
3 -27 15 –2 -10
-----конец файла-----

output.txt

-----начало файла-----
159
-----конец файла-----

Комментарий: 17+99+(-1)+5+10+34 = 159

Удач в решении задач. До следующего выпуска.

Решение:

Идея алгоритма: вначале ищем первый положительный элемент в последовательности. Если такого не окажется, то наибольший из просмотренных и будет решением. Если такой элемент нашелся, то считаем, что текущая сумма и максимальная равны этому элементу. Начинаем просматривать эту последовательность до конца. На каждом шаге увеличиваем текущую сумму на текущий элемент. Если текущая сумма оказаласть отрицательной - зануляем ее. Кроме того, если значение текущей суммы окажется больше максимальной, то максимальную сумму
считаем равной текущей. Вот рабочий код:
var min,j,maxsum,sum,n: longint;
inp, outp: text;
begin
assign(inp,'input.txt');
reset(inp);
readln(inp);
read(inp,min);
while (not eof(inp))and(min<=0)do
begin
read(inp,j);
if j>min then min:=j;
end;
maxsum:=min;
sum:=min;
while not eof(inp) do
begin
read(inp,j);
inc(sum,j);
if sum>maxsum then maxsum:=sum;
if sum<0 then sum:=0;
end;
assign(outp,'output.txt');
rewrite(outp);
write(outp,maxsum);
close(inp);
close(outp);
end.
В избранное