0

1から100000までの入力を受け取るはずのcでプログラムを作成しますが、プログラムを実行すると、最大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;
}
4

2 に答える 2

2

あなたの問題は、スタックスペースが不足している可能性が高いと思います。inversion_count()関数には、VLA があります。

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

そして、再帰に忙しいので、スペースを使いすぎているのではないかと思います。再帰を使用して配列内の反転の数をカウントすることに利点があるかどうかはわかりません。単一の線形パスを使用することを期待しています。実際、反転のみをカウントする必要がある場合、最後の行と現在の行以上をメモリに保持する必要があるかどうかは明らかではありません。

于 2013-02-10T05:16:49.587 に答える
0

これは、C ではなく ideone.com の問題です。ideone.com には入力テキスト ボックスの制限 (最大サイズ) があり、入力でこれらの制限を超えています。

コンパイラをローカル コンピューターにインストールしてそこで作業を行うか、プログラムを書き直します。入力は連続する整数のみであるため、入力から読み取る代わりにプログラムで生成できます。

于 2013-02-10T05:14:19.463 に答える