Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Локальный минимум 
:(
    Опции темы
X
Дата 9.12.2005, 01:40 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Всем привет!
Опять нужна ваша помощь, не могу разобраться. Имеется матрица размером m на n. Надо найти количество локальных минимумов матрицы. Локальный минимум, это элемент, который меньше все соседних элементов, его окружающих.
  Вверх
blackofe
Дата 9.12.2005, 02:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 173
Регистрация: 29.11.2005

Репутация: 4
Всего: 4
навскидку.

Код
const int MAX_X = 3;
const int MAX_Y = 4;

int a[MAX_X][MAX_Y] = {
    {    1,    3,    12,    -9 },
    {    5,    24,    0,    54 },
    {    -1,    10,    4,    -4 }
};

// check x+x_offset row
const bool checkXrow(const int x, const int y, const int x_offset)
{
    // y-1 col
    if(y > 0 && a[x+x_offset][y-1] < a[x][y])
        return true;
    // y col
    if(a[x+x_offset][y] < a[x][y])
        return true;
    // y+1 col
    if(y < MAX_Y-1 && a[x+x_offset][y+1] < a[x][y])
        return true;
    return false;
}

// if any around more, than the element(x, y), return false
const bool IsLocalMin(const int x, const int y)
{
    // x-1 row
    if(x > 0 && checkXrow(x, y, -1))
        return false;
    // x row
    if(checkXrow(x, y, 0))
        return false;
    // x+1 row
    if(x < MAX_X-1 && checkXrow(x, y, 1))
        return false;
    return true;
}

int main(int argc, char* argv[])
{
    // print matrix
    for(int i = 0; i < MAX_X; ++i) {
        for(int j = 0; j < MAX_Y; ++j)
            cout << a[i][j] << "\t";
        cout << endl;
    }
    // calculate number of local minimums
    int count = 0;
    for(int i = 0; i < MAX_X; ++i)
        for(int j = 0; j < MAX_Y; ++j)
            if(IsLocalMin(i, j))
                count++;
    // print number of local minimums
    cout << "number of local minimums: " << count << endl;
    return 0;
}


идея простая: перебрать все элементы и каждый проверить на вшивость - является ли он локальным минимумом (по ходу дела проверяя выход за границы массива).

результат работы программы:

Код
1       3       12      -9
5       24      0       54
-1      10      4       -4
number of local minimums: 4
Press any key to continue


не отрицаю наличия более красивого решения. очень спешил smile.

Это сообщение отредактировал(а) blackofe - 9.12.2005, 02:19
PM MAIL   Вверх
sergejzr
Дата 9.12.2005, 02:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Грубо говоря у нас 8 соседей (исключения - значения на границах)
Код

/*
   111
   101
   111

*/

bool isLocalMinimum(int *matrix, int y, int i, int maxX, int maxY)
{
  int value=matrix[x][y];
 /*Проверка границы,      затем проверка соседа*/
  if(x>0            &&  value>matrix[x-1][y]  ) return false;
  if(y>0            &&  value>matrix[x]  [y-1]) return false;
  if(x<maxX         &&  value>matrix[x+1][y]  ) return false;
  if(y<maxY         &&  value>matrix[x]  [y+1]) return false;
  if(y>0            &&  value>matrix[x-1][y-1]) return false;
  if(x>0&&y<maxY    &&  value>matrix[x-1][y+1]) return false;
  if(x<maxX&&y<maxY &&  value>matrix[x+1][y+1]) return false;
  if(x<maxX&&y>0    &&  value>matrix[x+1][y-1]) return false;

}

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


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
X
Дата 9.12.2005, 02:28 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Спасибо большое буду разбираться!!!
  Вверх
sergejzr
Дата 9.12.2005, 02:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Вот, товарищ опередил smile

Это конечно не алгоритм, а перебор. Если у тебя массив представляет собой двумерную функцию, существуют более "быстрые" алгоритмы поиска локальных минимумов. Почти все представляют собой спуск в обратном направлении градиента. Разница в основном в нахождении оптимальной ширины шага.
Добавлено @ 02:35
Хммм. ещё можно отбрасывать "проверенные" элементы, которые точно не могут быть локальным минимумом типа как игра в "кораблики". Нашёл минимум, закрасил всех его соседей идт.


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
X
Дата 9.12.2005, 04:35 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
sergej.z мне необходимо только это:
Код

bool isLocalMinimum(int *matrix, int y, int i, int maxX, int maxY)
{
  int value=matrix[x][y];
 /*Проверка границы,      затем проверка соседа*/
  if(x>0            &&  value>matrix[x-1][y]  ) return false;
  if(y>0            &&  value>matrix[x]  [y-1]) return false;
  if(x<maxX         &&  value>matrix[x+1][y]  ) return false;
  if(y<maxY         &&  value>matrix[x]  [y+1]) return false;
}


проверили границы и соседей, а потом что? Как найти кол-во лок. минимумов? Объясни поподробнее плиз smile
  Вверх
sergejzr
Дата 9.12.2005, 14:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Дальше разбирать не буду. И так уже достаточно подробно.
Код

void findAll(int *matrix, int maxX, int maxY)
{
 int count=0;
  for(int x=0;x<=maxX;x++)
    for(int y=0;y<=maxY;y++)
      if(isLocalMinimum(matrix, x, y, maxX, maxY))
        {
         cout<<"Local minimum "<<matrix[x][y]<<" at ("<<x<<","<<y<<")"<<endl;
         count++;
        }
   cout<<"There are "<<count<<" local minimas in the matrix"<<endl;
}



--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
blackofe
Дата 9.12.2005, 18:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 173
Регистрация: 29.11.2005

Репутация: 4
Всего: 4
sergej.z
мой первоначальный вариант именно таким и был, просто я все это выстроил по вертикали, и мне не очень понравилось, как это выглядит. вот я и вывел проверку по горизонтали в отдельную функцию. правда из-за этого у меня получилось 9 проверок (включая проверку на себя) - заломало проверять.

про "закрашивание" мысль хорошая. усложнило бы алгоритм (это ж их запоминать надо, или делать "слепок" матрицы с "закрасками"), но повысило бы эффективность.
PM MAIL   Вверх
sergejzr
Дата 9.12.2005, 19:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Если построчно проверять, то конечно "прошедшие" уже не надо проверять будет. то есть проверка только один раз каждого квадрата.

Кстати, есть алгоритм для игры в "кораблики"? ИМХО - сюда бы точно подошёл smile) Конечно при случайно разбросанных кораблях - тяжело, но кое какие оптимизации при закрашивании можно сделать..


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
blackofe
Дата 9.12.2005, 19:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 173
Регистрация: 29.11.2005

Репутация: 4
Всего: 4
sergej.z
прошедшие проверять на "локальную минимумость" было бы не нужно, но возникла бы необходимость проверять на "прошедшесть" smile. т.е. "прошел? - значит на локальный минимум не проверяем". и понятно, что проверка на "прошедшесть" более быстра, чем на локальный минимум.
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1188 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.