Перед вами таблица (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-мерном массиве. Но это уже в другой раз…
