Задача "Ёжик" (а точнее её решение),
опубликованная в предыдущем выпуске рассылки,
вызвала шквал эмоций со стороны читателей. В
связи с этим, в этом номере представляем два
более корректных и рациональных решения данной
задачи.
Ёжик
(3 уровень)
Условие:
План прямоугольного сада размером mxn состоит
из квадратных зон. В каждой зоне растёт по дереву.
С каждого дерева любой зоны могут упасть
несколько яблок.
В левом верхнем квадратике находится ёжик,
который должен дойти до правого нижнего
квадратика. В саду существуют ограничения
относительно способа передвижения: ёжик может
двигаться из текущего квадратика только в один
из двух соседних правый либо нижний.
Составьте программу, которая вычисляет
максимальное количество яблок, которое может
собрать ёжик, передвигаясь к нужному квадратику.
Технические
условия: План сада
задан таблицей apples содержащей m строк и n
столбиков. Элемент apples[i,j] таблицы указывает
количество яблок, упавших с дерева в зону с
координатами i,j.
Текстовый файл "input.txt" содержит в первой
строке числа m,n разделённые пробелом. В каждой из
следующих m строк содержится по n чисел apples[i,j]
разделённых пробелами.
Файл "output.txt" должен содержать одно
натуральное число.
Примеры
файлов:
Input.txt
Output.txt
3 3
1 2 3
1 2 3
1 2 3
12
Решение 1:(by
Andrei Bejenari [andrei.bejenari@wanadoo.fr])
---------- cut ----------
Классическая задача, которая решается в две
строчки динамическим программированием (более
того не требующего дополнительной памяти, что не
так часто), решена рекурсией!!! Да, может для
матрицы 10x10 back-tracking и пойдет, но а если она 100x100, то
сколько лет понадобится опубликованному Вами
алгоритму, чтобы закончить свою работу?
---------- cut ----------
const
input = 'input.txt';
output = 'output.txt';
MaxN = 100;
var
apples : array [0..MaxN,0..MaxN] of word;
m,n,i,j : integer;
fi,fo : text;
function max(a,b : word) : word;
begin
if a>b then max:=a
else max:=b
end;
begin
assign(fi,input); reset(fi);
assign(fo,output); rewrite(fo);
readln(fi,m,n);
for i:=1 to m do
for j:=1 to n do read(fi,apples[i,j]);
for i:=1 to m do
for j:=1 to n do inc(apples[i,j],max(apples[i-1,j],apples[i,j-1]));
---------- cut ----------
Почитал
предлагаемое решение задачи про ежика... Тихий
ужас ;)
Автор, наверное, не знаком с жесткими
ограничениями, которые установлены на
большинстве приличных олимпиад (т.е. выше
городского уровня). Перебор - штука
многофункциональная, но только при матрице
скромных размеров. Потому что временнАя
сложность алгоритма получается порядка 2^(m+n).
Лучше будет применить динамическое
программирование...
---------- cut ----------
var
f: text;
m, n, i, j, t, s: word;
a: array[0..1, 0..5000] of longint;
begin
assign(f, 'input.txt');
reset(f);
readln(f, m, n);
s := n * 4 + 1; { sizeOf(longint) = 4 }
fillChar(a[0], s, $00);
fillChar(a[1], s, $00);
for i := 1 to m do begin
move(a[1], a[0], s);
for j := 1 to n do
begin
read(f, t);
if a[0, j] >= a[1, j - 1] then
a[1, j] := a[0, j] + t
else
a[1, j] := a[1, j - 1] + t;
end;
readln(f);
end;
close(f);
assign(f, 'output.txt');
rewrite(f);
writeln(f, a[1, n]);
close(f);
end.
Рассылки проекта Sapisoft:
Всегда
рады видеть Вас на нашем сайте. Жду ваших
предложений и замечаний, Шамис Алексей
