Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
AliceUchiha
0 / 0 / 0
Регистрация: 30.11.2017
Сообщений: 19
1

Найти количество локальных минимумов в двумерном массиве

09.05.2018, 16:30. Просмотров 1020. Ответов 9
Метки нет (Все метки)

Нужно найти локальные минимумы в двумерном массиве и посчитать их количество. Локальный минимум это минимальный элемент среди всех вокруг стоящих соседей.Пример локального минимума:
4 4 4 4
4 1 4 4
4 4 4 1
Здесь 2 локальных минимума и оба =1.

Собсна код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "stdafx.h"
int Number_of_local_minima(int **A, int  N)
{
    int number = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            if (((A[i][j] < A[i - 1][j - 1]) || (i == 0 && j == 0)) && ((A[i][j] < A[i][j - 1]) || (j == 0)) &&
                ((A[i][j] < A[i + 1][j - 1]) || (i == (N - 1) && j == 0)) && ((A[i][j] < A[i - 1][j]) || (i == 0)) &&
                ((A[i][j] < A[i - 1][j + 1]) || (i == 0 && j == (N - 1))) && 
                ((A[i][j] < A[i][j + 1]) || (j == (N - 1))) &&
                ((A[i][j] < A[i + 1][j + 1]) || (i == (N - 1) && j == (N - 1))) &&
                ((A[i][j] < A[i + 1][j]) || (i == (N - 1))))
            {
                number++;
            }
    }
    return number;
}
помогите найти ошибку. Компилятор ругается, хотя вроде все правильно...
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2018, 16:30
Ответы с готовыми решениями:

Найти количество локальных минимумов в одномерном массиве
Составьте функцию, определяющую количество локальных минимумов для массива целых чисел. Элемент...

Найти в массиве количество локальных минимумов значение которых кратно трем
У меня такая проблема у меня есть задача Задание 25 № 7319. Дан массив, содержащий 2014...

Определить количество локальных минимумов в заданном числовом массиве
Задание: составить схему алгоритма и программу решения задачи. Определить количество локальных...

Найти количество локальных минимумов в матрице
Можете подсказать как найти кол-во локальных минимумов в двумерном массиве?

Подсчитать количество локальных минимумов матрицы, найти сумму модулей элементов выше главной диагонали
Элемент матрицы называется локальным минимумом, если он строго меньше всех имеющихся у него...

9
ReDoX
410 / 308 / 160
Регистрация: 01.07.2015
Сообщений: 1,071
09.05.2018, 17:23 2
Цитата Сообщение от AliceUchiha Посмотреть сообщение
Компилятор ругается
В приведенном примере не квадратная таблица, хотя обход в циклах происходит таблицы N на N.

Вы считаете не кол-во локальных минимумов, а сколько элементов меньше локальных минимумов.

Может, имелось в виду нечто похожее:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
 
using namespace std;
 
int Number_of_local_minima(int **A, int N) {
  int dx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
  int dy[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
 
  int ans = 0;
 
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int temp = 0;
      int limit = 8;
 
      for (int d = 0; d < 8; ++d) {
        int x = i + dx[d];
        int y = j + dy[d];
 
        bool bounds = x > 0 && x < N && y > 0 && y < N;
 
        if (!bounds) {
          --limit;
 
          continue;
        }
 
        if (bounds && A[i][j] < A[x][y])
          ++temp;
      }
 
      if (temp == limit)
        ++ans;
 
    }
  }
 
  return ans;
}
 
int main() {
  int n;
  cin >> n;
 
  int **a = new int*[n];
 
  for (int i = 0; i < n; ++i) {
    a[i] = new int[n];
 
    for (int j = 0; j < n; ++j)
      cin >> a[i][j];
  }
 
  cout << Number_of_local_minima(a, n);
}
Прикрепил картинку, где указано, каким образом заполняются dx и dy
1
Изображения
 
AliceUchiha
0 / 0 / 0
Регистрация: 30.11.2017
Сообщений: 19
09.05.2018, 17:45  [ТС] 3
Да, извиняюсь, массив не квадратный в примере, хотя должен быть квадратный вы правы, я просто хотел показать, что есть локальный минимум.
Так мне это и нужно, проверить является ли элемент минимумом. Я беру элемент и сравниваю его с соседями, если есть меньше него самого, тогда цикл переходит к следующему элементу а в number записывается +1. Почему это неправильно, объясните поподробнее, пожалуйста.

И не могли бы вы пожалуйста поподробнее объяснить что в данной части когда за что отвечает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int temp = 0;
      int limit = 8;
 
      for (int d = 0; d < 8; ++d) {
        int x = i + dx[d];
        int y = j + dy[d];
 
        bool bounds = x > 0 && x < N && y > 0 && y < N;
 
        if (!bounds) {
          --limit;
 
          continue;
        }
 
        if (bounds && A[i][j] < A[x][y])
          ++temp;
      }
 
      if (temp == limit)
        ++ans;
