c程序不接受最多100000个输入

Question

我用 c 编写了一个程序，该程序应该接受 1 到 100000 之间的输入，但是当我运行该程序时，我只接受最多 12773 的输入，但是我使用 long long unsigned int 来保存输入的数组。

如果我提供的输入小于 12774，程序会显示正确的行为，但不会超过该输入。 我做的程序是http://ideone.com/iXM1M0 我不明白c的这种奇怪行为。

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


unsigned long long int inversion_count(unsigned long long int *arr, unsigned long long int start, unsigned long long int end)
{
    unsigned long long int left_count, right_count, split_count = 0, i, left_arrend, j, no_ele;
    no_ele = end - start;
    unsigned long long int temp_arr[no_ele], k=0;
    if(no_ele == 1)        // this means that only one element is passed
        return 0;
    else
    {
        left_arrend = start + (no_ele/2);
        left_count = inversion_count(arr, start, left_arrend);
        right_count = inversion_count(arr, left_arrend, end);
        i = start;
        j = left_arrend;
        while((i< left_arrend) && (j < end))
        {
            if(arr[i] <= arr[j])
            {
                temp_arr[k] = arr[i];
                i++;
                k++;
            }
            else
            {
                split_count += left_arrend - i;
                temp_arr[k] = arr[j];
                j++;
                k++;
            }
        }
        while(i < left_arrend)
        {
            temp_arr[k] = arr[i];
            k++;
            i++;
        }
        while(j < end)
        {
            temp_arr[k] = arr[j];
            j++;
            k++;
        }

        for(i=start; i<end; i++)
            arr[i] = temp_arr[i-start];
        return left_count + right_count + split_count;
    }
}

int main()
{
    unsigned long long int num, n = 100000, i, result;
    unsigned long long int sum = 0;
    //    scanf("%lld", &n);
    unsigned long long int arr[n];
    for(i=0; i<n; i++)
    {
        scanf("%llu", &arr[i]);
        sum += arr[i];
    }

    result = inversion_count(arr, 0, n);
    //        for(i=0; i<n; i++)
    //            printf("%lld\n", arr[i]);
    printf("%llu\n", result);
    printf("sum = %llu\n", sum);
    printf("n = %llu\n", n);
    return 0;
}

Answer 1

我认为您的问题可能是堆栈空间不足。在您的 inversion_count() 函数中，您有一个 VLA:

unsigned long long int temp_arr[no_ele], k=0;

我怀疑这使用了太多空间，因为您正忙于递归。我不确定使用递归来计算数组中的反转次数有什么优势；我希望使用单个线性 channel 。事实上，如果您只需要计算反转次数，则不清楚是否需要在内存中保留最后一行和当前行以上的内容。