これは、各セルに0から99までの整数を持つテーブル（20x20）です。
タスクは、チェーンを壊すことなく、最大の製品で次々に4つの隣接する番号を見つけることです。4つの隣接する番号のさまざまなバリエーションが色で強調表示されます（2つの番号は、互いに1セル以内にある場合、隣接していると見なされます）。
今日は、C＃で検索アルゴリズムを実装します。
まず、20x20の2次元配列を作成し、それをファイルに書き込みましょう。
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(" ");
}
}
これで、ファイルの数値を2次元配列に書き込むことができます。
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でない場合は、2番目のレベルのすべてのネイバーを探します...
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;
}
}
第4レベルのネイバーへの検索を続行します。番号が重複していない場合は、コレクションに追加します。
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メソッドは、次のように視覚化できます。
ここで、2次元配列を繰り返して、最大の数値の組み合わせを探しています。
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 x 20ではなく、たとえば30 x 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テーブルで隣接する組み合わせを見つけるためのオプションの1つについて説明しました。
他に何ができますか：
- すべての組み合わせの複数の反復を取り除くこと、およびコードを最適化する他の方法を検討できます。
- 既存のアルゴリズムに基づいて、3次元配列上の隣接する番号の組み合わせの検索を実装します。しかし、これはすでに別の時間です...
