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 に答える