Рекурсивная функция для определения количества непрерывных подпоследовательностей в массиве, имеющего сумму в заданном диапазоне

Question

Я написал это code. Идея состоит в том, чтобы разбить array на 2 части и найти количество подпоследовательностей, которые удовлетворяют данному условию. Теперь также может быть подпоследовательность с элементами обоих subarrays. Поэтому я написал функцию crossub.

Функция subarray работает бесконечно loop (она постоянно печатает оператор отладки "BBBBBBBB"). Я потратил некоторое время на это, но, думаю, мне нужна помощь.

Примечание : Новое в программировании. Я знаю, что код это кусок дерьма. Но мне становится лучше.

#include <stdio.h>
#include <stdlib.h>

void crossub(int * A,int mid, int start, int end, int lbound, int ubound, int **k)
{
    int leftsum  = A[mid];
    int crossum;
    int rightsum = 0;
    int i;int j;
    for(i = mid -1; i>=0; i--)
    {
        leftsum = leftsum + A[i];
        for(j = mid +1; j <=end; j++)
        {
            rightsum = rightsum + A[j];
            crossum = rightsum + leftsum;
            if (lbound <= crossum && crossum <= ubound) k++;
            else if(crossum > ubound) break;
        }
    }
    return;
}
void subarray(int * A, int start, int end, int lbound, int ubound, int *count)
{
    printf("BBBBBBBBB ");
    if(start == end) 
    {
        if(lbound <= A[start] && A[start] <= ubound)
        {
            count++;
        }
       return;
    }
    int **k; int mid;
    k = &count;
    while (start <= end)
    {
    mid = (start + end)/2;
    subarray(A, start, mid,lbound,ubound,count);
    subarray(A, mid +1, end,lbound,ubound,count);
    crossub(A, mid, start, end, lbound,ubound,k);
    }
    return;
}

int numRange(int* A, int n, int lbound, int ubound) 
{
    // printf("AAAAAAAAAAA");
    int p = 0;
    int *count;
    count = &p;
    subarray(A, 0, n-1,lbound,ubound, count);

    return p;
}
int main()
{
    int A[] = {30, 5,1,0,2, 15,20,25};
    int n = sizeof(A)/sizeof(A[0]);
    printf("%d", n);
    int lbound = 6; int ubound = 8;
    int k = numRange(A, n,lbound, ubound);
    printf("%d ", k);
    return 0;
}

Answer 1

Что касается вашего бесконечного цикла, проблема заключается в функции subarray, а именно:

while (start <= end)
{
    mid = (start + end)/2;
    subarray(A, start, mid,lbound,ubound,count);
    subarray(A, mid +1, end,lbound,ubound,count);
    crossub(A, mid, start, end, lbound,ubound,k);
}

Как видите, это будет продолжаться вечно, потому что вы никогда не меняете значения начала / конца, поэтому вы продолжаете вызывать subarray в одном и том же разделе.

Хотя, как уже говорилось в первом ответе, это может быть не лучшим способом, но вы можете удалить цикл while и посмотреть, работает ли он, даже если это может быть не лучшим решением.

Answer 2

Я не уверен, что рекурсия здесь уместна. Способ здесь состоит в том, чтобы всегда иметь диапазон и проверять его сумму. Начальный диапазон должен содержать один первый элемент (диапазон может быть определен через начальный и конечный индексы), начальное значение для суммы должно быть равно значению. Дальнейшая обработка:

• Если ваша сумма меньше, чем вы ищете, увеличьте диапазон, увеличив его конечный индекс и добавив значение нового элемента к текущему значению суммы диапазона;
• Если ваша сумма больше, чем вы ищете, уменьшите диапазон, увеличивая его начальный индекс и вычитая значение исключенного элемента из суммы диапазона;
• Если ваша сумма в порядке для вас, верните ее.

Работа с диапазонами:

• Если ваша сумма меньше, чем вы ищете, и вы не можете увеличить его индекс конца, потому что он указывает на последний элемент в массиве, который вы просматриваете, вы можете вернуть результат, который говорит, что диапазон не является удовлетворяющих вашим требованиям;
• Если ваша сумма больше, чем вы ищете, и вы не можете увеличить ее начальный индекс, так как он указывает на последний элемент в массиве, вы также можете вернуть тот же результат «без ответа».

Я уверен, что не существует эффективного способа борьбы с диапазонами с использованием стратегии «разделяй и властвуй».