Найти ошибку в методе поиска локального минимума в двухмерном массиве

@Jabrobaka · Регистрация: 06.11.2012

Author24 — интернет-сервис помощи студентам

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

Кликните здесь для просмотра всего текста

C#

private bool IsLocalMin(sbyte i, sbyte j, int[,] m)
        {
            sbyte IMinus = Convert.ToSByte(i - 1);
            sbyte JMinus = Convert.ToSByte(j - 1);
            sbyte IPlus = Convert.ToSByte(i + 1);
            sbyte JPlus = Convert.ToSByte(j + 1);
            int a = m[i, j];
 
            if (((IMinus >= 0) && (JMinus >= 0)) && ((IPlus <= (m.GetLength(0) - 2)) && (JPlus <= (m.GetLength(1) - 2)))) //проверка не в углах и не по краям
            {
                for (sbyte x = IMinus; x < IPlus; x++)
                    for (sbyte y = JMinus; y < JPlus; y++)
                        if ((a >= m[x, y]) && (x != i) && (y != j))
                            return false;
                return true;
                
            }
 
 
            if ((IMinus < 0) | (JMinus < 0)) //проверка по краям и в углу слева вверху
            {
                if ((IMinus < 0) && (JMinus < 0))
                {
                    for (sbyte x = i; x < IPlus+1; x++)
                        for (sbyte y = j; y < JPlus+1; y++)
                            if ((a >= m[x, y]) && (x != i) && (y != j))
                                return false;
                    return true;
                }
                else if ((JMinus < 0) && (IMinus >= 0))
                {
                    if (IPlus <= (m.GetLength(0) - 1))
                    {
                        for (sbyte x = i; x < IPlus; x++)
                            for (sbyte y = j; y < JPlus; y++)
                                if ((a >= m[x, y]) && (x != i) && (y != j))
                                    return false;
                        return true;
                    }
                    else
                    {
                        for (sbyte x = i; x < IPlus; x++)
                            for (sbyte y = JMinus; y < JPlus; y++)
                                if ((a >= m[x, y]) && (x != i) && (y != j))
                                    return false;
                        return true;
                    }
                }
                else if ((IMinus < 0) && (JMinus >= 0))
                {
                    if (JPlus <= (m.GetLength(1)) - 1)
                    {
                        for (sbyte x = i; x < IPlus; x++)
                            for (sbyte y = j; y < JPlus; y++)
                                if ((a >= m[x, y]) && (x != i) && (y != j))
                                    return false;
                        return true;
                    }
                    else
                    {
                        for (sbyte x = i; x < IPlus; x++)
                            for (sbyte y = JMinus; y < j; y++)
                                if ((a >= m[x, y]) && (x != i) && (y != j))
                                    return false;
                        return true;
                    }
                }
 
 
            }
 
            if ((IPlus > (m.GetLength(0) - 1)) | (JPlus > (m.GetLength(1) - 1))) //проверка по краям и в углу снизу справа
            {
                sbyte LenI = Convert.ToSByte(m.GetLength(0) - 1);
                sbyte LenJ = Convert.ToSByte(m.GetLength(1) - 1);
                if ((IPlus > LenI) && (JPlus > LenJ))
                {
                    for (sbyte x = IMinus; x < i; x++)
                        for (sbyte y = JMinus; y < j; y++)
                            if ((a >= m[x, y]) && (x != i) && (y != j))
                                return false;
                    return true;
                }
                else if ((JPlus > LenJ) && (IPlus <= LenI))
                {
                    for (sbyte x = IMinus; x < IPlus; x++)
                        for (sbyte y = JMinus; y < j; y++)
                            if ((a >= m[x, y]) && (x != i) && (y != j))
                                return false;
                    return true;
                }
                else
                {
                    for (sbyte x = IMinus; x < i; x++)
                        for (sbyte y = JMinus; y < JPlus; y++)
                            if ((a >= m[x, y]) && (x != i) && (y != j))
                                return false;
                    return true;
                }
            }
 
            return false;
        }

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

@smth · 09.11.2012, 00:53

Ты сам себя запутал.
Твоя ошибка в том, что ты не понял, зачем именно создал метод. Судя по возвращаемому значению и аргументам, ты передаешь позицию в массиве и проверяешь, является ли она локальным минимумом. Это делается в одну строчку с кучей &&
Представь морской бой. Ты стреляешь в ячейку и просто проверяешь все остальные вокруг нее.
Так как у нас есть условия краев и углов, у тебя будет 4 условия проверки углов и 4 условия проверки краев + 1 условие проверки середины. Итого - 9 строчек.

