Является ли каждый рекурсивный алгоритм алгоритмом «разделяй и властвуй»?

Question

У меня проблема с домашней работой, и мне нужно решить эту проблему с помощью алгоритма «разделяй и властвуй».

Я решил этот алгоритм с помощью рекурсии.Использовал ли я «разделяй и властвуй» автоматически с помощью рекурсии?

Например, является ли приведенный ниже подход делением на алгоритм завоевания?Потому что я использую fun функцию в fun. (Рекурсивный вызов)

Код:

    #include <stdio.h>

/* int a[] = {-6,60,-10,20}; */
int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
int len = sizeof(a)/sizeof(*a);
int maxherearray[10];

int fun(int n);
int max(int a, int b);
int find_max(int a[], int len);
void print_array(int a[], int start_idx, int end_idx);

int start_idx = 0;  // Start of contiguous subarray giving max sum
int end_idx = 0;    // End of contiguous subarray giving max sum

#define NEG_INF (-100000)

int max_sum = NEG_INF;  // The max cont sum seen so far.

int main(void)
{
    start_idx = 0;
    end_idx = len - 1;
    maxherearray[0] = a[0];

    printf("Array a[]: ");
    print_array(a, 0, len-1);
    printf("\n");

    // Compute the necessary information to get max contiguous subarray
    fun(len - 1);
    printf("Max subarray value == %d\n", find_max(maxherearray, len));
    printf("\n");

    printf("Contiguous sums: ");
    print_array(maxherearray, 0, len - 1);
    printf("\n");

    printf("Contiguous subarray giving max sum: ");
    print_array(a, start_idx, end_idx);
    printf("\n\n");

    return 0;
}

int fun(int n)
{
    if(n==0)
        return a[0];

    int max_till_j = fun(n - 1);

    // Start of new contiguous sum
    if (a[n] > a[n] + max_till_j)
    {
        maxherearray[n] = a[n];

        if (maxherearray[n] > max_sum)
        {
            start_idx = end_idx = n;
            max_sum = maxherearray[n];
        }
    }
    // Add to current contiguous sum
    else
    {
        maxherearray[n] = a[n] + max_till_j;

        if (maxherearray[n] > max_sum)
        {
            end_idx = n;
            max_sum = maxherearray[n];
        }
    }

    return maxherearray[n];
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

// Print subarray a[i] to a[j], inclusive of end points.
void print_array(int a[], int i, int j)
{
    for (; i <= j; ++i) {
        printf("%d ", a[i]);
    }
}

int find_max(int a[], int len)
{
    int i;
    int max_val = NEG_INF;
    for (i = 0; i < len; ++i)
    {
        if (a[i] > max_val)
        {
            max_val = a[i];
        }
    }

    return max_val;
}

Answer 1

Каждая рекурсивная функция не обязательно является подходом «разделяй и властвуй».Существуют и другие подходы, такие как уменьшение и завоевание ( уменьшение на постоянный коэффициент , уменьшение на единицу , уменьшение на переменную ).

Является ли приведенный ниже подход делением на алгоритм завоевания?

Ваша функция точно уменьшается на постоянный коэффициент, который равен 1.Вы можете взглянуть на здесь .

Псевдокод для алгоритма «разделяй и властвуй» для поиска максимального подмассива

MaxSubarray(A,low,high)
//
if high == low   
   return (low, high, A[low]) // base case: only one element
else
   // divide and conquer
   mid = floor( (low + high)/2 )
   (leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
   (rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
   (xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
   // combine
   if leftsum >= rightsum and leftsum >= xsum
      return (leftlow,lefthigh,leftsum)
   else if rightsum >= leftsum and rightsum >= xsum
      return (rightlow,righthigh,rightsum)
   else
      return (xlow,xhigh,xsum)
   end if
end if

--------------------------------------------------------------

MaxXingSubarray(A,low,mid,high)
// Find a max-subarray of A[i..mid]
leftsum = -infty
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > leftsum
       leftsum = sum
       maxleft = i
    end if
end for
// Find a max-subarray of A[mid+1..j]
rightsum = -infty
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > rightsum
       rightsum = sum
       maxright = j
    end if
end for
// Return the indices i and j and the sum of the two subarrays
return (maxleft,maxright,leftsum + rightsum)

-----------------------------------------------------------

=== Remarks:

(1) Initial call: MaxSubarray(A,1,n)

(2) Divide by computing mid.
    Conquer by the two recursive alls to MaxSubarray.
    Combine by calling MaxXingSubarray and then determining
       which of the three results gives the maximum sum.

(3) Base case is when the subarray has only 1 element.

Answer 2

Не обязательно.Изучив парадигму функционального программирования, вы узнаете, что простой цикл for можно заменить на рекурсию

for i in range(x):
    body(i)

меняется на

def do_loop(x, _start=0):
    if _start < x:
         body(_start)
         do_loop(x, _start=_start+1)

, и совершенно очевидно, что не каждая итерацияалгоритм разделяй и властвуй.