1

这是一个计算数字阶乘的程序，我将它存储在一个向量中。该程序适用于高达 30 的输入，但对于 n=40 或更大，它会产生奇怪的输出。例如。

输入：

3

4

30

40

输出：

24

265252859812191058636308480000000

-190350521-236-6-6-5-745611269596115894272000000000

这个 - 符号来自哪里？

#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> solve(int n){
        if(n==1){
                vector<int> ans;
                ans.push_back(1);
                return ans; 
        }
        vector<int> b=solve(n-1);
        int temp=0,x=0;
        for(int i=0;i<b.size();i++){
                x=b[i]*n+temp;
                b[i]=x%10;
                temp=x/10;
        }
        if(temp!=0)
            b.push_back(temp);
        return b;
}   
    int main(){
            int t,n,i;
            scanf("%d",&t);
            while(t--){
                    scanf("%d",&n);
                    vector<int> ans=solve(n);
                    for(int j=ans.size()-1;j>=0;j--)
                             printf("%d",ans[j]);
                    printf("\n");
            }
    }
4

1 回答 1

1

这是整数溢出。一个固定大小的整数只能容纳这么大的值，然后它就会溢出。您可能想要使用像 GMP 这样的任意精度整数库。

使用这些更改运行您的代码，它会变得很明显：

vector<int> solve(int n)
{
    if(n==1){
            vector<int> ans; 
            ans.push_back(1);
            return ans;
    }
    vector<int> b=solve(n-1);
    int temp=0,x=0;
    cout << "b.size=" << b.size() << ", n=" << n << endl;
    for(int i=0;i<b.size();i++){
            x=b[i]*n+temp;
            cout << "b[ " << i << "]=" << b[i] << ", temp= " << temp << ", x=" << x << endl;
            b[i]=x%10;
            temp=x/10;
    }
    if(temp!=0)
    {
        cout << "push_back(" << temp << ")" << endl;
        b.push_back(temp);
    }
    return b;
}
于 2012-09-01T05:42:40.437 回答