первые 2 строчки отвечают за пробег по массиву, что делает 3тий for? что делает bool?С чем сравнивает предпоследний If?

Добавлено через 1 минуту
а компилятор я думаю ругается на выход за пределы массива, хотя я не пойму где и как это происходит если я поставил его перед выбором ИЛИ
0
Yetty
1639 / 1185 / 875
Регистрация: 18.12.2017
Сообщений: 4,096
09.05.2018, 17:46 4
Цитата Сообщение от AliceUchiha Посмотреть сообщение
помогите найти ошибку. Компилятор ругается, хотя вроде все правильно...
то что Вы считаете полным кодом - функция, а функция - только часть кода, вот компилятор и сообщает об этом.
0
AliceUchiha
0 / 0 / 0
Регистрация: 30.11.2017
Сообщений: 19
09.05.2018, 17:51  [ТС] 5
я знаю что это функция, и проблема у меня только в ней, в частности в выходе за границы массива, я только что проверил, убрав саму границу в массиве и проверив лишь внутреннюю часть массива, однако мне надо и границы посмотреть на минимумы, опять же не пойму где ошибка в функции if
0
ReDoX
410 / 308 / 160
Регистрация: 01.07.2015
Сообщений: 1,071
09.05.2018, 17:56 6
Лучший ответ Сообщение было отмечено AliceUchiha как решение

Решение

Ваш адский if абсолютно неотлаживаемый. Проще завести какие-нибудь два массива для направлений - dx, dy - и потом соответственно пробегаться по этим направлениям. На картинке, которую я прикрепил, указано, соответствия индекса и направления, то есть индексу 0 соответствует направление сверху слева и т.д. Таким образом 3 for - проверка текущего элемента по всем направлениям.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int Number_of_local_minima(int **A, int N) {
  // Проход по x
  int dx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
  
  // Проход по y
  int dy[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
 
  // Кол-во локальных минимумов.
  int ans = 0;
 
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int temp = 0;
      
      // Кол-во возможных направлений. То есть если элемент минимальный на
      // всех направлениях, то он является локальным минимумом.
      // Нужно не забывать еще про "стены", то есть тогда, когда элемент,
      // например, снизу или по углам.
      int limit = 8;
 
      for (int d = 0; d < 8; ++d) {
        // Берем элемент по новым координатам.
        int x = i + dx[d];
        int y = j + dy[d];
 
        // Проверяем выход за границы массива.
        bool bounds = x > 0 && x < N && y > 0 && y < N;
 
        // Если выходит, то нужно сократить лимит.
        if (!bounds) {
          --limit;
 
          continue;
        }
 
        // Если не выходит, проверяем, меньше ли наш элемент, чем тот, который
        // расположен в A[x][y].
        if (bounds && A[i][j] < A[x][y])
          ++temp;
      }
 
      // Если наш элемент меньше всех вокруг него, то прибавляем к кол-ву
      // локальных минимумов единицу.
      if (temp == limit)
        ++ans;
    }
  }
 
  return ans;
}
Добавлено через 1 минуту
Цитата Сообщение от AliceUchiha Посмотреть сообщение
Почему это неправильно, объясните поподробнее, пожалуйста.
Вы сказали, что кол-во локальных минимумов = 2. Перепишите ваш код без ошибок и посмотрите, что он выдаст
1
Yetty
1639 / 1185 / 875
Регистрация: 18.12.2017
Сообщений: 4,096
09.05.2018, 17:59 7
AliceUchiha, сбросьте весь код. но сначала сделайте это: локальные минимумы определяйте по следующему алгоритму: подсчёт внутренних минимумов (без периметра) + подсчёт минимумов периметра (без угловых) + подсчёт угловых минимумов.
1
AliceUchiha
0 / 0 / 0
Регистрация: 30.11.2017
Сообщений: 19
09.05.2018, 20:11  [ТС] 8
ваш код работает не совсем правильно. Что-то не так с нулями. Например при вводе массива
0 0 0 0
4 4 4 4
4 4 4 4
0 0 0 0 Он выдает 4 лок. минимума хотя их тут вообще нет

Добавлено через 23 минуты
а как отдельно периметр проверить?

