c++ - 文字列C++で数値を掛ける

Question

私が探しているのは、文字列内の数値に単純な数学を使用することです

100 の階乗を見つけようとしていますが、int または long long に入れるのは非常に大きいので、検索したところ、string が最適なソリューションであることがわかりましたが、

文字列で数値を乗算したり、int を乗算してから文字列に戻したりすることはできません。また、C++ の std 以外のライブラリを使用することはできません。

Answer 1

これを解決するには、数値を別の数値で乗算するコードを作成する必要があります。以下は、文字列の内容を 2 で乗算する関数です。

void times_two(char *str)
{
    int carry = 0;
    for(int i = DIGITS-2; i >= 0; i--)
    {
    int t = str[i] - '0';
    t *= 2;
    t += carry;
    str[i] = (t % 10) + '0';
    carry = (t > 9);
    }
}

文字列は DIGITS 文字の長さで、文字列の右側にゼロを「調整」して埋めるものと想定しています。

もちろん、「1桁以上」で掛けようとすると、掛ける数の長さをループする必要があり、「キャリー」が何を超えても1以上になることにも注意する必要があります2。しかし、原則は同じです。

[上記の 2 つのシナリオに対処するために、上記の関数を意図的に書き直していません。100 の階乗を行う目的は、答えを見つけることではなく、プログラミングの問題を解決する方法を学ぶことだからです。答えを見つけたいだけなら、最新の電卓を使えばいいのです!]

Answer 2

これは、私がかつて書いたコードがO(n^2)時間内に実行されることです。O（nlog n）時間で実行される高速フーリエ変換（fft）のようなより良いアルゴリズムがあります。乗算関数は 2 つの文字列 (数値) を受け入れ、その積を返します。

#define itc(n) char(n+48)
#define cti(ch) (ch-48)
 string itos(lld n)
    {
        ostringstream convert;
        convert<<n;
        return convert.str();
    }   



string add(string s1, string s2)
{
    int len1=s1.length(), len2=s2.length();
    if(len1<len2)                                   //s1 should be of greater length than s2
        return add(s2, s1);
    string ans="";
    int carry=0, i, s;
    for(i=1;i<=len1;i++)
    {
        s = carry+cti(s1[len1-i]);

        if(i<=len2)
            s += cti(s2[len2-i]);

        ans = itc(s%10)+ans;                        //finding the character to be added to the ans
        carry = s/10;                               //finding the carry
    }
    if(carry!=0)
        ans = itc(carry)+ans;

    return ans;
}

     string multiply(string s1, string s2)
        {
            int len1=s1.length(), len2=s2.length();
            if(len1<len2)
                return multiply(s2,s1);
            int i,j,p, carry=0;
            string result, net="", c;
            for(i=len2-1;i>=0;i--)
            {
                carry=0;
                result="";
                c="";
                for(j=len1-1;j>=0;j--)
                {
                    p=cti(s1[j])*cti(s2[i]);
                    result = itc((p+carry)%10)+result;
                    carry=(p+carry)/10;
                }
                if(carry!=0)
                {
                    c=itos(carry);
                    result=c+result;

                }
                for(j=i;j<len2-1;j++)
                    result+="0";

                net=add(net,result);
            }
            return net;
        }