Как вернуть правильное значение, когда алгоритм «Разделяй и властвуй» (для 1-D ближайших пар) выполнил свою работу?
Мне нужно найти ближайшую пару чисел целочисленного массива. Например: если у меня есть {25, 13, 59, 7, 16} чисел, мой результат должен быть | 13 — 16 | = 3. Поэтому я пытаюсь решить проблему, используя алгоритм «Разделяй и властвуй». Но когда я получаю различия чисел от подзадач, я не могу их сохранить и сравнить. Я вижу, где моя программа работает неправильно, когда я отлаживаю ее, но не могу найти решение в течение нескольких часов.
Вот моя функция:
int closestPairs(int list[], int first, int last)
{
if (last - first == 1)
return 0;
else if (last - first == 2)
return abs(list[first] - list[last - 1]);
int median = (first + last) / 2;
int left = closestPairs(list, first, median);
int right = closestPairs(list, median, last);
int temp = abs(list[first] - list[last - 1]);
if (abs(left - right) < temp)
temp = abs(left - right);
return temp;
}
А вот и функция драйвера:
int main()
{
int list[] = { 34, 23, 48 , 4, 66, 69};
int n = sizeof(list) / sizeof(int);
cout << closestPairs(list, 0, n) << endl;
return 0;
}
Итак, как я могу сохранить значение, полученное из abs (влево — вправо), и посмотреть, меньше ли оно или больше следующего значения? Или я не прав и все делаю не так? Заранее спасибо.
Решение
Мне кажется, что концепции использования рекурсии для поиска решения и сохранения значения для сравнения со следующей итерацией в данном случае являются противоположными. Сохранение переменной для сравнения в рекурсивной функции выглядит как беспорядок (и требует некоторой существенной реструктуризации вашего кода). Насколько я понимаю, идея вашего алгоритма «разделяй и властвуй» состоит в том, чтобы взять большой список целых и разбить его на более мелкие списки и дать наилучший из возможных ответов, чтобы пройти по цепочке. Вот как я вижу это на основе вашего кода (используя в основном псевдокод):
int FindClosest(int list[],int first,int last)
{
if(number of elements in list == 2)
{
return (int2 - int1)
}
if(number of elements in list == 3){
{
if((int3-int2)<(int2 - int2))
return (int3-int2)
else
return (int2-int1)
}
if(number of elements in list >3)
{
subList1 = oneSubGroupofElements(list)
subList2 = anotherSubGroupofelements(list)
if(FindClosest(subList1)<FindClosest(subList2))
return Findclosest(subList1)
else
return FindClosest(subList2)
}
}
Есть еще одна проблема с этим методом, которую вы можете увидеть для списков с более чем 2 элементами, потому что ваш результат основан на попарных соседях, вы должны учитывать, что вы не можете просто разделить список пополам. Например:
int list[] = {1,4,5,9}
Это вызовет проблемы, если вы просто разделите список на два списка из двух элементов, так как разница между 4 и 5 не будет учтена (что будет правильным ответом). Ваши подсписки должны будут включать перекрытие, чтобы хотя бы один из подсписков возвращал 5-4 при вызове из FindClosest.
Другие решения
Вы должны отсортировать список, прежде чем найти ближайшую пару, используя технику «разделяй и властвуй». Потому что это исключает множество угловых случаев.