Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] Количество локальных максимумов

Автор: golden 12.11.2006, 20:13

Задача: Дан массив [8,8].Найти количество локальных максимумов массива.

Требуется самое простое решение задачи. Заранее благодарю. Golden

Автор: powerfox 12.11.2006, 20:38

А что такое локальный максимум?

Автор: volvo877 12.11.2006, 21:08

Локальный максимум матрицы - элемент, который больше всех своих соседей...

Автор: powerfox 12.11.2006, 22:34

А соседи - числа и по строкам и по столбцам? И по диагонале?

93445
23232
23232

А11 - максимум? Так как рядом 3-3-2?

Автор: golden 13.11.2006, 07:31

Вы мне программу скиньте пожалуйсто!

Автор: powerfox 13.11.2006, 13:53

golden, а ты объясни чего надо, я и скину. Тут писанины на 2 минуты.
Выходит, что надо сравнивать Аnn с А(n+-1)n и c Аn(n+-1)?

Автор: Alexeis 13.11.2006, 14:40

Цитата(powerfox @ 13.11.2006, 13:53

)

Выходит, что надо сравнивать Аnn с А(n+-1)n и c Аn(n+-1)?

Ну поскольку это матрица, то соседей либо 8 либо 4 (в зависимости от того как смотреть)

Автор: golden 13.11.2006, 15:03

2powerfox\да ты прав:Выходит, что надо сравнивать Аnn с А(n+-1)n и c Аn(n+-1).Вот это и надо сделать только я незнаю как.

Автор: volvo877 13.11.2006, 17:29

Код

const n = 8;
var
  a: array[1 .. n, 1 .. n] of integer;
  i, j, ix, iy: integer;
  bad: boolean;

  max_amount: integer;

begin


  for i := 1 to n do begin
    writeln('line #', i);
    for j := 1 to n do begin
      writeln('a[', i, ',', j, '] = ');
      readln(a[i, j]);
    end;
  end;


  max_amount := 0; { <--- Это то, что ты ищешь}

  for i := 1 to n do
    for j := 1 to n do begin
      bad := false;
      for ix := -1 to 1 do
        for iy := -1 to 1 do
          if (ix * iy = 0) and
             ((i + ix) > 0) and ((i + ix) <= n) and
             ((j + iy) > 0) and ((j + iy) <= n) and
             (a[i, j] < a[i+ix, j+iy]) then bad := true;

      if not bad then inc(max_amount);
    end;

  writeln('local max count: ', max_amount);

end.

Автор: powerfox 13.11.2006, 17:46

Вот код. Внимательно проверь индексы.

Код


program local_maximum;
var
matrix:Array[1..8,0..8] of Integer;
temp,i,j,strings,stolb:Integer;

count_max:Integer;
begin
count_max:=0;
Writeln('');

for j:=1 to 8 do
  begin
  for i:=1 to 8 do
    read(matrix[j][i]);
  readln;
  writeln ('Enter the next string:');
  end;
readln;

{"Внутренняя" матрица}
for j:=2 to 7 do
  for i:=2 to 7 do
  if (matrix[j][i]>matrix[j][i-1])and(matrix[j][i]>matrix[j][i+1])and(matrix[j][i]>matrix[j-1][i])and(matrix[j][i]>matrix[j+1][i]) then
      if (matrix[j][i]>matrix[j-1][i-1])and(matrix[j][i]>matrix[j+1][i+1])and(matrix[j][i]>matrix[j+1][i-1])and(matrix[j][i]>matrix[j+1][i+1]) 
      inc(count_max);

{Верхняя строка без углов}
j:=1;   
for i:=2 to 7 do
 if (matrix[j][i]>matrix[j][i-1])and(matrix[j][i]>matrix[j][i+1])and(matrix[j][i]>matrix[j+1][i]) then
      inc(count_max);


{Нижняя строка без углов}
j:=strings;   
for i:=2 to 7 do
 if (matrix[j][i]>matrix[j][i-1])and(matrix[j][i]>matrix[j][i+1])and(matrix[j][i]>matrix[j+1][i]) then
      inc(count_max);

{Левый столбец без углов}
i:=1;
for j:=2 to 7 do
if (matrix[j][i]>matrix[j][i+1])and(matrix[j][i]>matrix[j-1][i])and(matrix[j][i]>matrix[j+1][i]) then
      inc(count_max);

{Правый столбец без углов}
i:=8;
for j:=2 to 7 do
if (matrix[j][i]>matrix[j][i-1])and(matrix[j][i]>matrix[j-1][i])and(matrix[j][i]>matrix[j+1][i]) then
      inc(count_max);

{Углы}
if (matrix[1][1]>matrix[2][1])and(matrix[1][1]>matrix[1][2])and(matrix[1][1]>matrix[2][2]) then
   inc(count_max);

if (matrix[1][8]>matrix[1][7])and(matrix[1][8]>matrix[2][8])and(matrix[1][8]>matrix[2][7]) then
   inc(count_max);

if (matrix[8][1]>matrix[8][2])and(matrix[8][1]>matrix[7][1])and(matrix[8][1]>matrix[7][2]) then
   inc(count_max);
