1. Descrição do tópico
Existe um array a[1000], que armazena 1000 inteiros. Encontre todos os pares de números no array cuja soma é M. Por exemplo, a matriz é -1,2,4,6,5,3,4,2,9,0,8,3, então os pares de números cuja soma é 8 são (-1,9), (2, 6), (4,4), (5,3), (5,3), (0,8).
2. O algoritmo mais comum
No caso de complexidade irredutível, o algoritmo mais simples para este problema é o seguinte:
Lista estática privada<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
for (int i = 0; i <arr.Comprimento; i++)
{
int expectNum = somaTotal - arr[i];
for (int j = i + 1; j <arr.Comprimento; j++)
{
if (arr[j] == expectNum)
{
resultado.Add(new int[]{arr[i], expectNum});
}
}
}
resultado de retorno;
}
Use um loop de dois níveis para encontrar todos os pares cuja soma seja um número fixo sumTotal e armazene os pares encontrados em uma lista. No entanto, a complexidade deste algoritmo é um pouco alta e, na verdade, ele realiza algum trabalho repetitivo durante a travessia:
1) Não há necessidade de processar a sequência previamente emparelhada em loops subsequentes.
2) Ao procurar um número cuja soma seja sumTotal, deve haver alguns processos que podem ser usados mutuamente.
Com base nesses dois pontos, você pode citar algumas 01 ideias de mochila ou programação dinâmica (talvez de forma inadequada, tenho um entendimento superficial dessas duas ideias) para melhorar esse algoritmo e usar recursão para operar.
2. Use algoritmo recursivo
O código usando o algoritmo recursivo é o seguinte:
Lista estática privada<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
int[] nextArr = new int[comprimento];
int próximoComprimento = 0;
int expectNum = somaTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < comprimento; i++)
{
if (arr[i] == expectNum)
{
int CircleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
contagemCírculo += 1;
for (int j = 0; j <circularCount; j++)
{
resultado.Add(new int[] { arr[0], expectNum });
}
findEndNumCount++;
}
senão se (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
resultado.Add(new int[] { expectNum, arr[0] });
}
findStartNumCount++;
}
outro
{
nextArr[nextLength++] = arr[i];
}
}
if (próximoComprimento > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item em nextResult)
{
resultado.Adicionar(item);
}
}
resultado de retorno;
}
Após cada recursão, todos os números que não foram verificados quanto à correspondência são formados em um novo array para processamento na próxima recursão, mas isso desperdiça uma enorme quantidade de espaço, especialmente quando o array é grande, consumirá muita memória . Para não criar um novo array recursivamente todas as vezes, você pode processá-lo no array original, remover os números correspondentes do array e mover os números subsequentes para frente para substituí-los.
3. Algoritmo de mudança dinâmica de array
O código para este algoritmo é o seguinte:
Lista estática privada<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while (startIndex <endIndex)
{
int expectNum = somaTotal - 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;
contagemCírculo += 1;
for (int iStart = 0; iStart <circleCount; iStart++)
{
resultado.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
eu--;
}
senão if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
resultado.Add(new int[] { expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
eu--;
}
}
startIndex++;
}
resultado de retorno;
}
Este algoritmo destruirá os dados do array original.
4. Comparação do tempo de três algoritmos
Embora a intenção original dos dois últimos algoritmos seja reduzir a complexidade do tempo, eles não são muito melhores que o primeiro algoritmo em testes específicos. Em particular, o algoritmo recursivo leva significativamente mais tempo que o primeiro algoritmo. Talvez haja um problema fundamental com a minha ideia, ou talvez este exemplo seja muito simples e torne óbvio o tempo ocupado pelos dados móveis.
Nunca fiz muitas pesquisas sobre algoritmos. Espero que os especialistas possam me dar alguns conselhos. Acredito que deve haver uma solução mais perfeita.
5. Todos os códigos
vazio estático principal(string[] args)
{
const int NUM_COUNT = 8000;
const int MIN_NUM = -4;
const int MAX_NUM = 12;
const intTOTAL = 8;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Os números gerados são:n-------------------------------------------------- ---- -");
//PrintNumArray(arr);
//maneira normal
TimeSpan normalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronômetro normalStw = new Cronômetro();
normalStw.Start();
List<int[]> resultadoUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
normalStw.Stop();
double normalRealTime = normalStw.Elapsed.TotalMilliseconds;
// Imprime o resultado normal
//Console.WriteLine("Os pares de números resultantes usando a maneira normal são:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
//maneira de recursão
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronômetro recuStw = new Cronômetro();
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;
// Imprime o resultado da recursão
//Console.WriteLine("Os pares de números resultantes usando o método de recusa são:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Maneira avançada
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Cronômetro advStw = new Cronômetro();
advStw.Start();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMilliseconds;
//Imprime resultado avançado
//Console.WriteLine("Os pares de números de resultados usando a forma avançada são:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n================================nO tempo utilizado:n---- ----------------------------------");
Console.WriteLine(String.Format("Normal: contagem - {0} Tempo de CPU - {1} Tempo real - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Recursão: contagem - {0} Tempo de CPU - {1} Tempo real - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Avançado: contagem - {0} Tempo de CPU - {1} Tempo real - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Console.Leitura();
}
private static int[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = new int[numCount];
Rdm aleatório = new Random((int)DateTime.Now.Ticks);
for (int i = 0; i <arr.Comprimento; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
retornar chegada;
}
vazio estático privado PrintNumArray(int[] arr)
{
for (int i = 0; i <arr.Comprimento; i++)
{
se (eu > 0 && eu % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}
privado estático vazio PrintNumPairs(List<int[]> numList)
{
for (int i = 0; i < numList.Count; i++)
{
se (eu > 0 && eu % 10 == 0)
{
Console.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Console.Write("n");
}
Lista estática privada<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
for (int i = 0; i <arr.Comprimento; i++)
{
int expectNum = somaTotal - arr[i];
for (int j = i + 1; j <arr.Comprimento; j++)
{
if (arr[j] == expectNum)
{
resultado.Add(new int[]{arr[i], expectNum});
}
}
}
resultado de retorno;
}
Lista estática privada<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
int[] nextArr = new int[comprimento];
int próximoComprimento = 0;
int expectNum = somaTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < comprimento; i++)
{
if (arr[i] == expectNum)
{
int CircleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
contagemCírculo += 1;
for (int j = 0; j <circularCount; j++)
{
resultado.Add(new int[] { arr[0], expectNum });
}
findEndNumCount++;
}
senão se (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
resultado.Add(new int[] { expectNum, arr[0] });
}
findStartNumCount++;
}
outro
{
nextArr[nextLength++] = arr[i];
}
}
if (próximoComprimento > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item em nextResult)
{
resultado.Adicionar(item);
}
}
resultado de retorno;
}
Lista estática privada<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Lista<int[]> resultado = new Lista<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while (startIndex <endIndex)
{
int expectNum = somaTotal - 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;
contagemCírculo += 1;
for (int iStart = 0; iStart <circleCount; iStart++)
{
resultado.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
eu--;
}
senão if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
resultado.Add(new int[] { expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
eu--;
}
}
startIndex++;
}
resultado de retorno;
}
-