1. Description du sujet
Il existe un tableau a[1000], qui stocke 1000 entiers. Veuillez trouver toutes les paires de nombres dans le tableau dont la somme est M. Par exemple, le tableau est -1,2,4,6,5,3,4,2,9,0,8,3, alors les paires de nombres dont la somme est 8 sont (-1,9), (2, 6), (4,4), (5,3), (5,3), (0,8).
2. L'algorithme le plus courant
Dans le cas d’une complexité irréductible, l’algorithme le plus simple pour ce problème est le suivant :
Liste statique privée<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
pour (int i = 0; i < arr.Length; i++)
{
int expectNum = sommeTotal - arr[i];
pour (int j = i + 1; j < arr.Length; j++)
{
si (arr[j] == expectNum)
{
result.Add(new int[]{arr[i], expectNum});
}
}
}
renvoyer le résultat ;
}
Utilisez une boucle à deux niveaux pour rechercher toutes les paires dont la somme est un nombre fixe sumTotal et stockez les paires trouvées dans une liste. Cependant, la complexité de cet algorithme est un peu élevée et il effectue en fait un travail répétitif lors du parcours :
1) Il n’est pas nécessaire de traiter la séquence précédemment appariée dans les boucles suivantes.
2) Lors de la recherche d'un nombre dont la somme est sumTotal, certains processus peuvent être utilisés mutuellement.
Sur la base de ces deux points, vous pouvez citer quelques 01 idées de programmation sac à dos ou dynamique (peut-être de manière inappropriée, j'ai une compréhension superficielle de ces deux idées) pour améliorer cet algorithme et utiliser la récursivité pour fonctionner.
2. Utiliser un algorithme récursif
Le code utilisant l'algorithme récursif est le suivant :
liste statique privée<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
int[] nextArr = new int[longueur];
int longueur suivante = 0;
int expectNum = sommeTotal - arr[0];
int findStartNumCount = 0 ;
int findEndNumCount = 0;
pour (int i = 1; i < longueur; i++)
{
si (arr[i] == expectNum)
{
int circleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
cercleCount += 1 ;
pour (int j = 0; j < circleCount; j++)
{
result.Add(new int[] { arr[0], expectNum });
}
findEndNumCount++;
}
sinon si (arr[i] == arr[0])
{
pour (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
autre
{
nextArr[nextLength++] = arr[i];
}
}
si (longueur suivante > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (élément int[] dans nextResult)
{
result.Add(item);
}
}
renvoyer le résultat ;
}
Après chaque récursion, tous les nombres dont la correspondance n'a pas été vérifiée sont formés dans un nouveau tableau pour être traités lors de la prochaine récursion, mais cela gaspille énormément d'espace, surtout lorsque le tableau est grand, cela consommera beaucoup de mémoire. . Afin de ne pas créer un nouveau tableau de manière récursive à chaque fois, vous pouvez le traiter sur le tableau d'origine, supprimer les nombres correspondants du tableau et déplacer les nombres suivants vers l'avant pour les remplacer.
3. Algorithme de changement dynamique de tableau
Le code de cet algorithme est le suivant :
Liste statique privée<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
tandis que (startIndex < endIndex)
{
int expectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0 ;
int findEndNumCount = 0;
pour (int i = startIndex + 1; i <= endIndex; i++)
{
si (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
si (arr[i] == expectNum)
{
int circleCount = arr[startIndex] == expectNum ? findEndNumCount : findStartNumCount;
cercleCount += 1 ;
pour (int iStart = 0 ; iStart < circleCount ; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
je--;
}
sinon if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
pour (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
je--;
}
}
startIndex++;
}
renvoyer le résultat ;
}
Cet algorithme détruira les données du tableau d'origine.
4. Comparaison du temps de trois algorithmes
Bien que l'intention initiale de ces deux derniers algorithmes soit de réduire la complexité temporelle, ils ne sont pas bien meilleurs que le premier algorithme dans des tests spécifiques. En particulier, l'algorithme récursif prend beaucoup plus de temps que le premier algorithme. Peut-être y a-t-il un problème fondamental avec mon idée, ou peut-être que cet exemple est trop simple et rend évident le temps occupé par les données mobiles.
Je n'ai jamais fait beaucoup de recherches sur les algorithmes. J'espère que les experts pourront me donner des conseils. Je pense qu'il doit y avoir une solution plus parfaite.
5. Tous les codes
static void Main(string[] arguments)
{
const int NUM_COUNT = 8 000 ;
const int MIN_NUM = -4 ;
const int MAX_NUM = 12 ;
const entier TOTAL = 8 ;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Les nombres générés sont :n------------------------------------ ---- -");
//PrintNumArray(arr);
//Voie normale
TimeSpan normalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Chronomètre normalStw = new Chronomètre();
normalStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
normalStw.Stop();
double normalRealTime = normalStw.Elapsed.TotalMilliseconds ;
// Imprimer le résultat normal
//Console.WriteLine("Les paires de numéros de résultat utilisant la méthode normale sont :n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// Méthode récursive
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Chronomètre recuStw = new Chronomètre();
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 ;
// Imprimer le résultat de la récursion
//Console.WriteLine("Les paires de numéros de résultat utilisant la méthode de récusion sont :n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Méthode avancée
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Chronomètre advStw = new Chronomètre();
advStw.Start();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMilliseconds ;
// Imprimer le résultat avancé
//Console.WriteLine("Les paires de numéros de résultat utilisant la méthode avancée sont :n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n================================nLe temps utilisé :n---- --------------------");
Console.WriteLine(String.Format("Normal : nombre - {0} Temps CPU - {1} Temps réel - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Récursion : nombre - {0} Temps CPU - {1} Temps réel - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Advanced : count - {0} Temps CPU - {1} Temps réel - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Console.Read();
}
private static int[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = nouveau int[numCount];
Random rdm = new Random((int)DateTime.Now.Ticks);
pour (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
retour arr;
}
vide statique privé PrintNumArray (int [] arr)
{
pour (int i = 0; i < arr.Length; i++)
{
si (je > 0 && je % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}
vide statique privé PrintNumPairs(List<int[]> numList)
{
pour (int i = 0; i < numList.Count; i++)
{
si (je > 0 && je % 10 == 0)
{
Console.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Console.Write("n");
}
Liste statique privée<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
pour (int i = 0; i < arr.Length; i++)
{
int expectNum = sommeTotal - arr[i];
pour (int j = i + 1; j < arr.Length; j++)
{
si (arr[j] == expectNum)
{
result.Add(new int[]{arr[i], expectNum});
}
}
}
renvoyer le résultat ;
}
liste statique privée<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
int[] nextArr = new int[longueur];
int longueur suivante = 0;
int expectNum = sommeTotal - arr[0];
int findStartNumCount = 0 ;
int findEndNumCount = 0;
pour (int i = 1; i < longueur; i++)
{
si (arr[i] == expectNum)
{
int circleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
cercleCount += 1 ;
pour (int j = 0; j < circleCount; j++)
{
result.Add(new int[] { arr[0], expectNum });
}
findEndNumCount++;
}
sinon si (arr[i] == arr[0])
{
pour (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
autre
{
nextArr[nextLength++] = arr[i];
}
}
si (longueur suivante > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (élément int[] dans nextResult)
{
result.Add(item);
}
}
renvoyer le résultat ;
}
Liste statique privée<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Liste<int[]> résultat = new List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
tandis que (startIndex < endIndex)
{
int expectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0 ;
int findEndNumCount = 0;
pour (int i = startIndex + 1; i <= endIndex; i++)
{
si (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
si (arr[i] == expectNum)
{
int circleCount = arr[startIndex] == expectNum ? findEndNumCount : findStartNumCount;
cercleCount += 1 ;
pour (int iStart = 0 ; iStart < circleCount ; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
je--;
}
sinon if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
pour (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
je--;
}
}
startIndex++;
}
renvoyer le résultat ;
}
-