3

両方とも大きな整数である 2 つの文字列 (このデモでは 10 桁の数字のみを使用) を取り、それらを合計して、合計を正確に表す最終的な文字列を生成する、より大きなプロジェクト用のアルゴリズムを作成しようとしています。 2本のオリジナル弦。最初からこれを実行するためのより良い方法がある可能性があることは認識していますが、長い整数ではなく、大きな整数の文字列を具体的に使用することになっています。

私が考えたのは、元の 2 つの弦を逆にして、1 の位置、10 の位置などをすべて適切に並べて追加することでした。次に、一度に1つの位置で、文字列の文字を単一の整数に変換し、それらを合計してから、その合計を1の位置として使用するか、最終的な文字列に使用します。これは、完了すると文字の正しい順序に戻されます.

問題が発生しているのは、文字列内の対応する位置からの 2 つの整数の合計が 9 を超えるイベントの準備であり、残りを次の位置に繰り越すことになると思います。たとえば、1 の位置に 7 と 5 を追加すると 12 になるので、2 を保持し、10 の位置操作のためにループバックしたら 10 の位置に 1 を追加します。

正確な結果が得られず、アルゴリズムを修正しようとして多くの時間を費やした後、これを修正するために何をする必要があるかわかりません。

私の意図したプロセスが明確であり、誰かが私を正しい方向に向けたり、プログラムにあるかもしれない間違いを修正したりできることを願っています.

前もって感謝します。

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()
{
    string str1 = "1234567890", str2 = "2345678901"; //Two original strings of large integers
    string rev_str1, rev_str2;
    int int1 = 0, int2 = 0;
    string final; //Final product string, sum of two original strings
    int temp_int = 0, buffer_int, remainder = 0;
    string temp_str = "", buffer_str;
    char buffer[100] = {0};

    cout << "str1 = " << str1 << endl;
    cout << endl;
    cout << "str2 = " << str2 << endl;
    cout << endl;

    rev_str1 = string(str1.rbegin(), str1.rend());
    rev_str2 = string(str2.rbegin(), str2.rend());

    for (int i = 0; i < 10; i++)
    {
        buffer_str = rev_str1.at(i);
        int1 = atoi(buffer_str.c_str());
        buffer_str = rev_str2.at(i);
        int2 = atoi(buffer_str.c_str());
        buffer_int += (int1 + int2 + remainder);
        remainder = 0;

        while (buffer_int > 9)
        {
            buffer_int -= 10;
            remainder += 10;
        }

        temp_str = itoa(buffer_int, buffer, 10);
        final += temp_str;
    }

    final = string(final.rbegin(), final.rend());

    cout << "final = " << final << endl;
    cout << endl;
}
4

3 に答える 3

6

これが私が思いついたものです。これは 2 つの加数のためだけです。それ以上ある場合は、特にキャリーを少し調整する必要があります。キャリーは 19 よりも大きくなる可能性があり、結果の文字列が割り当てられる方法は次のとおりです。

#include <iostream>
#include <string>

using namespace std;

int main()
{
    // Two original strings of large integers
    string str1 = "1234567890",
           str2 = "2345678901234";

    // Zero-padd str1 and str2 to the same length
    size_t n = max(str1.size(), str2.size());
    if (n > str1.size())
        str1 = string(n-str1.size(), '0') + str1;
    if (n > str2.size())
        str2 = string(n-str2.size(), '0') + str2;

    // Final product string, sum of two original strings.
    // The sum of two integers has at most one digit more, for more inputs make
    // below reverse_iterator a back_insert_iterator, then reverse the result
    // and skip the removal of the padding.
    string final(n+1, '0');

    // The carry
    char carry = 0;

    // Iterators
    string::const_reverse_iterator s1 = str1.rbegin(), e = str1.rend(),
                                   s2 = str2.rbegin();
    string::reverse_iterator f = final.rbegin();

    // Conversion
    for (; s1 != e; ++s1, ++s2, ++f)
    {
        // Bracketing to avoid overflow
        char tmp = (*s1-'0')+(*s2-'0') + carry;
        if (tmp > 9)
        {
            carry = 1;
            tmp -= 10;
        }
        else
        {
            carry = 0;
        }
        *f = tmp + '0';
    }
    final[0] = carry + '0';

    // Remove leading zeros from result
    n = final.find_first_not_of("0");
    if (n != string::npos)
    {
        final = final.substr(n);
    }

    cout << "str1 = " << str1 << endl
         << "str2 = " << str2 << endl
         << "final = " << final << endl;
}
于 2013-01-29T08:44:39.987 に答える
4

問題は、1 ではなく 10 を持っていることです。を追加する19 + 5と、単位の位置に 4 が追加され、10 の位置に 1 が追加されます。10 の位置に 10 を追加することはありません。

この行を に変更するだけremainder += 10;ですremainder += 1;。

また、while2 つ以上の加数がある場合、そのループは必要ありません。そのままでは、一度に 2 桁だけを追加する場合、最大の加数は9 + 9であり、1 しかありません。

于 2013-01-29T07:18:02.990 に答える