1. Descripción del tema
Hay una matriz a [1000], que almacena 1000 números enteros. Encuentre todos los pares de números en la matriz cuya suma es M. Por ejemplo, el array es -1,2,4,6,5,3,4,2,9,0,8,3, entonces los pares de números cuya suma es 8 son (-1,9), (2, 6), (4,4), (5,3), (5,3), (0,8).
2. El algoritmo más común.
En el caso de complejidad irreducible, el algoritmo más simple para este problema es el siguiente:
Lista estática privada<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
para (int i = 0; i < arr.Length; i++)
{
int expectNum = sumaTotal - arr[i];
para (int j = i + 1; j < arr.Length; j++)
{
si (arr[j] == expectNum)
{
resultado.Add(new int[]{arr[i], expectNum});
}
}
}
resultado de devolución;
}
Utilice un bucle de dos niveles para encontrar todos los pares cuya suma sea un número fijo sumTotal y almacene los pares encontrados en una Lista. Sin embargo, la complejidad de este algoritmo es un poco alta y, de hecho, realiza un trabajo repetitivo durante el recorrido:
1) No es necesario procesar la secuencia previamente emparejada en bucles posteriores.
2) Al buscar un número cuya suma sea sumTotal, debe haber algunos procesos que puedan usarse mutuamente.
Con base en estos dos puntos, puede citar algunas ideas de programación dinámica o de mochila 01 (tal vez de manera inapropiada, tengo una comprensión superficial de estas dos ideas) para mejorar este algoritmo y usar la recursividad para operar.
2. Utilice un algoritmo recursivo
El código que utiliza el algoritmo recursivo es el siguiente:
Lista estática privada<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
int[] nextArr = nuevo int[longitud];
int siguienteLongitud = 0;
int expectNum = sumaTotal - arr[0];
int encontrarNúmeroInicio = 0;
int findEndNumCount = 0;
para (int i = 1; i < longitud; i++)
{
si (arr[i] == expectNum)
{
int circuloCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
círculoCount += 1;
para (int j = 0; j < circuloCount; j++)
{
resultado.Add(new int[] {arr[0], expectNum });
}
encontrarEndNumCount++;
}
de lo contrario si (arreglo[i] == arreglo[0])
{
para (int j = 0; j < findEndNumCount; j++)
{
resultado.Add(new int[] { expectNum, arr[0] });
}
encontrarStartNumCount++;
}
demás
{
nextArr[nextLength++] = arr[i];
}
}
si (siguienteLongitud > 0)
{
Lista<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (elemento int[] en nextResult)
{
resultado.Agregar(elemento);
}
}
resultado de devolución;
}
Después de cada recursión, todos los números cuya coincidencia no se ha verificado se forman en una nueva matriz para procesar en la siguiente recursión, pero esto desperdicia una gran cantidad de espacio, especialmente cuando la matriz es grande, consumirá mucha memoria. . Para no crear una nueva matriz de forma recursiva cada vez, puede procesarla en la matriz original, eliminar los números coincidentes de la matriz y mover los números posteriores hacia adelante para reemplazarlos.
3. Algoritmo de cambio dinámico de matriz
El código de este algoritmo es el siguiente:
Lista estática privada<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
int startIndex = 0, endIndex = arr.Longitud - 1;
mientras (índice inicial < índice final)
{
int expectNum = sumaTotal - arr[startIndex];
int encontrarNúmeroInicio = 0;
int findEndNumCount = 0;
para (int i = índiceinicio + 1; i <= índicefinal; i++)
{
si (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
si (arr[i] == expectNum)
{
int círculoCount = arr[startIndex] == expectNum? findEndNumCount: findStartNumCount;
círculoCount += 1;
para (int iStart = 0; iStart < círculoCount; iStart++)
{
resultado.Add(new int[] {arr[startIndex], arr[i] });
}
encontrarEndNumCount++;
endIndex--;
i--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
para (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
resultado.Add(new int[] { expectNum, arr[i] });
}
encontrarStartNumCount++;
endIndex--;
i--;
}
}
inicioIndex++;
}
resultado de devolución;
}
Este algoritmo destruirá los datos de la matriz original.
4. Comparación del tiempo de tres algoritmos.
Aunque la intención original de los dos últimos algoritmos es reducir la complejidad del tiempo, no son mucho mejores que el primer algoritmo en pruebas específicas. En particular, el algoritmo recursivo tarda mucho más que el primer algoritmo. Quizás haya un problema fundamental con mi idea, o quizás este ejemplo sea demasiado simple y haga evidente el tiempo que ocupan los datos móviles.
Nunca he investigado mucho sobre algoritmos. Espero que los expertos puedan darme algún consejo. Creo que debe haber una solución más perfecta.
5. Todos los códigos
vacío estático principal (cadena [] argumentos)
{
constanteint NUM_COUNT = 8000;
constante int MIN_NUM = -4;
constanteint MAX_NUM = 12;
constante int TOTAL = 8;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Los números generados son:n------------------------------------ ---- -");
//ImprimirNumArray(arr);
//forma normal
TimeSpan normalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronómetro normalStw = nuevo Cronómetro();
normalStw.Inicio();
Lista<int[]> resultadoUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMillisegundos;
normalStw.Stop();
double normalRealTime = normalStw.Elapsed.TotalMillisegundos;
// Imprimir resultado normal
//Console.WriteLine("Los pares de números resultantes usando la forma normal son:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// forma recursiva
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronómetro recuStw = nuevo Cronómetro();
recuStw.Inicio();
Lista<int[]> resultadoUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
double recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMillisegundos;
recuStw.Stop();
doble recuRealTime = recuStw.Elapsed.TotalMillisegundos;
// Imprimir resultado de recursión
//Console.WriteLine("Los pares de números resultantes usando la forma recusiva son:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// forma avanzada
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronómetro advStw = nuevo Cronómetro();
advStw.Inicio();
Lista<int[]> resultadoUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMillisegundos;
advStw.Stop();
doble advRealTime = advStw.Elapsed.TotalMillisegundos;
// Imprimir resultado avanzado
//Console.WriteLine("Los pares de números resultantes usando la forma avanzada son:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n=================================nEl tiempo utilizado:n---- ----------------------------------");
Console.WriteLine(String.Format("Normal: recuento - {0} Tiempo de CPU - {1} Tiempo real - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Recursión: recuento - {0} Tiempo de CPU - {1} Tiempo real - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Avanzado: recuento - {0} Tiempo de CPU - {1} Tiempo real - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Consola.Read();
}
int estático privado [] GenerateArray (int numCount, int minValue, int maxValue)
{
int[] arr = nuevo int[numCount];
RDM aleatorio = new Random((int)DateTime.Now.Ticks);
para (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
volver llegar;
}
vacío estático privado PrintNumArray(int[] arr)
{
para (int i = 0; i < arr.Length; i++)
{
si (yo > 0 && yo % 20 == 0)
{
Consola.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Consola.Write("n");
}
vacío estático privado PrintNumPairs(List<int[]> numList)
{
para (int i = 0; i < numList.Count; i++)
{
si (yo > 0 && yo % 10 == 0)
{
Consola.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Consola.Write("n");
}
Lista estática privada<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
para (int i = 0; i < arr.Length; i++)
{
int expectNum = sumaTotal - arr[i];
para (int j = i + 1; j < arr.Length; j++)
{
si (arr[j] == expectNum)
{
resultado.Add(new int[]{arr[i], expectNum});
}
}
}
resultado de devolución;
}
Lista estática privada<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
int[] nextArr = nuevo int[longitud];
int siguienteLongitud = 0;
int expectNum = sumaTotal - arr[0];
int encontrarNúmeroInicio = 0;
int findEndNumCount = 0;
para (int i = 1; i < longitud; i++)
{
si (arr[i] == expectNum)
{
int circuloCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
círculoCount += 1;
para (int j = 0; j < circuloCount; j++)
{
resultado.Add(new int[] {arr[0], expectNum });
}
encontrarEndNumCount++;
}
de lo contrario si (arreglo[i] == arreglo[0])
{
para (int j = 0; j < findEndNumCount; j++)
{
resultado.Add(new int[] { expectNum, arr[0] });
}
encontrarStartNumCount++;
}
demás
{
nextArr[nextLength++] = arr[i];
}
}
si (siguienteLongitud > 0)
{
Lista<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (elemento int[] en nextResult)
{
resultado.Agregar(elemento);
}
}
resultado de devolución;
}
Lista estática privada<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = nueva Lista<int[]>();
int startIndex = 0, endIndex = arr.Longitud - 1;
mientras (índice inicial < índice final)
{
int expectNum = sumaTotal - arr[startIndex];
int encontrarNúmeroInicio = 0;
int findEndNumCount = 0;
para (int i = índiceinicio + 1; i <= índicefinal; i++)
{
si (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
si (arr[i] == expectNum)
{
int círculoCount = arr[startIndex] == expectNum? findEndNumCount: findStartNumCount;
círculoCount += 1;
para (int iStart = 0; iStart < círculoCount; iStart++)
{
resultado.Add(new int[] {arr[startIndex], arr[i] });
}
encontrarEndNumCount++;
endIndex--;
i--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
para (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
resultado.Add(new int[] { expectNum, arr[i] });
}
encontrarStartNumCount++;
endIndex--;
i--;
}
}
inicioIndex++;
}
resultado de devolución;
}
-