В твоем же коде ты зачем-то делаешь кучу переборов значений каких-то, используешь кучу лишних переменных, условий.. в общем, голову сломаешь )

Код должен быть как можно более лаконичным. Не используй много лишних переменных, не используй непонятных названий, с другой стороны, не экономь на переменных. Все в меру.
Не экономь на памяти, использование sbyte никому лучше не сделает, чтобы тебя не мучила жадность и совесть - компилятор все равно переделает их скорее всего в int.
Четко понимай, что ты реализуешь в том или ином методе. Не пытайся запихать все в один метод, но и не создавай кучу новых ради выполнения одной операции.
Очень советую не отказываться от бумаги с ручкой и рисовать алгоритмы и блок-схемы. Это очень помогает. Поначалу рисуй максимально подробно. Если ты можешь без проблем написать реализацию какого-то блока - значит, ты понял, из чего он состоит. И наоборот, если ты не видишь необходимости расписывать какое-либо действие более подробно - значит, ты понял этот кусок.

Как-то так.
В твоем случае логика такова:
в основной программе перебираем поэлементно массив и для каждого элемента вызываем метод проверки.

@Jabrobaka · 09.11.2012, 17:56 **[ТС]**

Спасибо за советы. Я пытался сделать универсальное решение, а получилась какая-то сборная солянка. Попробую еще раз, ориентируясь вашим ценным советам. После прочтения Вашего ответа, появились некоторые ценные мысли.

Psilon · 09.11.2012, 20:05

smth, а если внезапно надо будет учитывать не только соседние точки, но и точки через них (то есть не только точки, окаймляющие фигуру "морского боя", но и точки, окаймляющие это окаймовку), то дописывать еще 100500 условий? Автор все правильно делал, а вы его только путаете.
Jabrobaka,
С другой стороны, идея более-менее, а вот реализация хромает: куча лишних переменных, к тому же нет смысла использовать sbyte, переменная все равно занимает число байт, кратное четырем, если только она не является полем класса/структуры (так называемое выравнивание). Напишите, чего вы хотите (в чем именно заключается условие локального минимума), мб найдем чем помочь.

@Jabrobaka · 09.11.2012, 22:12 **[ТС]**

сбайт делал потому, что в паре мест было отрицательное значение -1, не помню уже где, решил все байты в сбайты сделать, чтобы ошибок не было. Переборщил, конечно.
А моя каша получилась как раз из похожих Ваших мыслей, которые Вы изложили в ответе к smth.
Нужно решить задачу: "Дана матрица размера M x N. Элемент называется локальным минимумом, если он меньше всех окружающих его элементов. Заменить все локальные минимумы данной матрицы на 0."

Psilon · 09.11.2012, 22:38

Jabrobaka, ну например так:

C#

using System;
using System.Collections.Generic;
 
namespace LocalMin
{
    internal static class Program
    {
        private static void Main()
        {
            var a = new[,]
                {
                    {1, 2, 3},
                    {4, 5, 6},
                    {7, 8, 9}
                };
            a.Print();
            Console.WriteLine();
            a.SetAllLocalMinToZero();
            a.Print();
            Console.ReadKey();
        }
 
 
        private static void Print(this int[,] a)
        {
            for (int i = 0; i < a.GetLength(0); i++)
            {
                for (int j = 0; j < a.GetLength(1); j++)
                    Console.Write(a[i, j] + " ");
                Console.WriteLine();
            }
        }
 
 
        private static void SetAllLocalMinToZero(this int[,] a)
        {
            var list = new List<Tuple<int, int>>();
            for (int i = 0; i < a.GetLength(0); i++)
                for (int j = 0; j < a.GetLength(1); j++)
                    if (a.IsLocalMin(i, j))
                        list.Add(new Tuple<int, int>(i, j));
            foreach (var tuple in list)
                a[tuple.Item1, tuple.Item2] = 0;
        }
 
 
        private static bool IsLocalMin(this int[,] a, int i, int j)
        {
            int m = a.GetLength(0), n = a.GetLength(1), x = a[i, j];
            int starti = i > 0 ? i - 1 : 0, finishi = i < m ? i + 1 : m;
            int startj = j > 0 ? j - 1 : 0, finishj = j < n ? i + 1 : n;
            for (int k = starti; k <= finishi; k++)
                for (int l = startj; l <= finishj; l++)
                    if (x >= a[k, l] && (k != i || l != j))
                        return false;
            return true;
        }
    }
}

