Регистрация

[Алгоритмы, C#] Найти комбинацию соседних чисел, имеющих самое большое произведение

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
10-Авг-2020 12:31
Цитировать


Перед вами таблица (20x20) с целым числом от 0 до 99 в каждой из клеток.
Задача — найти 4 соседних числа без разрыва цепочки, одно за другим, имеющих самое большое произведение. Цветом выделены различные варианты 4 соседних чисел (соседними считаются два числа, расположенных не более чем на 1 клетку друг от друга)
Сегодня мы с вами реализуем алгоритм поиска на языке C#
Для начало создадим двумерный массив 20х20 и запишем его в файл
static void CreateArrayFile()
{
    Random random = new Random();
    string file = "";
    for (int i = 0; i < 20; i++)
    {
        string line = "";
        for (int j = 0; j < 20; j++)
        {
            line += random.Next(0, 99) + ",";
        }
        line = line + Environment.NewLine;
        file += line;
    }
    using (FileStream fstream = new FileStream($"array.txt", FileMode.OpenOrCreate))
    {
        byte[] array = System.Text.Encoding.Default.GetBytes(file);
        fstream.Write(array, 0, array.Length);
        Console.WriteLine("Массив записан в файл");
    }
}


Теперь мы можем, записать числа из файла в двумерный массив.
string[] lines = arrayFile.Split(Environment.NewLine);
for (int i = 0; i < 20; i++)
{
    string[] items = lines[i].Split(',');
    for (int j = 0; j < 20; j++)
    {
        table[i, j] = Convert.ToInt32(items[j]);
    }
}

Для представления координат и значения числа создадим класс Element
public class Element
{
    public int Line { get; set; }
    public int Column { get; set; }
    public int Value { get; set; }
}

По условиям задачи, требуется найти комбинацию произведений. Реализуем класс Multiplication для представления комбинации содержащий массив чисел и значение произведения чисел в комбинации.
public class Multiplication
{
    public Multiplication()
    {
        Elements = new Element[4];
    }
    public Element[] Elements { get; set; }
    public int Value
    {
        get
        {
            Multiply();
            return value;
        }
    }
    int value;
    void Multiply()
    {
        if(Elements[0] != null && Elements[1] != null && Elements[2] != null && Elements[3] != null)
        {
            value = Elements[0].Value * Elements[1].Value * Elements[2].Value * Elements[3].Value;
        }
    }
}

Первое что нужно сделать найти ближайших соседей числа. Например, для числа 40 в нашем случае следующие соседи:

А у числа 48 в правом нижнем углу есть всего 3 соседа. Не трудно понять, что соседи любого числа это
table[i-1][j-1]
table[i-1][j]
table[i-1][j+1]
table[i][j-1]
table[i][j+1]
table[i+1][j-1]
table[i+1][j]
table[i+1][j+1]

Убедившись, что индекс не находится вне границ, получаем метод FindNeighbors возвращающий коллекцию всех ближайших соседей конкретного числа.
По условию задачи, нам нужно найти комбинацию из 4 соседних чисел. Для этого нам нужен метод для поиска всех возможных комбинаций из 4 чисел
static List<Multiplication> GetFactorCombinations(int line, int column)
{
    List<Multiplication> combinations = new List<Multiplication>();
    if (table[line, column] != 0)
    {
        List<Element> firstLevelNeighbors = FindNeighbors(line, column);
        foreach (var firstLevelNeighbor in firstLevelNeighbors)
        {
            Element[] elements = new Element[4];
            elements[0] = new Element
            {
                Line = line,
                Column = column,
                Value = table[line, column]
            };
            elements[1] = firstLevelNeighbor;
            List<Element> secondLevelNeighbors = FindNeighbors(firstLevelNeighbor.Line, firstLevelNeighbor.Column);
            foreach (var secondLevelNeighbor in secondLevelNeighbors)
            {
                if (!elements[0].Equals(secondLevelNeighbor) && !elements[1].Equals(secondLevelNeighbor))
                {
                    elements[2] = secondLevelNeighbor;
                }
                if (elements[2] != null)
                {
                    List<Element> thirdLevelNeighbors = FindNeighbors(secondLevelNeighbor.Line, secondLevelNeighbor.Column);
                    foreach (var thirdLevelNeighbor in thirdLevelNeighbors)
                    {
                        if (!elements[0].Equals(thirdLevelNeighbor) && !elements[1].Equals(thirdLevelNeighbor) && !elements[2].Equals(thirdLevelNeighbor))
                        {
                            elements[3] = thirdLevelNeighbor;
                            Multiplication multiplication = new Multiplication
                            {
                                Elements = elements
                            };
                            if (combinations.Where(p=>p.Elements[0].Value==elements[0].Value&& p.Elements[1].Value == elements[1].Value && p.Elements[2].Value == elements[2].Value && p.Elements[3].Value == elements[3].Value).FirstOrDefault()==null)
                            {
                                var nnnn =new Multiplication
                                {
                                    Elements = new Element[] { elements[0], elements[1], elements[2], elements[3]}
                                };
                                combinations.Add(nnnn);
                            }
                        }
                    }
                }
            }
        }
    }
    return combinations;
}

Метод получает координаты числа в таблице и проверяет значение этого числа на 0 (При умножении любого числа на 0 всегда получается 0). Потом метод ищет всех соседей данного числа. Перебираем соседей первого уровня, в случае если число не 0 ищем всех соседей второго уровня…
Переопределяем метод Equals для сравнивания чисел:
public override bool Equals(Object obj)
{
    if (this==null || (obj == null) || !this.GetType().Equals(obj.GetType()))
    {
        return false;
    }
    else if(Line == ((Element)obj).Line && Column == ((Element)obj).Column)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Продолжаем поиск до соседей четвертого уровня если числа не дублируются, то добавляем его в нашу коллекцию.
if (!elements[0].Equals(thirdLevelNeighbor) && !elements[1].Equals(thirdLevelNeighbor) && !elements[2].Equals(thirdLevelNeighbor))
{
    elements[3] = thirdLevelNeighbor;
    Multiplication multiplication = new Multiplication
    {
        Elements = elements
    };
    if (combinations.Where(p=>p.Elements[0].Value==elements[0].Value&& p.Elements[1].Value == elements[1].Value && p.Elements[2].Value == elements[2].Value && p.Elements[3].Value == elements[3].Value).FirstOrDefault()==null)
    {
        var combination=new Multiplication
        {
            Elements = new Element[] { elements[0], elements[1], elements[2], elements[3]}
        };
        combinations.Add(combination);
    }
}

Работу метода GetFactorCombinations можно визуализировать так:

Теперь перебрав наш двумерный массив ищем самую большую комбинацию чисел.
for (int i = 0; i < 20; i++)
{
    for (int j = 0; j < 20; j++)
    {
        List<Multiplication> combinations = GetFactorCombinations(i, j);
        foreach (var combination in combinations)
        {
            if (combination.Value > maxMultiplication.Value)
            {
                Console.WriteLine("Найдена новая самая большая комбинация " + combination.Elements[0].Value + " * " + combination.Elements[1].Value + " * " + combination.Elements[2].Value + " * " + combination.Elements[3].Value + " = " + combination.Value);
                maxMultiplication = combination;
            }
        }
    }
}
Console.WriteLine("Самое большое произведение четырех чисел = " + maxMultiplication.Elements[0].Value + " * " + maxMultiplication.Elements[1].Value + " * " + maxMultiplication.Elements[2].Value + " * " + maxMultiplication.Elements[3].Value + " = " + maxMultiplication.Value);

Если следующая комбинация больше чем maxMultiplication, переписываем его.

Да, мы сделали это. Мы нашли комбинацию из 4 чисел с самым большим произведением.
Фактически, мы решили задачу, но код захардкожен под конкретные условия, чисто процедурный метод. А если нам нужно будет искать из матрицы не 20 на 20, а к примеру 30 на 30 и комбинацию не из 4, а 5 чисел? каждый раз добавлять еще один вложенный цикл (для перебора всех со всеми) …
Зарезервируем 2 константы для размера таблицы, и для размера искомой комбинации
const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;

Перепишем метод GetFactorCombinations на рекурсивный метод
static List<Multiplication> GetMultiplicationForStep(int line, int column, List<Element> otherElements = null)
{
    List<Multiplication> resultMultiplications = new List<Multiplication>();
    List<Element> resultElements = new List<Element>();
    Element element = new Element
    {
        Column = column,
        Line = line,
        Value = table[line, column]
    };
    if (otherElements == null)
    {
        otherElements = new List<Element>();
    }
    if(otherElements!=null)
    {
        resultElements.AddRange(otherElements);
    }
    if (table[line, column] != 0)
    {
        if (otherElements.Where(p => p.Equals(element)).FirstOrDefault() == null)
        {
            resultElements.Add(element);
        }
    }
    if (resultElements.Count() == COMBINATION_SIZE)
    {
        Multiplication multiplication = new Multiplication
        {
            Elements = resultElements.ToArray()
        };
        resultMultiplications.Add(multiplication);
    }
    else
    {
        List<Element> elementNeighbors = FindNeighbors(line, column);
        elementNeighbors = elementNeighbors.Where(p => !p.Equals(element)&& otherElements.Where(p=>p.Equals(element)).FirstOrDefault()==null).ToList();
        List<Multiplication> newMultiplications = new List<Multiplication>();
        foreach(Element neighbor in elementNeighbors)
        {
            // Если количество комбинаций меньше COMBINATION_SIZE рекурсивно продолжаю искать соседей...
            newMultiplications.AddRange(GetMultiplicationForStep(neighbor.Line, neighbor.Column, resultElements).Where(p=>p!=null));
        }
        foreach(Multiplication multiplication in newMultiplications)
        {
            if(resultMultiplications.Where(p=>p.Value==multiplication.Value).FirstOrDefault()==null)
            {
                resultMultiplications.Add(multiplication);
            }
        }
    }
    return resultMultiplications;
}

Метод работает по тому же принципу как и раньше только вместо вложенных циклов, рекурсивно продолжаем поиск соседей пока количество найденных элементов resultElements.Count() != COMBINATION_SIZE
После нахождения комбинации можно его красиво отобразить в консоли
for (int i = 0; i < TABLE_SIZE; i++)
{
    for (int j = 0; j < TABLE_SIZE; j++)
    {
        if (maxMultiplication.Elements.Where(p => p.Line == i && p.Column == j).FirstOrDefault() != null)
        {
            Console.BackgroundColor = ConsoleColor.White;
            Console.ForegroundColor = ConsoleColor.Black; // Тут я вывожу таблицу заново, и отображаю самую большую найденную комбинацию
            Console.Write(table[i, j] + " ");
            Console.ResetColor();
        }
        else
        {
            Console.Write(table[i, j] + " ");
        }
    }
    Console.WriteLine();
}



Заключение
В этой статье мы познакомились с одним из вариантов нахождения соседних комбинаций в таблице NxN.
Что можно сделать еще:
  • Можно рассмотреть возможность избавиться от множественных повторных переборов всех комбинаций со всеми, и другими способами оптимизировать код.
  • На основе существующего алгоритма реализовать поиск комбинаций соседних чисел на 3-мерном массиве. Но это уже в другой раз…


 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_algoritmy (Алгоритмы), #_c#, #_s# (с#), #_algoritmy (алгоритмы), #_algoritmy (
Алгоритмы
), #_c#
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 15:47
Часовой пояс: UTC + 5