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

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

Форум программистов > C/C++: Для новичков > Найти максимум из всех локальных минимумов матрицы

Автор: persalena 10.12.2008, 16:34

Задача следующая: Дана матрица : строк не более 12, столбцов не более 10. Нужно найти максимум из всех локальных минимумов. Элемент матрицы называется локальным минимумом, если он строго меньше всех имеющихся у него соседей.
(соседи - элементы окружающие задынный элемент. Т.е. если элемент стоит, например, в центре, то у него 8 соседей, если в углу - то 3, и если просто скраю, то 5)

Вопрос заключается в следующем: Я создаю подпрограмму для нахождения локального минимума. Мне приходится его сравнивать со всеми окружающими его элементами через if, и при этом еще разбить на несколько случаев:
1) если элемент в углу
    1.1) в правом верхнем
    1.2)в правом нижнем
    1.3)в левом верхнем
    1.4)в левом нижнем
2) если элемент сбоку:
    2.1) слева
    2.2)справа
    2.3)сверху
    2.4)снизу
3) общий случай(когда 8 соседей)

Можно ли каким-то образом упростить этот алгоритм? Вообщем то я уверена, что можно, но как именно, додуматься не могу. Помогите пожалуйста какими-нибудь идейками.

Автор: bsa 10.12.2008, 16:45

persalena, если мне память не изменяет, то, обычно, матрицы делаются закольцованными (т.е. у каждого элемента матрицы 8 соседей)...
В любом случае, нет ничего проще. создаешь массив из 8 точек, которые определяют положение соседнего элемента относительно координат проверяемого минимума: (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0)
затем вычисляешь координаты соседа и, если они допустимые, сравниваешь с текущим элементом, если недопустимые, то переходишь к следующей точке.

Автор: persalena 11.12.2008, 18:23

А вот такой вопрос: можно ли в Си сравнивать ,например, 1 элемент матрицы с -1? Чисто теоритически ведь там должен находиться какой-либо виртуальный элемент... ну мне так кажется=)

Автор: bsa 11.12.2008, 18:49

Я не понял вопрос, но попытаюсь ответить кодом:

Код

int array[10];
int i;
for(i = 0; i < 10; ++i)
   array[i] = i;

if (array[1] > 1)
  printf("error\n");

Автор: persalena 24.12.2008, 15:56

Ну проверили мой метод решения. Оказался неверным(  Мне сказали ввести переменную К, которая будет то 1, то -1.
И сравнивать элемент с соседями по циклу в трех случаях:
1) если элемент в углу
2) если элемент сбоку
3) общий случай(когда 8 соседей)
Т.е варианты (
    1.1) в правом верхнем
    1.2)в правом нижнем
    1.3)в левом верхнем
    1.4)в левом нижнем
     2.1) слева
    2.2)справа
    2.3)сверху
    2.4)снизу)
ОБОБЩИТЬ с помощью этого самого К.
Вопрос: Как это возможно?

Автор: likehood 24.12.2008, 16:34

Код


// функция проверяет, является ли элемент matrix[row][col] локальным min
bool isLocalMinimum(int matrix[12][10], int row, int col)
{
    bool isMinimum = true;
    for (int i=row-1; i<=row+1; i++)
        for (int j=col-1; j<=col+1; j++)
        {
            if (i==row && j==col)
                continue;
            
            if (i<0 || j<0 || i>=12 || j>=10)
                continue;

            if (matrix[i][j] <= matrix[row][col]) {
                isMinimum = false;
                goto end_loop;
            }
        }

end_loop:
    return isMinimum;
}

Автор: persalena 24.12.2008, 17:03

Ну вообщем-то я так и делала) Сказали переделать... k вставить вместо +1 и -1. и оно меняться должно в зависимости от чего-то...

Автор: likehood 24.12.2008, 17:09

можно конечно и так сделать, но не понятно, чем это принципиально отличается от первого варианта

Код


bool isLocalMinimum(int matrix[12][10], int row, int col)
{
    bool isMinimum = true;
    for (int k1=-1; k1<=1; k1++)
        for (int k2=-1; k2<=1; k2++)
        {
            if (k1==0 && k2==0)
                continue;
            
            int i = row+k1, j = col+k2;
            if (i<0 || j<0 || i>=12 || j>=10)
                continue;

            if (matrix[i][j] <= matrix[row][col]) {
                isMinimum = false;
                goto end_loop;
            }
        }

end_loop:
    return isMinimum;
}

Автор: persalena 24.12.2008, 17:12

Вот и мне тоже непонятно. Причем k должен быть только один. И как я поняла в программе будет изобилие if-ов

Автор: Dmi3ev 24.12.2008, 17:25