@Jabrobaka · 09.11.2012, 22:45 **[ТС]**

C++

1	var list = new List<Tuple<int, int>>();

Насколько я понимаю, это создание нового объекта. Но больше я ничего не понял, с <> такими скобками не знаком еще. Можно пояснить?

Psilon · 09.11.2012, 22:49

Jabrobaka, почитайте про обобщенные классы и методы:

http://msdn.microsoft.com/ru-r... aeb7t.aspx

Добавлено через 1 минуту
http://msdn.microsoft.com/ru-r... a29h6.aspx

@smth 179 / 48 / 6 Регистрация: 23.06.2011 Сообщений: 248
	09.11.2012, 00:53	2
	Ты сам себя запутал. Твоя ошибка в том, что ты не понял, зачем именно создал метод. Судя по возвращаемому значению и аргументам, ты передаешь позицию в массиве и проверяешь, является ли она локальным минимумом. Это делается в одну строчку с кучей && Представь морской бой. Ты стреляешь в ячейку и просто проверяешь все остальные вокруг нее. Так как у нас есть условия краев и углов, у тебя будет 4 условия проверки углов и 4 условия проверки краев + 1 условие проверки середины. Итого - 9 строчек. В твоем же коде ты зачем-то делаешь кучу переборов значений каких-то, используешь кучу лишних переменных, условий.. в общем, голову сломаешь ) Код должен быть как можно более лаконичным. Не используй много лишних переменных, не используй непонятных названий, с другой стороны, не экономь на переменных. Все в меру. Не экономь на памяти, использование sbyte никому лучше не сделает, чтобы тебя не мучила жадность и совесть - компилятор все равно переделает их скорее всего в int. Четко понимай, что ты реализуешь в том или ином методе. Не пытайся запихать все в один метод, но и не создавай кучу новых ради выполнения одной операции. Очень советую не отказываться от бумаги с ручкой и рисовать алгоритмы и блок-схемы. Это очень помогает. Поначалу рисуй максимально подробно. Если ты можешь без проблем написать реализацию какого-то блока - значит, ты понял, из чего он состоит. И наоборот, если ты не видишь необходимости расписывать какое-либо действие более подробно - значит, ты понял этот кусок. Как-то так. В твоем случае логика такова: в основной программе перебираем поэлементно массив и для каждого элемента вызываем метод проверки. 1

@Jabrobaka 0 / 0 / 0 Регистрация: 06.11.2012 Сообщений: 5
	09.11.2012, 17:56 [ТС]	3
	Спасибо за советы. Я пытался сделать универсальное решение, а получилась какая-то сборная солянка. Попробую еще раз, ориентируясь вашим ценным советам. После прочтения Вашего ответа, появились некоторые ценные мысли. 0

Psilon Master of Orion 6100 / 4956 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	09.11.2012, 20:05	4
	smth, а если внезапно надо будет учитывать не только соседние точки, но и точки через них (то есть не только точки, окаймляющие фигуру "морского боя", но и точки, окаймляющие это окаймовку), то дописывать еще 100500 условий? Автор все правильно делал, а вы его только путаете. Jabrobaka, С другой стороны, идея более-менее, а вот реализация хромает: куча лишних переменных, к тому же нет смысла использовать sbyte, переменная все равно занимает число байт, кратное четырем, если только она не является полем класса/структуры (так называемое выравнивание). Напишите, чего вы хотите (в чем именно заключается условие локального минимума), мб найдем чем помочь. 1

@Jabrobaka 0 / 0 / 0 Регистрация: 06.11.2012 Сообщений: 5
	09.11.2012, 22:12 [ТС]	5
	сбайт делал потому, что в паре мест было отрицательное значение -1, не помню уже где, решил все байты в сбайты сделать, чтобы ошибок не было. Переборщил, конечно. А моя каша получилась как раз из похожих Ваших мыслей, которые Вы изложили в ответе к smth. Нужно решить задачу: "Дана матрица размера M x N. Элемент называется локальным минимумом, если он меньше всех окружающих его элементов. Заменить все локальные минимумы данной матрицы на 0." 0

Psilon Master of Orion 6100 / 4956 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	09.11.2012, 22:49	8
	Jabrobaka, почитайте про обобщенные классы и методы: http://msdn.microsoft.com/ru-r... aeb7t.aspx Добавлено через 1 минуту http://msdn.microsoft.com/ru-r... a29h6.aspx 1