أفكار بسيطة حول خوارزمية "العثور على جميع أزواج الأرقام في مصفوفة يكون مجموعها رقمًا ثابتًا"

1. وصف الموضوع

توجد مصفوفة a[1000]، والتي تخزن 1000 عدد صحيح. يرجى العثور على جميع أزواج الأرقام في المصفوفة التي مجموعها M. على سبيل المثال، المصفوفة هي -1,2,4,6,5,3,4,2,9,0,8,3، ثم أزواج الأرقام التي مجموعها 8 هي (-1,9)، (2، 6)، (4،4)، (5،3)، (5،3)، (0،8).

2. الخوارزمية الأكثر شيوعا

في حالة التعقيد غير القابل للاختزال، فإن أبسط خوارزمية لهذه المشكلة هي كما يلي:

قائمة ثابتة خاصة<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();

لـ (int i = 0; i < arr.Length; i++)
{
int waitNum = sumTotal - arr[i];

لـ (int j = i + 1; j < arr.Length; j++)
{
إذا (arr[j] == تتوقعNum)
{
result.Add(new int[]{arr[i], المتوقعNum});
}
}
}

نتيجة الإرجاع؛
}
استخدم حلقة ذات مستويين للعثور على جميع الأزواج التي يكون مجموعها عبارة عن رقم ثابت مجموع إجمالي، وقم بتخزين الأزواج التي تم العثور عليها في القائمة. ومع ذلك، فإن تعقيد هذه الخوارزمية مرتفع بعض الشيء، وهي في الواقع تقوم ببعض الأعمال المتكررة أثناء الاجتياز:

1) ليست هناك حاجة لمعالجة التسلسل المقترن مسبقًا في الحلقات اللاحقة.

2) عند البحث عن رقم مجموعه هو sumTotal، يجب أن تكون هناك بعض العمليات التي يمكن استخدامها بشكل متبادل.

بناءً على هاتين النقطتين، يمكنك اقتباس بعض أفكار البرمجة الديناميكية أو حقيبة الظهر (ربما بشكل غير مناسب، لدي فهم سطحي لهاتين الفكرتين) لتحسين هذه الخوارزمية واستخدام التكرار للتشغيل.

2. استخدم الخوارزمية العودية

الكود الذي يستخدم الخوارزمية العودية هو كما يلي:

قائمة ثابتة خاصة<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
int waitNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;

لـ (int i = 1; i < length; i++)
{
إذا (arr[i] == تتوقعNum)
{
int CircleCount = arr[0] == تتوقعNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;

لـ (int j = 0; j <circleCount; j++)
{
result.Add(new int[] { arr[0], المتوقعNum });
}

findEndNumCount++;
}
وإلا إذا (arr[i] == arr[0])
{
لـ (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {توقعNum, arr[0] });
}
findStartNumCount++;
}
آخر
{
nextArr[nextLength++] = arr[i];
}
}

إذا (الطول التالي > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (عنصر int[] في النتيجة التالية)
{
result.Add(item);
}
}

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

3. خوارزمية التغيير الديناميكي للمصفوفة

رمز هذه الخوارزمية هو كما يلي:

قائمة ثابتة خاصة<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;

بينما (startIndex <endIndex)
{
int waitNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;

لـ (int i = startIndex + 1; i <= endIndex; i++)
{
إذا (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}

إذا (arr[i] == تتوقعNum)
{
int CircleCount = arr[startIndex] == تتوقعNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;

لـ (int iStart = 0; iStart <circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}

findEndNumCount++;
endIndex--;
أنا--؛
}
وإلا إذا (arr[i] == arr[startIndex] && arr[startIndex] != توقعNum)
{
لـ (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {توقعNum, arr[i] });
}

findStartNumCount++;
endIndex--;
أنا--؛
}
}
startIndex++;
}

نتيجة الإرجاع؛
}

ستقوم هذه الخوارزمية بتدمير بيانات المصفوفة الأصلية.

4. مقارنة زمن ثلاث خوارزميات

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

لم أقم أبدًا بإجراء الكثير من الأبحاث حول الخوارزميات، وآمل أن يقدم لي الخبراء بعض النصائح، وأعتقد أنه يجب أن يكون هناك حل أكثر مثالية.

5. جميع الرموز

الفراغ الثابت الرئيسي (سلسلة [] الحجج)
{
كونست إنت NUM_COUNT = 8000؛
const int MIN_NUM = -4;
كونست إنت MAX_NUM = 12؛
كونست إنت توتال = 8؛

int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);