а если так???

Код


//---------------------------------------------------------------------------
#include <iostream.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
int main()
{
int n,m;
int **mas ;
const int k=1;
randomize();
cout<<"rows=";
cin>>n;
cout<<endl;
cout<<"coloumns=";
cin>>m;
cout<<endl;
mas=new int*[m];
for (int j=0; j<m; j++)
 mas[j]=new int [n];

for (int i=0; i<n; i++)
 for (int j=0; j<m; j++)
  *(*(mas+j)+i)=random(100)-50;

cout<<endl<<"Matrix:"<<endl;
for (int i=0; i<n; i++)
 {
  for (int j=0; j<m; j++)
   cout<<*(*(mas+j)+i)<<"; ";
  cout<<endl;
 }

for (int i=0; i<n; i++)
 {
  for (int j=0; j<m; j++)
   {
    bool min=true;
    for (int i1=i-k; i1<=i+k; i1++)
     for (int j1=j-k; j1<=j+k; j1++)
      {
       if (i1>=0 && i1<n)
        {
         if (j1>=0 && j1<m)
          {
           if ((*(*(mas+j)+i))>=(*(*(mas+j1)+i1)))
            {
             if (i1==i && j1==j)
              continue;
             else
              min=false; break;
            }
          }
        }
      }
    if (min)
     cout<<"optimum: A["<<i+1<<"] ["<<j+1<<"]="<<*(*(mas+j)+i)<<endl;
   }
 }
char s;
cin>>s;
        return 0;
}
//---------------------------------------------------------------------------

Автор: likehood 24.12.2008, 17:30

Цитата(Dmi3ev @ 24.12.2008, 17:25

)

const int k=1;

Добавлено через 1 минуту и 19 секунд
лучше тогда вот так: const int odin = 1; smile

Автор: Dmi3ev 24.12.2008, 17:35

likehood, да я просто предложил smile

заодно у меня массив какой угодно (n x m), может пригодится smile

а может и нет ... smile

че ты глумишься ??? smile

Автор: likehood 24.12.2008, 17:53

Цитата(Dmi3ev @ 24.12.2008, 17:35

)

че ты глумишься ???

забей

просто понравилось как ты выполнил требование использовать переменную k

Автор: Dmi3ev 24.12.2008, 18:17

к вообще там ни в рот, ни в попу smile

поэтому и прилепил его... вот так вот забавно...
likehood, да я просто прогу написал smile

а persalena скорее всего этого и хотела... smile

для прикола попрошу:
persalena, выложи свой код, который был до нас с likehood smile

если он есть smile

мне просто кажется, что его нет... smile

потому что, если бы он был, было бы логично выложить его и спросить, чего там переделать, чтобы так-то, так-то...

Автор: persalena 24.12.2008, 18:30

Код

#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include<stdio.h>
# define n 10
#define m 12
#define u 120 
 min(float a[n][m], int i, int j, int st, int s)
 {
 int k,l,f,o;
 o=a[i][j];
 for(k=i-1;k<=i+1;k++)
   {
   for(l=j-1;l<=j+1;l++)
     {
      if(k>=0&&k<=s&&l>=0&&l<=st&&(k!=i||l!=j))
       if(a[i][j]>=a[k][l])
       f=1;

     }
   }
   return f;
  }

     float maxim (float *b, int h)
     {
     int x,y;
     float t;
     t=b[0];
     for(x=0;x<(h-1);x++)
       if(t<b[x+1])
       t=b[x+1];
     return t;
     }
     
 
     void vvod(float a[n][m], int s,int st)
     {
     int p,q;
     for(p=0;p<s;p++)
      {
      for(q=0;q<st;q++)

      scanf("%f",&a[p][q]);
      }
     }

void main()
{int i,j,h,s,st; h=0;
float a[n][m],b[u],jk, t;
printf("\nvvedite k-vo strok\n");
scanf("%i", &s);
printf("vvedite k-vo st-cov\n");
scanf("%i", &st);
printf("vvedite matricy\n");
vvod(a,s,st);
for(i=0;i<s;i++)
{
for(j=0;j<st;j++)
{if(min(a,i,j,st,s)!=1)
{
b[h]=a[i][j];
h++;}}
}
t=maxim(b,h);
if (h!=0)
printf("\n%f\n",t);
getch();
}

Добавлено через 49 секунд
Тут не переделывать надо, а заново писать! Метод решения не тот. а так все работает)

Автор: Dmi3ev 24.12.2008, 19:59

persalena, извиняюсь за

Цитата

мне просто кажется, что его нет..

просто здесь много залётных, которые словами бросаются, я это, я то, но не получается ничего, а на самом деле ничего и нет...