Неточная факторная программа C ++

Question

Я написал реализацию следующего урока: LINK

По сути, поскольку C / C ++ не имеет BIG Integer, мы храним факториальные десятичные значения в массиве. Это эквивалентно написанию умножения, которое выполняет умножение, которому учат дети в школах.

Проблема: отлично работает для значений до 17! после этого (18 !, 19!, ...) он не выводит правильные значения.

#include <iostream>
using namespace std;

int main(){
    int fact[1000]={1};
    int n; scanf("%d", &n); //n are the number of factorials we will calculate
    while(n--){
        int number; scanf("%d", &number);   //scan the number
        if(number == 0) printf("%d", 1);
        int flag = number;
        int index = 0, length = 0;
        //following lines we find the length of the entered number
        while(flag!=0){
            fact[index] = flag%10;
            flag /= 10;
            index++; length++;
        }
        //following lines are the multiplication code
        while(number>1){
            index = 0;
            int temp = 0;
            number--;
            for(index = 0; index<length; index++){
                int x = (fact[index] * number) + temp;
                fact[index] = x%10;
                temp = x/10;
            }
            //here we append the carry over left from multiplication
            while(temp){
                fact[index] = temp%10;
                temp /= 10;
                length++;
            }
        }
        //print the array from most to least significant digit
        for(int i = length-1; i>=0; i--){
            printf("%d", fact[i]);
        }
        printf("\n");
    }
    return 0;
}

Answer 1

Для начала вам нужно быть очень осторожным с:

long long int x = (fact[index] * number) + temp;

Поскольку fact[], number и temp - это все int типы, расчет будет сделано как int и расширено только до long long при помещении значения в x.

Вам будет лучше:

long long x = fact[index];
x *= number;
x += temp;

Таким образом, он становится long long достаточно рано, чтобы вычисления были выполнены с этим типом.

---

Однако это на самом деле не исправляет вашу проблему, поэтому давайте изменим ваш коднемного, чтобы увидеть, в чем проблема:

#include <iostream>
using namespace std;

int main(){
    int fact[1000]={1};
    int n = 18, numberx = 0;
    while(n-- > 0){
        int number = ++numberx;
        if(number == 0) { printf("%d", 1); continue; }
        int flag = number;
        int index = 0, length = 0;
        //following lines we find the length of the entered number
        while(flag!=0){
            fact[index] = flag%10;
            flag /= 10;
            index++; length++;
        }
        //following lines are the multiplication code
        while(number>1){
            index = 0;
            int temp = 0;
            number--;
            for(index = 0; index<length; index++){
                long long int x = fact[index];
                x *= number;
                x += temp;
                fact[index] = x%10;
                temp = x/10;
            }
            //here we append the carry over left from multiplication
            while(temp){
                fact[index] = temp%10;
                temp /= 10;
                length++;
            }
        }
        //print the array from most to least significant digit
        printf("%d! = ", number);
        for(int i = length-1; i>=0; i--){
            printf("%d ", fact[i]);
        }
        printf("\n");
    }
    return 0;
}

Запуск этого дает вам:

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! = 1 3 0 7 6 7 4 3 6 8 0 0 0
16! = 2 0 9 2 2 7 8 9 8 8 8 0 0 0
17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0
18! = 1 9 9 1 0 4 7 1 7 3 8 5 7 2 8 0 0 0

, то есть, как вы говорите, все в порядке до 18 !, где, если не удается.И, на самом деле, вы можете увидеть соотношение между 17!и 18!это около 500, а не 18, так что это то, где мы должны смотреть.

Давайте сначала удалим посторонние вещи, начиная с в 17 !.Это можно сделать, просто изменив пару начальных значений:

int n = 2, numberx = 16;

, и это даст:

17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0
18! = 1 9 9 1 0 4 7 1 7 3 8 5 7 2 8 0 0 0

Затем мы можем добавить отладочный код, чтобы увидеть, что происходит, и выводить временные результатыпуть.Основным циклом может стать:

while(number>1){
    index = 0;
    int temp = 0;
    number--;
    if (numberx > 17) printf("\n");
    for(index = 0; index<length; index++){
        if (numberx > 17) printf("index %d fact[] %d number %d temp %d", index, fact[index], number, temp);
        long long int x = fact[index];
        x *= number;
        x += temp;
        fact[index] = x%10;
        temp = x/10;
        if (numberx > 17) printf(" -> fact[] %d temp %d\n", fact[index], temp);
    }
    //here we append the carry over left from multiplication
    while(temp){
        fact[index] = temp%10;
        temp /= 10;
        length++;
    }
    if (numberx > 17) {
        printf("temp: ");
        for(int i = length-1; i>=0; i--){
            printf("%d ", fact[i]);
        }
        printf("\n");
    }
}

Это показывает вам * точно, где что-то идет не так (добавлено мной // битов):

17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0

index 0 fact[] 8 number 17 temp 0 -> fact[] 6 temp 13
index 1 fact[] 1 number 17 temp 13 -> fact[] 0 temp 3
temp: 3 0 6 // okay: 18 * 17 = 306

index 0 fact[] 6 number 16 temp 0 -> fact[] 6 temp 9
index 1 fact[] 0 number 16 temp 9 -> fact[] 9 temp 0
index 2 fact[] 3 number 16 temp 0 -> fact[] 8 temp 4
temp: 4 8 9 6 // okay 306 * 16 = 4896

index 0 fact[] 6 number 15 temp 0 -> fact[] 0 temp 9
index 1 fact[] 9 number 15 temp 9 -> fact[] 4 temp 14
index 2 fact[] 8 number 15 temp 14 -> fact[] 4 temp 13
index 3 fact[] 4 number 15 temp 13 -> fact[] 3 temp 7
temp: 7 3 4 4 0 // okay 4896 * 15 = 73440

index 0 fact[] 0 number 14 temp 0 -> fact[] 0 temp 0
index 1 fact[] 4 number 14 temp 0 -> fact[] 6 temp 5
index 2 fact[] 4 number 14 temp 5 -> fact[] 1 temp 6
index 3 fact[] 3 number 14 temp 6 -> fact[] 8 temp 4
index 4 fact[] 7 number 14 temp 4 -> fact[] 2 temp 10
temp: 8 1 2 8 1 6 0 // no good: 73440 * 14 = 10128160 !!!
      1 0 2 8 1 6 0 // is what it should be

С небольшим количествомдумал, что это, по-видимому, точка, в которой конечный «перенос» умножения больше девяти, то есть почти наверняка в коде для обработки:

while(temp){
    fact[index] = temp%10;
    temp /= 10;
    length++;
}

Думая об этом (и сравнивая его сдругой код, который изменяет index и length вместе), становится очевидным - даже если вы увеличиваете длину массива, вы не увеличиваете индекс.Это означает, что для окончательного переноса десяти или более последующий перенос не будет заполнять правильный индекс, он будет просто перезаписывать один и тот же индекс каждый раз.

Это можно увидеть здесь:

temp: 8 1 2 8 1 6 0 // no good: 73440 * 14 = 10128160 !!!
      1 0 2 8 1 6 0 // is what it should be

, где он поместит ноль (10% 10) в это второе место (увеличив длину), но затем поместит единицу (10/10) в тот же индекс , оставив 8при любом значении, которое было раньше.

Итак, если мы также увеличим index, что мы увидим (возвращаясь к менее подробному коду)?

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! = 1 3 0 7 6 7 4 3 6 8 0 0 0
16! = 2 0 9 2 2 7 8 9 8 8 8 0 0 0
17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0
18! = 6 4 0 2 3 7 3 7 0 5 7 2 8 0 0 0
19! = 1 2 1 6 4 5 1 0 0 4 0 8 8 3 2 0 0 0
20! = 2 4 3 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0

Это решает вашуконкретная проблема и, надеюсь, даст некоторое образование по отладке: -)