时间戳

首页 > 解决方案 > 递归函数，用于查找数组中连续子序列的数量，其总和在给定范围内

c - 递归函数，用于查找数组中连续子序列的数量，其总和在给定范围内

问题描述

我写了这个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;
}

标签： carraysrecursionsubsequence

解决方案

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

  • 如果您的总和小于您正在寻找的，请扩大范围，增加其结束索引并将新项目的值添加到范围总和的当前值；
  • 如果您的总和大于您正在寻找的，请减少范围，增加其起始索引并从范围的总和中减去排除项的值；
  • 如果您的金额对您来说还可以，请退还。

处理范围：

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

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

推荐阅读