-1

我正在编写代码来查找 C 中的最大和连续子数组。在我看来，逻辑似乎很好，但输出仍然不正确。请查看代码。在三个循环中，第二个循环从第一个值运行，保持第一个循环的值固定，第三个循环是获取子数组的总和。请查看代码

#include<stdio.h>
int A[10],i,j;
void lsa(int A[],int n)
{
    int m,l,z,max=0,sum;
    for(m=0;m<n;m++)
    {
        sum=0;
        for(l=0;l<n;l++)
        {
            for(z=m;z<=l;z++)
            {
                if(m==l)                 //maximum sum from a contiguous sub array
                {
                }
               else
                {
                    sum=A[z]+A[l];
                    if(sum>max)
                    {
                        max=sum;
                        i=m;
                        j=l;
                     }
                 }
             }
        }
    }
}
void main()
{
    int n,p;
    printf("enter size of array\n");
    scanf("%d",&n);
    printf("enter array elements\n");        //creation of array
    for(p=0;p<n;p++)
        scanf("%d",&A[p]);
        lsa(A,n);
        printf("sub array is\n");
        for(p=i;p<j;p++)
        {
             printf("%d ",A[p]);
        }
}
4

1 回答 1

0

你的代码有很多问题。

在函数的第一个for循环中main，您有：

for(p=0;p<n;p++)
    scanf("%d",&A[i]);

  • i是全局变量且未初始化，因此您甚至没有将元素正确扫描到元素中

  • 你搞砸了你的lsa函数，即使上面的 for 循环是固定的，它也不会产生正确的结果

  • 并且您的代码的限制之一是它仅适用于大小10或更小的数组

我了解您想要找到最大连续数组的方式..正如您所说：

  • 第二个循环从第一个值运行，保持第一个循环的值固定
  • 第三个循环是获取子数组的总和

我会说与其制作第三个循环并使代码看起来很混乱，不如将其分解为另一个计算子数组总和的函数

解决方案 ：

在这里，我提供了一个适用于任何大小数组的解决方案......只需使用动态数组分配

注意： lsa代表“最大连续子阵列”

  • 这是主要函数、函数声明和全局变量：

（说明在评论中给出）

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

//array pointer
int *array;
//size of lsa and its starting index value, same as i,j in your code
int lsa_size=1,lsa_start_index=0;

//function to find sum of sub array
int sum(int size_of_array, int start_index);

//the lsa function in your code
void lsaf(int *array,int size_of_array);

//main funtion
int main()
{
    int size, index;

    //scanning size of input array
    printf("enter size of array\n");
    scanf("%d",&size);

    //creates required amount of space for array
    array=malloc(size*sizeof(int));
    if(array==NULL) //check if successfully created or not
    {
        //if not successful exit by returning 1
        printf(" memory creation unsuccessful\n enter any key to exit : ");
        exit(1);
    }

    //input of array elements
    printf("enter array elements\n");
    for(index=0 ; index < size ; index++)
        scanf("%d",&array[index]);

    //function call ... function described below
    lsaf(array,size);

    //printing largest contiguous sub-array
    printf("answer : ");
    for(index=0 ; index < lsa_size ; index++)
    {
        printf("(%d)->",array[lsa_start_index]);
        lsa_start_index++;
    }

    printf("*end*\n\n");

    //freeing allocated memory
    free(array);

    return 0;
}//main function

现在，lsa查找函数（我将其命名为lsaf）：

void lsaf(int *array,int size_of_array)
{
    int subarray_size,start_index,number_of_arrays;
    int lsa_sum=sum(1,0);//initializing sum of lsa as first element
    int subarray_sum;

    for(subarray_size = 1; subarray_size <= size_of_array ; subarray_size++)
    {
        number_of_arrays = size_of_array - subarray_size +1;
        for(start_index=0;start_index < number_of_arrays ; start_index++)
        {
            subarray_sum=sum( subarray_size,start_index);
            if(subarray_sum >= lsa_sum)
            {
                //updating lsa size and starting index
                lsa_sum=subarray_sum;
                lsa_size=subarray_size;
                lsa_start_index=start_index;
            }
        }//start_index loop
    }//subarray_size loop
}//lsaf function
  • 第一个循环决定子数组的大小
  • 第二个循环决定子数组的起始索引

现在我创建了函数sum()，而不是第三个循环，它计算子数组元素的总和：

int sum(int size_of_array, int start_index)
{
    int add=0,index;
    for(index=0; index < size_of_array ; index++)
    {
        add+=array[start_index];
        start_index++;
    }
    return add;
}//sum function
  • 所以我没有制作3个循环，而是为第三个循环制作了一个函数，我调用它来计算子数组的总和

我希望您了解上述功能...如果有任何疑问，请随时通过评论问我:)

因此，将所有代码放在一起将是：

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

//array pointer
int *array;
//size of lsa and its starting index value
int lsa_size=1,lsa_start_index=0;

//function to find sum of sub array
int sum(int size_of_array, int start_index);

//the lsa function
void lsaf(int *array,int size_of_array);

//main funtion
int main()
{
    int size, index;

    //scanning size of input array
    printf("enter size of array\n");
    scanf("%d",&size);

    //creates required amount of space for array
    array=malloc(size*sizeof(int));
    if(array==NULL) //check if successfully created or not
    {
        //if not successful exit by returning 1
        printf(" memory creation unsuccessful\n enter any key to exit : ");
        exit(1);
    }

    //input of array elements
    printf("enter array elements\n");
    for(index=0 ; index < size ; index++)
        scanf("%d",&array[index]);

    //function call
    lsaf(array,size);

    //printing largest contiguous sub-array
    printf("answer : ");
    for(index=0 ; index < lsa_size ; index++)
    {
        printf("(%d)->",array[lsa_start_index]);
        lsa_start_index++;
    }

    printf("*end*\n\n");

    //freeing allocated memory
    free(array);

    return 0;
}//main function


int sum(int size_of_array, int start_index)
{
    int add=0,index;
    for(index=0; index < size_of_array ; index++)
    {
        add+=array[start_index];
        start_index++;
    }
    return add;
}//sum function


void lsaf(int *array,int size_of_array)
{
    int subarray_size,start_index,number_of_arrays;
    int lsa_sum=sum(1,0);//initializing sum of lsa as first element
    int subarray_sum;

    for(subarray_size = 1; subarray_size <= size_of_array ; subarray_size++)
    {
        number_of_arrays = size_of_array - subarray_size +1;
        for(start_index=0;start_index < number_of_arrays ; start_index++)
        {
            subarray_sum=sum( subarray_size,start_index);
            if(subarray_sum >= lsa_sum)
            {
                //updating lsa size and starting index
                lsa_sum=subarray_sum;
                lsa_size=subarray_size;
                lsa_start_index=start_index;
            }
        }//start_index loop
    }//subarray_size loop
}//lsaf function

样本输入和输出：

enter size of array
6
enter array elements
1
-3
0
2
11
-90
answer : (0)->(2)->(11)->*end*
于 2016-06-15T17:29:02.790 回答