факториал для больших чисел, дающих неправильный вывод

Question

Я пытаюсь найти факториал больших чисел

Я ввожу t количество тестовых случаев

и число в каждом случае, чей факториал я пытаюсь найти

Я сохраняю цифры факториала в векторе (динамический c массив)

и умножаю его каждый раз на уменьшенное значение n

функция display: отображает все цифры в вектор v

#include <iostream>
#include <vector>

using namespace std;

void display(vector<int> v)
{
    for(int x : v)
    {
        cout << x;
    }
    cout << endl;
}


vector <int> factorial(int n)
{
    vector <int>v;
    if(n > 9)
    {
        int n1 = n;
        int r;
        while(n1 != 0)
        {
            r = n1 % 10;
            n /= 10;
            v.insert(v.begin(), r);
        }
    }
    else
    {
        v.push_back(n);
    }
    --n;
    int pdt;
    int carry = 0;
    int digit;

    while(n != 1)
    {
        for(int i = v.size() - 1; i >= 0; --i)
        {
            pdt = v[i] * n + carry;
            carry = pdt / 10;
            digit = pdt % 10;
            v.insert(v.begin() + i, digit);
            // display(v);
        }
        if(carry != 0)
        {
            if(carry > 9)
            {
                int n1 = n;
                int r;
                while(n1 != 0)
                {
                    r = n1 % 10;
                    n /= 10;
                    v.insert(v.begin(), r);
                }

            }
            else
            {
                v.insert(v.begin(), carry);
            }

        }
        carry = 0;
        --n;
    }

    return v;  
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >>n;
        vector <int> v;
        v = factorial(n);
        display(v);
    }
}

вывод для n = 5

1264221101505

Answer 1

В коде было несколько проблем. Основным является то, что текущий вектор никогда не изменяется: каждый раз, когда обнаруживается новый di git, он вставляется. Была также проблема использования одной переменной вместо другой.

Более того, код может быть значительно упрощен с условием, что v[0] соответствует LSB, а не MSB.

Была также возможность упростить код, избегая ненужных тестов, как if (n > 9 ....).

Вот рабочий код:

#include <iostream>
#include <vector>

void display (std::vector<int> &v) {
    for (int i = v.size() -1 ; i >= 0; --i) {
        std::cout << v[i];
    }
    std::cout << "\n";
}

std::vector<int> factorial (int n) {
    std::vector<int> v; 
    v.push_back(1);

    while (n != 1) {
        int carry = 0;
        for (int i = 0; i < v.size(); ++i) {
            int pdt = v[i] * n + carry;
            carry = pdt / 10;
            v[i] = pdt % 10;
        }
        while (carry != 0) {
            int r = carry % 10;
            carry /= 10;
            v.push_back(r);
        }
        --n;
    }
    return v;  
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        auto v = factorial(n);
        display(v);
    }
}