c - 求和在给定范围内的数组中的连续子序列数的递归函数

Question

我写了这个代码。思路是将数组分成2部分，找出满足给定条件的子序列的个数。现在还可以有一个子序列，其元素来自两个 subarrays。因此，我编写了 crossub 函数。

子数组 函数正在进行无限循环(它不断打印调试语句"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

我不确定递归在这里是否相关。这里的方法是始终有一个范围并检查它的总和。初始范围应包含单个第一项(范围可以通过开始和结束索引定义)，sum 的初始值应等于 的值。进一步处理是:

• 如果您的总和小于您要查找的总和，则扩大范围，增加其结束索引并将新项目的值添加到范围总和的当前值；
• 如果您的总和大于您要查找的总和，则减少范围，增加其起始索引并从范围的总和中减去排除项的值；
• 如果您的金额合适，请退还。

处理范围:

• 如果你的总和小于你正在寻找的，并且你无法增加它的结束索引，因为它指向你正在查看的数组中的最后一项，你可能会返回一个结果，表明没有范围是满足您的要求；
• 如果你的总和大于你正在寻找的，并且你无法增加它的起始索引，因为它指向数组中的最后一项，你也可能返回相同的“无答案”结果。

我确信没有使用“分而治之”策略处理范围的有效方法。