if (matrix[8][8]>matrix[8][7])and(matrix[8][8]>matrix[7][8])and(matrix[8][8]>matrix[7][7]) then
   inc(count_max);


writeln('Num of local maximums is',count_max);

end.

Автор: powerfox 13.11.2006, 18:02

volvo877, красивое решение, но нерабочее. У тебя там с этим наворотом bad проблемы.

Автор: likehood 13.11.2006, 18:18

чуть подправил решение volvo877:

Код


const n = 8;    
var    
  a: array[1 .. n, 1 .. n] of integer;    
  i, j, ix, iy: integer;    
  bad: boolean;    
  max_amount: integer;    
begin    
  for i := 1 to n do begin    
    writeln('line #', i);    
    for j := 1 to n do begin    
      writeln('a[', i, ',', j, '] = ');    
      readln(a[i, j]);    
    end;    
  end;    
  max_amount := 0; { <--- Это то, что ты ищешь}    
  for i := 1 to n do    
    for j := 1 to n do begin    
      bad := false;    
      for ix := -1 to 1 do    
        for iy := -1 to 1 do    
          if (not (ix=0 and iy=0)) and      { <<<< чтобы не сравнивать с самим собой }
             ((i + ix) > 0) and ((i + ix) <= n) and    
             ((j + iy) > 0) and ((j + iy) <= n) and    
             (a[i, j] < a[i+ix, j+iy]) then bad := true;    
      if not bad then inc(max_amount);    
    end;    
  writeln('local max count: ', max_amount);    
end.

Автор: golden 13.11.2006, 18:51

Ок спасибо разберусь

Автор: volvo877 13.11.2006, 18:59

Цитата(powerfox @ 13.11.2006, 17:02

)

красивое решение, но нерабочее.

Правда? А ты проверял?
Я вот прогнал на матрице - как положено, так и отрабатывает.

Код


const
  n = 4;
  a: array[1 .. n, 1 .. n] of integer = (
    (1, 2, 3, 4),
    (1, 4, 6, 3),
    (8, 2, 5, 2),
    (3, 4, 5, 6)
  );

4 локальных максимума. Показать, или найдешь сам?
Приведи мне матрицу, на которой МОЮ программу проверял ТЫ...

Добавлено @ 19:03
baronp, теперь вопрос к тебе: чем тебе помешало сравнение с самим собой? Ты считаешь, что это может повлиять на правильность результата? Могу тебя огорчить: ты не разобрался в логике работы программы, в следующий раз сначала разберись, а потом будешь критиковать...

К тому же с твоим исправлением будут сравниваться и диагональные элементы (рассказать, почему?), а этого (судя по посту автора) делать не нужно:

Цитата(golden @ 13.11.2006, 14:03

)

Аnn с А(n+-1)n и c Аn(n+-1)

Автор: powerfox 13.11.2006, 19:16

volvo877, не чиркай красным, а то это харазительно:

Твой код:

Цитата

Код


 for i := 1 to n do    
    for j := 1 to n do begin    
     [color=red] bad := false;    [/color]
      for ix := -1 to 1 do    
        for iy := -1 to 1 do    
          if (ix * iy = 0) and    
             ((i + ix) > 0) and ((i + ix) <= n) and    
             ((j + iy) > 0) and ((j + iy) <= n) and    
           [color=red]  (a[i, j] < a[i+ix, j+iy]) then bad := true;    [/color]
     [color=red] if not bad then inc(max_amount);[/color]    
    end;

У тебя true устанавливается, даже если выполняется условие для одного соседнего элемента.
Для матрицы
1 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Ответ получился 54.

Цитата(volvo877 @ 13.11.2006, 19:59

)

К тому же с твоим исправлением будут сравниваться и диагональные элементы (рассказать, почему?), а этого (судя по посту автора) делать не нужно:

Автор сам не знает, что ему надо (кроме рещённой задачи). По диагонале надо сравнивать:

Автор: likehood 13.11.2006, 23:33

Цитата(volvo877 @ 13.11.2006, 19:59

)

baronp, теперь вопрос к тебе: чем тебе помешало сравнение с самим собой? Ты считаешь, что это может повлиять на правильность результата?

в данном случае не помешает, только вот вопрос: что выведет твоя программа, если матрица будет заполнена нулями?
Специально проверял: выведет n*n, хотя максимумов здесь не будет, поскольку

Цитата(volvo877 @ 12.11.2006, 22:08

)

Локальный максимум матрицы - элемент, который больше всех своих соседей...

Чтобы учитывать равентство соседних элементов, нужно последнее условие заменить на

Код


a[i, j] <= a[i+ix, j+iy]

Именно из-за этого я исключил сравнение с самим собой, поскольку иначе неравенство всегда будет давать bad:=true, только неравенство забыл подправить (каюсь).

Цитата(volvo877 @ 13.11.2006, 19:59

)

К тому же с твоим исправлением будут сравниваться и диагональные элементы (рассказать, почему?)

Так оно и задумывалось, видимо я неправильно понял условие задачи. Надеюсь, автор разберется какой ему нужен максимум и сам доделает задачу.

Автор: golden 15.11.2006, 07:42

Всё ОК! задача сдана. Я получил зачёт. спасибо всем сочуствующем!