Hier ist eine Tabelle (20x20) mit einer Ganzzahl von 0 bis 99 in jeder der Zellen.
Die Aufgabe besteht darin, 4 benachbarte Zahlen zu finden, ohne die Kette nacheinander mit dem größten Produkt zu unterbrechen. Verschiedene Varianten von 4 benachbarten Nummern werden farblich hervorgehoben (zwei Nummern gelten als benachbart, wenn sie nicht mehr als eine Zelle voneinander entfernt sind).
Heute werden wir den Suchalgorithmus in C # implementieren.
Erstellen wir zunächst ein zweidimensionales 20x20-Array und schreiben es in eine Datei:
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(" ");
}
}
Jetzt können wir die Zahlen aus der Datei in ein zweidimensionales Array schreiben.
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]);
}
}
Erstellen wir eine Elementklasse, um die Koordinaten und den Wert einer Zahl darzustellen:
public class Element
{
public int Line { get; set; }
public int Column { get; set; }
public int Value { get; set; }
}
Entsprechend den Bedingungen des Problems ist es erforderlich, eine Kombination von Werken zu finden. Implementieren wir die Multiplikationsklasse, um eine Kombination darzustellen, die ein Array von Zahlen und den Wert des Produkts der Zahlen in der Kombination enthält.
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;
}
}
}
Als erstes müssen Sie die nächsten Nachbarn der Nummer finden. Zum Beispiel für die Nummer 40 in unserem Fall die folgenden Nachbarn:
Und die Nummer 48 in der unteren rechten Ecke hat nur 3 Nachbarn. Es ist nicht schwer zu verstehen, dass die Nachbarn einer beliebigen Anzahl sind:
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]
Nachdem wir sichergestellt haben, dass der Index nicht außerhalb der Grenzen liegt, erhalten wir die FindNeighbors-Methode, die eine Sammlung aller nächsten Nachbarn einer bestimmten Zahl zurückgibt.
Entsprechend der Problemstellung müssen wir eine Kombination von 4 benachbarten Zahlen finden. Dazu benötigen wir eine Methode, um alle möglichen Kombinationen von 4 Zahlen zu finden:
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;
}
Die Methode ruft die Koordinaten einer Zahl in der Tabelle ab und überprüft den Wert dieser Zahl mit 0 (Wenn eine Zahl mit 0 multipliziert wird, stellt sich immer heraus, dass sie 0 ist). Dann sucht die Methode nach allen Nachbarn der angegebenen Nummer. Wir iterieren über die Nachbarn der ersten Ebene. Wenn die Zahl nicht 0 ist, suchen wir nach allen Nachbarn der zweiten Ebene. Wir
überschreiben die Equals-Methode, um Zahlen zu vergleichen:
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;
}
}
Wir setzen die Suche zu den Nachbarn der vierten Ebene fort. Wenn die Zahlen nicht dupliziert werden, fügen wir sie unserer Sammlung hinzu.
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);
}
}
Die GetFactorCombinations-Methode kann wie folgt visualisiert werden:
Jetzt iterieren wir über unser zweidimensionales Array und suchen nach der größten Zahlenkombination.
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);
Wenn die nächste Kombination größer als maxMultiplication ist, schreiben Sie sie neu.
Ja wir haben es geschafft. Wir haben die Kombination von 4 Zahlen mit dem größten Produkt gefunden.
Tatsächlich haben wir das Problem gelöst, aber der Code ist für bestimmte Bedingungen fest codiert, eine rein prozedurale Methode. Und wenn wir aus einer Matrix suchen müssen, nicht 20 mal 20, sondern zum Beispiel 30 mal 30 und eine Kombination aus nicht 4, sondern 5 Zahlen? Fügen Sie jedes Mal eine weitere verschachtelte Schleife hinzu (um alle mit allen zu durchlaufen) ... Wir
reservieren 2 Konstanten für die Größe der Tabelle und für die Größe der gewünschten Kombination:
const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;
Schreiben wir die GetFactorCombinations-Methode in eine rekursive Methode um:
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;
}
Die Methode funktioniert nach dem gleichen Prinzip wie zuvor, aber anstelle von verschachtelten Schleifen suchen wir rekursiv weiter nach Nachbarn, bis die Anzahl der gefundenen Elemente resultElements.Count ()! = COMBINATION_SIZE ist.
Nachdem Sie die Kombination gefunden haben, können Sie sie in der Konsole wunderschön anzeigen:
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();
}
Fazit
In diesem Artikel haben wir eine der Optionen zum Auffinden benachbarter Kombinationen in der NxN-Tabelle kennengelernt.
Was kannst du noch tun:
- Sie können mehrere Iterationen aller Kombinationen mit allen und andere Möglichkeiten zur Optimierung des Codes entfernen.
- Implementieren Sie basierend auf dem vorhandenen Algorithmus eine Suche nach Kombinationen benachbarter Zahlen in einem dreidimensionalen Array. Aber das ist schon ein anderes Mal ...
