ابحث عن مجموعة الأرقام المجاورة مع المنتج الأكبر

يوجد هنا جدول (20 × 20) بعدد صحيح من 0 إلى 99 في كل خلية.



المهمة هي إيجاد 4 أرقام متجاورة دون كسر السلسلة ، واحدًا تلو الآخر ، بحيث يكون الناتج أكبر. يتم تمييز المتغيرات المختلفة المكونة من 4 أرقام متجاورة بالألوان (يعتبر رقمان متجاورين إذا كانا لا يزيدان عن خلية واحدة عن بعضهما البعض).



اليوم سنقوم بتنفيذ خوارزمية البحث في 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; }
}

وفقًا لظروف المشكلة ، يلزم العثور على مجموعة من الأعمال. دعنا ننفذ فئة الضرب لتمثيل مجموعة تحتوي على مصفوفة من الأرقام وقيمة حاصل ضرب الأرقام في المجموعة.

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]

بعد التأكد من أن الفهرس ليس خارج الحدود ، نحصل على طريقة FindNeighbours التي تُرجع مجموعة من أقرب جيران لرقم معين.



وفقًا للمسألة ، علينا إيجاد مجموعة مكونة من 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 أرقام؟ في كل مرة نضيف حلقة متداخلة أخرى (لتكرار الكل مع الكل) ...



نحتفظ بثابتين لحجم الجدول ، ولحجم التركيبة المطلوبة:

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.



ماذا يمكنك أن تفعل أيضا:

• يمكنك التفكير في التخلص من التكرارات المتعددة لجميع المجموعات مع الكل ، وطرق أخرى لتحسين الكود.
• بناءً على الخوارزمية الحالية ، قم بتنفيذ بحث عن مجموعات من الأرقام المجاورة في مصفوفة ثلاثية الأبعاد. لكن هذا بالفعل وقت آخر ...