Cでn> = 34の場合、配列を使用して階乗値を格納すると間違った値が出力されるのはなぜですか

debugcn 投稿 Dev

MMJJQQ

33未満の階乗値は正しいです。

しかし、私のコードは以下のように34からうまくいきません：

34！=-134263930639604140847618609643520000000 
35！= 25226455986144929666651337523200000000 
36！= 908152415501217467999448150835200000000 
37！=-9348033593545046315979581580902400000000 
38！=-11627892614711760007224100074291200000000 
39！= 
18958590953758640281739902897356800000000

コードは次のとおりです。

#include <stdio.h>
#include <math.h>

#define N 100
int Fact(int a[], int n);
int a[N] = { 0 };

int main() {
    int n, i, j, index;
    printf("input n(1≤n≤40):");
    scanf_s("%d", &n);
    for (i = 1; i <= n; i++) { //printf every factorial value from 1 to 40
        for (j = 0; j < N; j++)
            a[j] = 0; /* reset the array as 0 in every loop */
        index = Fact(a, i);/*Calculates the factorial value and stores the result in array,
                        returning the array index of the highest bit of the factorial value*/
        printf("\n%d!=", i);
        for (j = index; j >= 1; --j)
            printf("%d", a[j]);
    }
    return 0;
}

int Fact(int a[], int n) {
    int i, j, temp, index = 1;
    a[1] = 1; //the index of array starts from 1, not 0
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= index; j++)
            a[j] *= i; //Multiply each position of the array by 1 to i
        for (j = 1; j < index; ++j) {
            if (a[j] > 9) { //Judging if every position of array needs a carry
                temp = a[j];
                a[j] = a[j] % 10;
                a[j + 1] += temp / 10;
            }
        }
        if (a[index] > 9) { //Judging if the highest position needs a carry
            temp = a[index];
            a[index] = a[index] % 10;
            a[++index] += temp / 10;
        }
    }
    return index;
}

期待される出力：

1！= 1 
2！= 2 
3！= 6 
4！= 24 
5！= 120 
6！= 720 
7！= 5040 
8！= 40320 
9！= 362880 
10！= 3628800 
11！= 39916800 
12！= 479001600 
13！= 6227020800 
14！= 87178291200 
15！= 1307674368000 
16！= 20922789888000 
17！= 355687428096000 
18！= 6402373705728000 
19！= 121645100408832000 
20！= 2432902008176640000 
21！= 51090942171709440000 
22！= 1124000727777607680000 
23！= 25852016738884976640000 
24！= 620448401733239439360000  
25！= 15511210043330985984000000
26！= 403291461126605635584000000 
27！= 10888869450418352160768000000 
28！= 304888344611713860501504000000 
29！= 8841761993739701954543616000000 
30！= 265252859812191058636308480000000 
31！= 8222838654177922817725562880000000 
32！= 263130836933693530167218012160000000 
33！= 8683317618811886495518194401280000000 
34！= 295232799039604140847618609643520000000 
35！= 10333147966386144929666651337523200000000 
36！= 371993326789901217467999448150835200000000 
37！= 13763753091226345046315979581580902400000000 
38！= 523022617466601111760007224100074291200000000 
39！= 20397882081197443358640281739902897356800000000
40！= 815915283247897734345611269596115894272000000000

SacrificerXY

Fact関数内で、コードのこの部分でオーバーフローが発生しています。

            if (a[index] > 9) {//Judging if the highest position needs a carry
                temp = a[index];
                a[index] = a[index] % 10;
                a[++index] += temp / 10;
            }

ソリューション：変更ifするwhileループ。

            while(a[index] > 9) {  //   <---- if to while
                temp = a[index];
                a[index] = a[index] % 10;
                a[++index] += temp / 10;
            }

説明：

私が理解できる限り、a配列には結果の階乗の各桁が含まれている必要があります。サイズはN100に初期化されます。数字の内部表現も逆になります。

10! = 362880 = [0, 8, 8, 2, 6, 3, ... rest of unused indices]
                               ^
                            a[index]

上記のスニペットでa[index]は、最上位桁を指しています。

a[index]より大きい場合は、1回だけ処理し9ます。私のテストでは、a[index]ゆっくりと忍び寄って大きな数になります。内部手順を1回実行した後でa[index] > 9も、の階乗については当てはまりますn>=15。したがって、条件が当てはまらなくなるまで、内部手順を実行する必要があります。

