матрицы, нахождение в матрице подматрицы Опции

[ted]

Помогите решить задачу, очень надо.
Дана матрица а(m/n). Найдите в ней прямоугольную подматрицу, сумма элементов которой максимальна. Задачу решить с помощью рекурсии.

[klem4]

Отчет очевиден - матрица m * n от элемента [0,0].

Чего-то в условии хватает.

Сообщение отредактировано: klem4 - 22.03.2009 18:34

[volvo]

Неправда... Не все так очевидно:

-1 -2 -3
-5  2  3
 6  7  8

[klem4]

volvo, точно, поторопился я с выводом.

Если у автора есть тестовые примеры пусть приводит, особо не тестил, но думаю ошибок быть не должно.

const max_rows = 10; max_cols = 10;
type tarr = array[1..max_rows, 1..max_cols] of integer;

procedure init( var arr: tarr );
var i, j: integer;
begin
  randomize;
  for i := 1 to max_rows do
    for j := 1 to max_cols do arr[i, j] := random(21) - 10
end;

procedure dump( const arr: tarr; const left_r, left_c, rows, cols: integer);
var
  i, j, stop_r, stop_c: integer;
begin
  stop_r := left_r + rows - 1;
  if stop_r > max_rows then stop_r := max_rows;

  stop_c := left_c + cols - 1;
  if stop_c > max_cols then stop_c := max_cols;

  for i := left_r to stop_r do begin
    writeln;
    for j := left_c to stop_c do write( arr[i, j]:4 );
  end;
  writeln
end;

function sum ( const arr: tarr; const left_r, left_c,
  rows, cols: integer ): integer;
var
  i, j, stop_r, stop_c, _sum: integer;
begin
  _sum := 0;

  stop_r := left_r + rows - 1;
  if stop_r > max_rows then stop_r := max_rows;

  stop_c := left_c + cols - 1;
  if stop_c > max_cols then stop_c := max_cols;

  for i := left_r to stop_r do
    for j := left_c to stop_c do inc(_sum, arr[i, j]);
  sum := _sum;
end;

procedure solve( const arr: tarr; var r_row, r_col,
  rr_count, rc_count: integer);
var
  last_max, rows, cols, lr, lc, curr_sum: integer;
begin
  last_max := -maxint;
  for rows := max_rows downto 1 do
   for cols := max_cols downto 1 do
    for lr := 1 to max_rows - rows + 1 do
     for lc := 1 to max_cols - cols + 1 do begin
       curr_sum := sum( arr, lr, lc, rows, cols );
       if  curr_sum > last_max then begin
         last_max := curr_sum;
         r_row := lr;
         r_col := lc;
         rr_count := rows;
         rc_count := cols;
       end;
     end;
end;

var arr: tarr; rows, cols, r_row, r_col, rr_cnt, rc_cnt: integer;

begin
  init(arr);
  dump(arr, 1, 1, max_rows, max_cols);
  solve(arr, r_row, r_col, rr_cnt, rc_cnt);
  dump(arr, r_row, r_col, rr_cnt, rc_cnt);
end.

[volvo]

Рекурсивно - вот так, например:

const
  max_rows = 3; max_cols = 3;
type
  tarr = array[1 .. max_rows, 1 .. max_cols] of integer;

procedure print(const arr: tarr; si, sj, fi, fj: integer);
var i, j: integer;
begin
  for i := si to fi do begin
    for j := sj to fj do write(arr[i, j]:4);
    writeln;
  end;
end;

procedure run(const arr: tarr; var st_i, st_j, fn_i, fn_j: integer);

  var
    max_sum: integer;

  procedure solve(si, sj, fi, fj: integer);

    procedure check_sum;
    var i, j, s: integer;
    begin
      s := 0;
      for i := si to fi do
        for j := sj to fj do s := s + arr[i, j];
      if s > max_sum then begin
        st_i := si; st_j := sj; fn_i := fi; fn_j := fj;
        max_sum := s;
      end;
    end;

  begin
    if (si > max_cols) or (sj > max_rows) or
       (fi > max_cols) or (fj > max_rows) then exit;
    check_sum;

    solve(si, sj, fi, fj + 1);
    solve(si, sj, fi + 1, fj);
    solve(si, sj + 1, fi, fj);
    solve(si + 1, sj, fi, fj);
  end;

begin
  max_sum := -maxint;
  solve(1, 1, 1, 1);
end;

const
  arr: tarr = (
    (-1, -2, 3),
    (-6,  2, 23),
    (-5,  7, 8)
  );

var
  st_i, st_j, fn_i, fn_j: integer;

begin
  run(arr, st_i, st_j, fn_i, fn_j);
  print(arr, st_i, st_j, fn_i, fn_j);
end.

[ted]

Спасибо !!!!!!!!!!

[ted]

У меня ещё небольшой вопрос по этой задче, как сделать так чтобы она считала суммы элементов каждой подматрицы,сравнивала их и выводила самый большой. Зарание спасибо!!!!!