//Console.WriteLine("الأرقام التي تم إنشاؤها هي:n------------------------------------ ---- -");
//PrintNumArray(arr);

// الطريقة العادية
TimeSpan NormalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ساعة الإيقاف NormalStw = new Stopwatch();
NormalStw.Start();

List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);

double NormalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMillithans;
NormalStw.Stop();
double NormalRealTime = NormalStw.Elapsed.TotalMillithans;

// طباعة النتيجة العادية
//Console.WriteLine("أزواج أرقام النتائج باستخدام الطريقة العادية هي:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);

// طريقة العودية
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ساعة الإيقاف recuStw = new Stopwatch();
recuStw.Start();

List<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);

double recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMillithans;
recuStw.Stop();
double recuRealTime = recuStw.Elapsed.TotalMillithans;

// طباعة نتيجة العودية
//Console.WriteLine("أزواج أرقام النتائج التي تستخدم طريقة الاسترداد هي:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);

// طريقة متقدمة
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ساعة الإيقاف advStw = ساعة الإيقاف الجديدة();
advStw.Start();

List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);

double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMillithans;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMillithans;

// طباعة النتيجة المتقدمة
//Console.WriteLine("أزواج أرقام النتائج باستخدام الطريقة المتقدمة هي:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);

Console.WriteLine("n==================nالوقت المستخدم:n---- ----------------------------------");
Console.WriteLine(String.Format("Normal : count - {0} Cpu Time - {1} Real Time - {2}", resultUseNormalWay.Count,normalCupTime,normalRealTime));
Console.WriteLine(String.Format("Recursion: count - {0} وقت وحدة المعالجة المركزية - {1} الوقت الحقيقي - {2}"، resultUseRecursionWay.Count، recuCupTime، recuRealTime));
Console.WriteLine(String.Format("Advanced : count - {0} Cpu Time - {1} Real Time - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));

Console.Read();
}

int ثابت خاص[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = new int[numCount];

Random rdm = new Random((int)DateTime.Now.Ticks);
لـ (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}

العودة آر؛
}

PrintNumArray (int[] arr) باطل ثابت خاص
{
لـ (int i = 0; i < arr.Length; i++)
{
إذا (i > 0 && i % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}

PrintNumPairs باطل ثابت خاص (List<int[]> numList)
{
لـ (int i = 0; i < numList.Count; i++)
{
إذا (i > 0 && i % 10 == 0)
{
Console.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Console.Write("n");
}

قائمة ثابتة خاصة<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();

لـ (int i = 0; i < arr.Length; i++)
{
int waitNum = sumTotal - arr[i];

لـ (int j = i + 1; j < arr.Length; j++)
{
إذا (arr[j] == تتوقعNum)
{
result.Add(new int[]{arr[i], المتوقعNum});
}
}
}

نتيجة الإرجاع؛
}

قائمة ثابتة خاصة<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
int waitNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;

لـ (int i = 1; i < length; i++)
{
إذا (arr[i] == تتوقعNum)
{
int CircleCount = arr[0] == تتوقعNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;

لـ (int j = 0; j <circleCount; j++)
{
result.Add(new int[] { arr[0], المتوقعNum });
}

findEndNumCount++;
}
وإلا إذا (arr[i] == arr[0])
{
لـ (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {توقعNum, arr[0] });
}
findStartNumCount++;
}
آخر
{
nextArr[nextLength++] = arr[i];
}
}

إذا (الطول التالي > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (عنصر int[] في النتيجة التالية)
{
result.Add(item);
}
}

نتيجة الإرجاع؛
}

قائمة ثابتة خاصة<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;

بينما (startIndex <endIndex)
{
int waitNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;

لـ (int i = startIndex + 1; i <= endIndex; i++)
{
إذا (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}

إذا (arr[i] == تتوقعNum)
{
int CircleCount = arr[startIndex] == تتوقعNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;

لـ (int iStart = 0; iStart <circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}

findEndNumCount++;
endIndex--;
أنا--؛
}
وإلا إذا (arr[i] == arr[startIndex] && arr[startIndex] != توقعNum)
{
لـ (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {توقعNum, arr[i] });
}

findStartNumCount++;
endIndex--;
أنا--؛
}
}
startIndex++;
}

نتيجة الإرجاع؛
}

-