これは、a配列の有効数字の出力です。

1!=1
2!=2
3!=6
4!=2 4
5!=1 2 0
6!=7 2 0
7!=5 0 4 0
8!=4 0 3 2 0
9!=3 6 2 8 8 0
10!=3 6 2 8 8 0 0
11!=3 9 9 1 6 8 0 0
12!=4 7 9 0 0 1 6 0 0
13!=6 2 2 7 0 2 0 8 0 0
14!=8 7 1 7 8 2 9 1 2 0 0
15!=13 0 7 6 7 4 3 6 8 0 0 0
16!=20 9 2 2 7 8 9 8 8 8 0 0 0
17!=35 5 6 8 7 4 2 8 0 9 6 0 0 0
18!=64 0 2 3 7 3 7 0 5 7 2 8 0 0 0
19!=121 6 4 5 1 0 0 4 0 8 8 3 2 0 0 0
20!=243 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0
21!=510 9 0 9 4 2 1 7 1 7 0 9 4 4 0 0 0 0
22!=1124 0 0 0 7 2 7 7 7 7 6 0 7 6 8 0 0 0 0
23!=2585 2 0 1 6 7 3 8 8 8 4 9 7 6 6 4 0 0 0 0
24!=6204 4 8 4 0 1 7 3 3 2 3 9 4 3 9 3 6 0 0 0 0
25!=15511 2 1 0 0 4 3 3 3 0 9 8 5 9 8 4 0 0 0 0 0 0
26!=40329 1 4 6 1 1 2 6 6 0 5 6 3 5 5 8 4 0 0 0 0 0 0
27!=108888 6 9 4 5 0 4 1 8 3 5 2 1 6 0 7 6 8 0 0 0 0 0 0
28!=304888 3 4 4 6 1 1 7 1 3 8 6 0 5 0 1 5 0 4 0 0 0 0 0 0
29!=884176 1 9 9 3 7 3 9 7 0 1 9 5 4 5 4 3 6 1 6 0 0 0 0 0 0
30!=2652528 5 9 8 1 2 1 9 1 0 5 8 6 3 6 3 0 8 4 8 0 0 0 0 0 0 0
31!=8222838 6 5 4 1 7 7 9 2 2 8 1 7 7 2 5 5 6 2 8 8 0 0 0 0 0 0 0
32!=26313083 6 9 3 3 6 9 3 5 3 0 1 6 7 2 1 8 0 1 2 1 6 0 0 0 0 0 0 0
33!=86833176 1 8 8 1 1 8 8 6 4 9 5 5 1 8 1 9 4 4 0 1 2 8 0 0 0 0 0 0 0
34!=-1342639306 3 9 6 0 4 1 4 0 8 4 7 6 1 8 6 0 9 6 4 3 5 2 0 0 0 0 0 0 0
35!=25226455 9 8 6 1 4 4 9 2 9 6 6 6 6 5 1 3 3 7 5 2 3 2 0 0 0 0 0 0 0 0
36!=90815241 5 5 0 1 2 1 7 4 6 7 9 9 9 4 4 8 1 5 0 8 3 5 2 0 0 0 0 0 0 0 0
37!=-934803359 3 5 4 5 0 4 6 3 1 5 9 7 9 5 8 1 5 8 0 9 0 2 4 0 0 0 0 0 0 0 0
38!=-1162789261 4 7 1 1 7 6 0 0 0 7 2 2 4 1 0 0 0 7 4 2 9 1 2 0 0 0 0 0 0 0 0
39!=189585909 5 3 7 5 8 6 4 0 2 8 1 7 3 9 9 0 2 8 9 7 3 5 6 8 0 0 0 0 0 0 0 0
40!=-1006498211 5 0 3 4 5 6 1 1 2 6 9 5 9 6 1 1 5 8 9 4 2 7 2 0 0 0 0 0 0 0 0 0

ご覧のとおり、最上位桁a[index]がオーバーフローしています。この出力は、結果の配列を出力するときに数字の間にスペースを追加するだけで生成されます。

    int main(){
        // ...
        // for loop
            // calc factorial

            /* output the result */
           printf("\n%d!=", i);
            for (j = index; j >= 1; --j)
                printf("%d ", a[j]); //     <---- add space between digits


        // end for loop
        return 0;
    }

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]