Voici un tableau (20x20) avec un entier de 0 à 99 dans chacune des cellules.
La tâche est de trouver 4 nombres adjacents sans casser la chaîne, l'un après l'autre, ayant le plus gros produit. Différentes variantes de 4 nombres adjacents sont surlignées en couleur (deux nombres sont considérés comme adjacents s'ils ne sont pas situés à plus d'une cellule l'un de l'autre).
Aujourd'hui, nous allons implémenter l'algorithme de recherche en C #.
Tout d'abord, créons un tableau bidimensionnel 20x20 et écrivons-le dans un fichier:
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(" ");
}
}
Nous pouvons maintenant écrire les nombres du fichier dans un tableau à deux dimensions.
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]);
}
}
Créons une classe Element pour représenter les coordonnées et la valeur d'un nombre:
public class Element
{
public int Line { get; set; }
public int Column { get; set; }
public int Value { get; set; }
}
Selon les conditions du problème, il est nécessaire de trouver une combinaison d'œuvres. Implémentons la classe Multiplication pour représenter une combinaison contenant un tableau de nombres et la valeur du produit des nombres dans la combinaison.
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;
}
}
}
La première chose à faire est de trouver les voisins les plus proches du nombre. Par exemple, pour le nombre 40 dans notre cas, les voisins suivants:
Et le numéro 48 dans le coin inférieur droit n'a que 3 voisins. Il n'est pas difficile de comprendre que les voisins de n'importe quel nombre sont:
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]
Après s'être assuré que l'index n'est pas hors limites, nous obtenons la méthode FindNeighbors qui renvoie une collection de tous les voisins les plus proches d'un nombre particulier.
Selon l'énoncé du problème, nous devons trouver une combinaison de 4 nombres adjacents. Pour ce faire, nous avons besoin d'une méthode pour trouver toutes les combinaisons possibles de 4 nombres:
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;
}
La méthode obtient les coordonnées d'un nombre dans le tableau et vérifie la valeur de ce nombre par 0 (lors de la multiplication d'un nombre par 0, il s'avère toujours être 0). Ensuite, la méthode recherche tous les voisins du nombre donné. On itère sur les voisins du premier niveau, si le nombre n'est pas 0, on cherche tous les voisins du deuxième niveau ... On
remplace la méthode Equals pour comparer les nombres:
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;
}
}
Nous continuons la recherche vers les voisins du quatrième niveau, si les nombres ne sont pas dupliqués, nous les ajoutons à notre collection.
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);
}
}
La méthode GetFactorCombinations peut être visualisée comme suit:
Maintenant, en parcourant notre tableau à deux dimensions, nous recherchons la plus grande combinaison de nombres.
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);
Si la combinaison suivante est supérieure à maxMultiplication, réécrivez-la.
Oui, nous l'avons fait. Nous avons trouvé la combinaison de 4 chiffres avec le plus gros produit.
En fait, nous avons résolu le problème, mais le code est codé en dur pour des conditions spécifiques, une méthode purement procédurale. Et si nous devons rechercher à partir d'une matrice non pas 20 par 20, mais par exemple 30 par 30 et une combinaison non pas de 4, mais de 5 nombres? ajouter à chaque fois une autre boucle imbriquée (pour itérer sur tout avec tout) ... On
réserve 2 constantes pour la taille du tableau, et pour la taille de la combinaison souhaitée:
const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;
Réécrivons la méthode GetFactorCombinations en une méthode récursive:
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;
}
La méthode fonctionne selon le même principe que précédemment, mais au lieu de boucles imbriquées, nous continuons récursivement à rechercher des voisins jusqu'à ce que le nombre d'éléments trouvés soit resultElements.Count ()! = COMBINATION_SIZE
Après avoir trouvé la combinaison, vous pouvez l'afficher magnifiquement dans la console:
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();
}
Conclusion
Dans cet article, nous nous sommes familiarisés avec l'une des options permettant de rechercher des combinaisons adjacentes dans la table NxN.
Que pouvez vous faire d'autre:
- Vous pouvez envisager de vous débarrasser de plusieurs itérations de toutes les combinaisons avec tout et d'autres moyens d'optimiser le code.
- Sur la base de l'algorithme existant, implémentez une recherche de combinaisons de nombres voisins sur un tableau à 3 dimensions. Mais c'est déjà une autre fois ...
