大数的阶乘给出错误的输出

Question

I am trying to find the factorial of large numbers

I input t number of test cases

and a number in each case whose factorial I am trying to find

I am storing the digits of the factorial in a vector (dynamic array)

and multiplying it each time with decremented n's value

function display: displays all digits in vector 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);
    }
}

output for n = 5

1264221101505

Answer 1

代码中存在多个问题。最主要的是当前向量永远不会被修改：每次找到一个新数字时，它就会被插入。还有一个问题是使用一个变量而不是另一个变量。

此外，代码可以大大简化，因为 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);
    }
}

大数的阶乘给出错误的输出

factorial for large numbers giving wrong output

c++

stl

factorial