Добавлено через 43 минуты
спасибо, написал как ты и сказал и все прекрасно работает, хоть и громоздка однако
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "stdafx.h"
int Number_of_local_minima(int **A, int  N)
{
    int number = 0;
    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
            if (A[i][j] < A[i - 1][j - 1])
                if (A[i][j] < A[i - 1][j])
                    if (A[i][j] < A[i - 1][j + 1])
                        if (A[i][j] < A[i][j + 1])
                            if (A[i][j] < A[i + 1][j + 1])
                                if (A[i][j] < A[i + 1][j])
                                    if (A[i][j] < A[i + 1][j - 1])
                                        if (A[i][j] < A[i][j - 1])
                                            number++;
    }
    for (int i = 0; i < 1; i++) 
    {
        for (int j = 1; j < N-1; j++)
                if (A[i][j] < A[i + 1][j - 1])
                    if (A[i][j] < A[i + 1][j])
                        if (A[i][j] < A[i + 1][j + 1])
                            if (A[i][j] < A[i][j - 1])
                                if (A[i][j] < A[i][j + 1])
                                    number++;
    }
    for (int i = N-1; i < N; i++)
    {
        for (int j = 1; j < N-1; j++)
                if (A[i][j] < A[i - 1][j - 1])
                    if (A[i][j] < A[i - 1][j])
                        if (A[i][j] < A[i - 1][j + 1])
                            if (A[i][j] < A[i][j - 1])
                                if (A[i][j] < A[i][j + 1])
                                    number++;
    }
    for(int i=1;i<N-1;i++)
    {
    for (int j = 0; j < 1; j++) 
                if (A[i][j] < A[i - 1][j + 1])
                    if (A[i][j] < A[i][j + 1])
                        if (A[i][j] < A[i + 1][j + 1])
                            if (A[i][j] < A[i - 1][j])
                                if (A[i][j] < A[i + 1][j])
                                    number++;
    }
    for (int i = 1; i<N - 1; i++)
    {
        for (int j = N-1; j < N; j++)
            if (A[i][j] < A[i - 1][j -1])
                if (A[i][j] < A[i][j - 1])
                    if (A[i][j] < A[i + 1][j - 1])
                        if (A[i][j] < A[i - 1][j])
                            if (A[i][j] < A[i + 1][j])
                                number++;
    }
    for (int i = 0; i<1; i++)
    {
        for (int j = 0; j < 1; j++)
            if (A[i][j] < A[i][j + 1])
                if (A[i][j] < A[i+1][j])
                    if (A[i][j] < A[i + 1][j + 1])
                                number++;
    }
    for (int i = 0; i<1; i++)
    {
        for (int j = N-1; j < N; j++)
            if (A[i][j] < A[i][j - 1])
                if (A[i][j] < A[i + 1][j])
                    if (A[i][j] < A[i + 1][j - 1])
                        number++;
    }
    for (int i = N - 1; i<N; i++)
    {
        for (int j = 0; j < 1; j++)
            if (A[i][j] < A[i-1][j])
                if (A[i][j] < A[i][j+1])
                    if (A[i][j] < A[i -1][j+ 1])
                        number++;
    }
    for (int i = N - 1; i<N; i++)
    {
        for (int j = N-1; j < N; j++)
            if (A[i][j] < A[i][j-1])
                if (A[i][j] < A[i-1][j])
                    if (A[i][j] < A[i - 1][j -1])
                        number++;
    }
    return number++;
}
0
Yetty
1639 / 1185 / 875
Регистрация: 18.12.2017
Сообщений: 4,096
09.05.2018, 20:17 9
AliceUchiha, код конечно должен быть компактнее , напишите оригинал условия задачи
0
ReDoX
410 / 308 / 160
Регистрация: 01.07.2015
Сообщений: 1,071
09.05.2018, 20:31 10
Ошибка в условии была. Теперь с нулями все верно проверяет

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
 
using namespace std;
 
int Number_of_local_minima(int **A, int N) {
  int dx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
  int dy[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
 
  int ans = 0;
 
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int temp = 0;
      int limit = 8;
 
      for (int d = 0; d < 8; ++d) {
        int x = i + dx[d];
        int y = j + dy[d];
 
        bool bounds = x >= 0 && x < N && y >= 0 && y < N;
 
        if (!bounds) {
          --limit;
 
          continue;
        }
 
        if (A[i][j] < A[x][y])
          ++temp;
      }
 
      if (temp == limit)
        ++ans;
 
    }
  }
 
  return ans;
}
 
int main() {
  int n;
  cin >> n;
 
  int **a = new int*[n];
 
  for (int i = 0; i < n; ++i) {
    a[i] = new int[n];
 
    for (int j = 0; j < n; ++j)
      cin >> a[i][j];
  }
 
  cout << Number_of_local_minima(a, n);
}
0
09.05.2018, 20:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2018, 20:31

Подсчитать количество локальных минимумов
Элемент матрицы называется локальным минимумом, если он строго меньше всех имеющихся у него...

Количество локальных минимумов в списке
Всем привет, в списке нужно подсчитать кол-во локальных минимумов и вывести их. Подсчитать...

Массив: посчитать количество локальных минимумов
Вот задание: Официальный язык форума - русский, задание перевести


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru