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[]> результат = новый List<int[]>();
for (int i = 0; i <arr.Length; i++)
{
int ожидаемыйNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
если (arr[j] == ожидаемое число)
{
result.Add(new int[]{arr[i],expectNum});
}
}
}
вернуть результат;
}
Используйте двухуровневый цикл, чтобы найти все пары, сумма которых представляет собой фиксированное число sumTotal, и сохраните найденные пары в списке. Однако сложность этого алгоритма немного высока, и во время обхода он фактически выполняет некоторую повторяющуюся работу:
1) Нет необходимости обрабатывать ранее спаренную последовательность в последующих циклах.
2) При поиске числа, сумма которого равна sumTotal, должны быть некоторые процессы, которые можно использовать совместно.
Основываясь на этих двух моментах, вы можете процитировать некоторые идеи ранца или динамического программирования (возможно, неуместно, я поверхностно понимаю эти две идеи), чтобы улучшить этот алгоритм и использовать рекурсию для работы.
2. Используйте рекурсивный алгоритм
Код, использующий рекурсивный алгоритм, выглядит следующим образом:
частный статический список<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> результат = новый List<int[]>();
int[] nextArr = новый int[длина];
интервал следующейдлины = 0;
int ожидаемыйNum = sumTotal - arr[0];
интервал findStartNumCount = 0;
интервал findEndNumCount = 0;
for (int я = 1; я <длина; я++)
{
если (arr[i] == ожидаемое число)
{
int CircleCount = arr[0] == ожидаемыйNum? findEndNumCount: findStartNumCount;
кругCount += 1;
for (int j = 0; j <circleCount; j++)
{
result.Add(new int[] { arr[0],expectNum});
}
найтиEndNumCount++;
}
иначе, если (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
еще
{
nextArr[nextLength++] = arr[i];
}
}
если (следующая длина > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (элемент int[] в nextResult)
{
результат.Добавить(элемент);
}
}
вернуть результат;
}
После каждой рекурсии все числа, не проверенные на совпадение, формируются в новый массив для обработки в следующей рекурсии, но при этом тратится огромное количество места, особенно когда массив большой, он будет потреблять много памяти. . Чтобы не создавать каждый раз рекурсивно новый массив, можно обработать его на исходном массиве, удалить совпадающие числа из массива и переместить последующие числа вперед, чтобы заменить их.
3. Алгоритм динамического изменения массива
Код этого алгоритма следующий:
частный статический список<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> результат = новый List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
в то время как (startIndex < endIndex)
{
int ожидаемыйNum = sumTotal - arr[startIndex];
интервал findStartNumCount = 0;
интервал findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
если (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
если (arr[i] == ожидаемое число)
{
int CircleCount = arr[startIndex] == ожидаемыйNum? findEndNumCount: findStartNumCount;
кругCount += 1;
for (int iStart = 0; iStart <circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
найтиEndNumCount++;
КонечныйИндекс--;
я--;
}
иначе, если (arr[i] == arr[startIndex] && arr[startIndex] != continueNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
КонечныйИндекс--;
я--;
}
}
стартовыйиндекс++;
}
вернуть результат;
}
Этот алгоритм уничтожит данные исходного массива.
4. Сравнение времени трёх алгоритмов
Хотя первоначальная цель последних двух алгоритмов состоит в сокращении временной сложности, в конкретных тестах они не намного лучше первого алгоритма. В частности, рекурсивный алгоритм занимает значительно больше времени, чем первый алгоритм. Возможно, в моей идее есть фундаментальная проблема, или, может быть, этот пример слишком прост и делает очевидным время, занимаемое мобильными данными.
Я никогда особо не исследовал алгоритмы. Надеюсь, эксперты дадут мне несколько советов. Я считаю, что должно быть более совершенное решение.
5. Все коды
static void Main(string[] args)
{
константное число NUM_COUNT = 8000;
константный интервал MIN_NUM = -4;
константный интервал MAX_NUM = 12;
const int ИТОГО = 8;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Сгенерированные числа:n------------------------------------ ---- -");
//PrintNumArray(arr);
//Обычный способ
TimeSpannormalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
СекундомерnormalStw = новый секундомер();
нормальныйStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
двойной нормальныйCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliсекунды;
нормальныйStw.Stop();
Double NormalRealTime = NormalStw.Elapsed.TotalMilliсекунды;
// Печатаем нормальный результат
//Console.WriteLine("Результирующие пары чисел обычным способом:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// Путь рекурсии
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Секундомер recuStw = новый секундомер();
recuStw.Старт();
List<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
двойной recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliсекунды;
recuStw.Стоп();
двойной recuRealTime = recuStw.Elapsed.TotalMilliсекунды;
// Печать результата рекурсии
//Console.WriteLine("Результирующие пары чисел с использованием способа редукции:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Продвинутый способ
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Секундомер advStw = новый секундомер();
advStw.Старт();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
двойной advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliсекунды;
advStw.Стоп();
двойной advRealTime = advStw.Elapsed.TotalMilliсекунды;
// Печать расширенного результата
//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("Рекурсия: count - {0} Время процессора - {1} Реальное время - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Дополнительно: count - {0} Время процессора - {1} Реальное время - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Консоль.Читать();
}
частный статический int [] GenerateArray (int numCount, int minValue, int maxValue)
{
int[] arr = новый int[numCount];
Случайный rdm = новый Random((int)DateTime.Now.Ticks);
for (int i = 0; i <arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
возврат обр;
}
Private static void PrintNumArray(int[] arr)
{
for (int i = 0; i <arr.Length; i++)
{
если (я > 0 && я % 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; я <numList.Count; i++)
{
если (я > 0 && я % 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[]> результат = новый List<int[]>();
for (int i = 0; i <arr.Length; i++)
{
int ожидаемыйNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
если (arr[j] == ожидаемое число)
{
result.Add(new int[]{arr[i],expectNum});
}
}
}
вернуть результат;
}
частный статический список<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> результат = новый List<int[]>();
int[] nextArr = новый int[длина];
интервал следующейдлины = 0;
int ожидаемыйNum = sumTotal - arr[0];
интервал findStartNumCount = 0;
интервал findEndNumCount = 0;
for (int я = 1; я <длина; я++)
{
если (arr[i] == ожидаемое число)
{
int CircleCount = arr[0] == ожидаемыйNum? findEndNumCount: findStartNumCount;
кругCount += 1;
for (int j = 0; j <circleCount; j++)
{
result.Add(new int[] { arr[0],expectNum});
}
найтиEndNumCount++;
}
иначе, если (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
еще
{
nextArr[nextLength++] = arr[i];
}
}
если (следующая длина > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (элемент int[] в nextResult)
{
результат.Добавить(элемент);
}
}
вернуть результат;
}
частный статический список<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> результат = новый List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
в то время как (startIndex < endIndex)
{
int ожидаемыйNum = sumTotal - arr[startIndex];
интервал findStartNumCount = 0;
интервал findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
если (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
если (arr[i] == ожидаемое число)
{
int CircleCount = arr[startIndex] == ожидаемыйNum? findEndNumCount: findStartNumCount;
кругCount += 1;
for (int iStart = 0; iStart <circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
найтиEndNumCount++;
КонечныйИндекс--;
я--;
}
иначе, если (arr[i] == arr[startIndex] && arr[startIndex] != continueNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
КонечныйИндекс--;
я--;
}
}
стартовыйиндекс++;
}
вернуть результат;
}
-