1. Themenbeschreibung
Es gibt ein Array a[1000], das 1000 ganze Zahlen speichert. Bitte finden Sie alle Zahlenpaare im Array, deren Summe M ist. Das Array ist beispielsweise -1,2,4,6,5,3,4,2,9,0,8,3, dann sind die Zahlenpaare, deren Summe 8 ist, (-1,9), (2, 6), ( 4,4), (5,3), (5,3), (0,8).
2. Der gebräuchlichste Algorithmus
Im Fall irreduzibler Komplexität lautet der einfachste Algorithmus für dieses Problem wie folgt:
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
intexpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == ExpectNum)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
Ergebnis zurückgeben;
}
Verwenden Sie eine zweistufige Schleife, um alle Paare zu finden, deren Summe eine feste Zahl sumTotal ist, und speichern Sie die gefundenen Paare in einer Liste. Allerdings ist die Komplexität dieses Algorithmus etwas hoch und er führt während des Durchlaufs tatsächlich einige sich wiederholende Arbeiten aus:
1) Es besteht keine Notwendigkeit, die zuvor gepaarte Sequenz in nachfolgenden Schleifen zu verarbeiten.
2) Bei der Suche nach einer Zahl, deren Summe sumTotal ist, sollten einige Prozesse vorhanden sein, die gegenseitig verwendet werden können.
Basierend auf diesen beiden Punkten können Sie einige 01-Rucksack- oder dynamische Programmierideen zitieren (vielleicht unangemessen, ich habe ein oberflächliches Verständnis dieser beiden Ideen), um diesen Algorithmus zu verbessern und Rekursion für den Betrieb zu verwenden.
2. Verwenden Sie einen rekursiven Algorithmus
Der Code, der den rekursiven Algorithmus verwendet, lautet wie folgt:
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
intexpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < length; i++)
{
if (arr[i] == ExpectNum)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
sonst wenn (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0]});
}
findStartNumCount++;
}
anders
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] Element in nextResult)
{
result.Add(item);
}
}
Ergebnis zurückgeben;
}
Nach jeder Rekursion werden alle Zahlen, die nicht auf Übereinstimmung überprüft wurden, in einem neuen Array zur Verarbeitung in der nächsten Rekursion zusammengefasst. Dadurch wird jedoch viel Platz verschwendet, insbesondere wenn das Array groß ist, wird viel Speicher verbraucht . Um nicht jedes Mal rekursiv ein neues Array zu erstellen, können Sie es auf dem ursprünglichen Array verarbeiten, die übereinstimmenden Zahlen aus dem Array entfernen und die nachfolgenden Zahlen nach vorne verschieben, um sie zu ersetzen.
3. Algorithmus zur dynamischen Änderung des Arrays
Der Code für diesen Algorithmus lautet wie folgt:
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while (startIndex < endIndex)
{
intexpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == ExpectNum)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
ich--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i]});
}
findStartNumCount++;
endIndex--;
ich--;
}
}
startIndex++;
}
Ergebnis zurückgeben;
}
Dieser Algorithmus zerstört die Daten des ursprünglichen Arrays.
4. Vergleich der Zeit von drei Algorithmen
Obwohl die ursprüngliche Absicht der beiden letztgenannten Algorithmen darin besteht, die Zeitkomplexität zu reduzieren, sind sie in bestimmten Tests nicht viel besser als der erste Algorithmus. Insbesondere dauert der rekursive Algorithmus deutlich länger als der erste Algorithmus. Vielleicht gibt es ein grundlegendes Problem mit meiner Idee, oder vielleicht ist dieses Beispiel zu einfach und macht den Zeitaufwand für mobile Daten deutlich.
Ich habe noch nie viel über Algorithmen geforscht. Ich hoffe, dass Experten mir einen Rat geben können. Ich glaube, dass es eine perfektere Lösung geben muss.
5. Alle Codes
static void Main(string[] args)
{
const int NUM_COUNT = 8000;
const int MIN_NUM = -4;
const int MAX_NUM = 12;
const int TOTAL = 8;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Die generierten Zahlen sind:n------------------------------------ ---- -");
//PrintNumArray(arr);
//Normaler Weg
TimeSpan normalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stoppuhr normalStw = new Stopwatch();
normalStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
normalStw.Stop();
double normalRealTime = normalStw.Elapsed.TotalMilliseconds;
// Normales Ergebnis drucken
//Console.WriteLine("Die resultierenden Zahlenpaare auf normale Weise sind:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// Rekursionsmethode
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stoppuhr recuStw = new Stopwatch();
recuStw.Start();
List<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
double recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliseconds;
recuStw.Stop();
double recuRealTime = recuStw.Elapsed.TotalMilliseconds;
// Rekursionsergebnis drucken
//Console.WriteLine("Die Ergebniszahlenpaare unter Verwendung der Rekussionsmethode sind:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Fortgeschrittener Weg
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stoppuhr advStw = new Stopwatch();
advStw.Start();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMilliseconds;
// Erweitertes Ergebnis drucken
//Console.WriteLine("Die Ergebniszahlenpaare bei Verwendung der erweiterten Methode sind:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n===============================nDie verwendete Zeit:n---- ----------------------------------");
Console.WriteLine(String.Format("Normal : count - {0} CPU-Zeit - {1} Echtzeit - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Rekursion: count - {0} CPU-Zeit - {1} Echtzeit - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Advanced : count - {0} Cpu Time - {1} Real Time - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Console.Read();
}
private static int[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = new int[numCount];
Random rdm = new Random((int)DateTime.Now.Ticks);
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
Rückkehr arr;
}
private static void PrintNumArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (i > 0 && i % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}
private static void PrintNumPairs(List<int[]> numList)
{
for (int i = 0; i < numList.Count; i++)
{
if (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");
}
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
intexpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == ExpectNum)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
Ergebnis zurückgeben;
}
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
intexpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < length; i++)
{
if (arr[i] == ExpectNum)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
sonst wenn (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0]});
}
findStartNumCount++;
}
anders
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] Element in nextResult)
{
result.Add(item);
}
}
Ergebnis zurückgeben;
}
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while (startIndex < endIndex)
{
intexpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == ExpectNum)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
ich--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i]});
}
findStartNumCount++;
endIndex--;
ich--;
}
}
startIndex++;
}
Ergebnis zurückgeben;
}
-