Berikut adalah tabel (20x20) dengan bilangan bulat dari 0 hingga 99 di setiap sel.
Tugasnya adalah menemukan 4 bilangan yang berdekatan tanpa memutus rantai, satu demi satu, yang memiliki hasil kali terbesar. Varian berbeda dari 4 nomor yang berdekatan disorot dalam warna (dua nomor dianggap berdekatan jika terletak tidak lebih dari 1 sel dari satu sama lain).
Hari ini kami akan menerapkan algoritma pencarian di C #.
Pertama, mari buat larik dua dimensi 20x20 dan tulis ke file:
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(" ");
}
}
Sekarang kita dapat menulis angka dari file ke dalam array dua dimensi.
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]);
}
}
Mari buat kelas Elemen untuk mewakili koordinat dan nilai angka:
public class Element
{
public int Line { get; set; }
public int Column { get; set; }
public int Value { get; set; }
}
Sesuai dengan kondisi permasalahannya, perlu dicari kombinasi pekerjaannya. Mari kita terapkan kelas Perkalian untuk mewakili kombinasi yang berisi larik angka dan nilai produk dari angka dalam kombinasi tersebut.
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;
}
}
}
Hal pertama yang harus dilakukan adalah menemukan tetangga terdekat dari nomor tersebut. Misalnya, untuk nomor 40 dalam kasus kami, tetangga berikut:
Dan angka 48 di pojok kanan bawah hanya memiliki 3 tetangga. Tidak sulit untuk memahami bahwa tetangga dari nomor berapa pun adalah:
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]
Setelah memastikan bahwa indeks tidak keluar batas, kita mendapatkan metode FindNeighbours yang mengembalikan kumpulan semua tetangga terdekat dari nomor tertentu.
Berdasarkan soal tersebut, kita perlu mencari kombinasi dari 4 bilangan yang berdekatan. Untuk melakukan ini, kita memerlukan metode untuk menemukan semua kemungkinan kombinasi dari 4 angka:
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;
}
Metode mendapatkan koordinat angka di tabel dan memeriksa nilai angka ini dengan 0 (Saat mengalikan angka apa pun dengan 0, hasilnya selalu 0). Kemudian metode mencari semua tetangga dari nomor yang diberikan. Kami mengiterasi tetangga tingkat pertama, jika jumlahnya bukan 0, kami mencari semua tetangga tingkat kedua ... Kami
mengganti metode Sama dengan untuk membandingkan angka:
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;
}
}
Kami melanjutkan pencarian ke tetangga tingkat keempat, jika jumlahnya tidak diduplikasi, maka kami menambahkannya ke koleksi kami.
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);
}
}
Metode GetFactorCombinations dapat divisualisasikan sebagai berikut:
Sekarang, mengulangi larik dua dimensi kita, kita mencari kombinasi angka terbesar.
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);
Jika kombinasi berikutnya lebih besar dari maxMultiplication, tulis ulang.
Ya, kami berhasil. Kami telah menemukan kombinasi 4 angka dengan produk terbesar.
Faktanya, kami telah memecahkan masalah, tetapi kodenya dikodekan keras untuk kondisi tertentu, metode prosedural murni. Dan jika kita perlu mencari dari matriks bukan 20 kali 20, tetapi misalnya 30 kali 30 dan kombinasi bukan 4, tetapi 5 angka? setiap kali tambahkan loop bersarang lainnya (untuk mengulang semuanya dengan semua) ... Kami
memesan 2 konstanta untuk ukuran tabel, dan untuk ukuran kombinasi yang diinginkan:
const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;
Mari kita tulis ulang metode GetFactorCombinations menjadi metode rekursif:
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;
}
Metode ini bekerja sesuai dengan prinsip yang sama seperti sebelumnya, tetapi alih-alih loop bersarang, kami secara rekursif terus mencari tetangga hingga jumlah elemen yang ditemukan adalah resultElements.Count ()! = COMBINATION_SIZE
Setelah menemukan kombinasi, Anda dapat menampilkannya dengan indah di konsol:
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();
}
Kesimpulan
Pada artikel ini, kami berkenalan dengan salah satu opsi untuk menemukan kombinasi yang berdekatan di tabel NxN.
Apa lagi yang bisa Anda lakukan:
- Anda dapat mempertimbangkan untuk menyingkirkan beberapa iterasi dari semua kombinasi dengan semua, dan cara lain untuk mengoptimalkan kode.
- Berdasarkan algoritme yang ada, terapkan pencarian kombinasi angka yang berdekatan pada larik 3 dimensi. Tapi ini sudah lain kali ...
