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

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

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

如果您的总和小于您要查找的值，请扩大范围，增加其结束索引并将新项目的值添加到范围总和的当前值；
如果您的总和大于您要查找的总和，则减少范围以增加其起始索引并从范围的总和中减去排除项的值；
如果你的总和对你来说还可以，return它。

处理范围：

如果你的总和小于你要找的，并且你无法增加它的结束索引，因为它指向你正在查看的数组中的最后一项，你可以 return结果表明没有范围满足您的要求；
如果您的总和大于您要查找的值，并且您无法增加其起始索引，因为它指向数组中的最后一项，您也可以 return 相同 "no answer" 结果。

我敢肯定没有使用 "divide and conquer" 策略处理范围的有效方法。

Answer 2

关于你的无限循环，问题出在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);
}

如您所见，这将一直持续下去，因为您永远不会更改 start/end 的值，所以您会在同一部分继续调用 subarray。

尽管如第一个答案所述，这可能不是最佳方法，但您可以删除 while 循环并查看它是否有效，即使它可能不是最佳解决方案。

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

Recursive function to find the number of continuous sub-sequences in an array having a sum in the given range

c

arrays

recursion

subsequence