【毎週1題】2017.3.2 HDU 1002問題解決報告

タイトルの説明

は2つの数AとBを与え、A+Bの値を求めて出力する.(AとBは大きいかもしれませんが、intでは入れません.)

はコードをここに提出することができます.http://acm.hdu.edu.cn/showproblem.php?pid=1002

解題分析

この問題は大数演算を考察し、2つの数字の加算を実現する過程を要求し、各数字を読み取り、低位から高位への進位を実現し、最後に印刷出力を含む.その考え方もとても簡単です.最も一般的な解題構想を与える:まず文字列を用いてAとBを読み込み、AとBの各ビットを分解して低位から高位までの順序でint配列に格納し、その後forサイクルで各ビットを加算して進位し、最後に逆順序で出力すればよい.

注意すべき点:

題では、2つの数字は1000ビットを超えないが、加算後に1000ビットを超える可能性があるため、結果として配列の長さは1001を超える.

には複数の入力データがあるので、計算が終わるたびに配列を空にします.

は、AとBの桁数が異なる場合を考慮する必要がある.

最高位も可能であることを忘れないでください.

フォーマットは、サンプルデータの出力フォーマットと同じである必要があることに注意してください.

今回のテーマは比較的簡単で、主にOJの使い方を熟知するために、後続のテーマは次第に難しくなります.アルゴリズムの書籍を購入することができます(「アルゴリズム(第4版)」(ISBN:9787115293800)と「アルゴリズム導論」)をお勧めします.また、問題を解く過程で、時間と空間の複雑さについてよく知っている概念が必要です.

思考問題
1.この問題の時間的複雑さと空間的複雑さはどのくらいですか.
2.どのようにして大数の減算、乗算、除算を実現しますか?主なコードセグメントを頭の中で大まかに形成してください.
ルーチン(C+)
(注:ルーチンは問題を解く方法を与えるだけで、標準プログラムではなく、最も完璧な解法とは限らない)

#include 
#include 
using namespace std;


void clearArray(short _array[], int _count)
{
    for (int i = 0; i < _count; i++)
    {
        _array[i] = 0;
    }
}

int main()
{
    int totalCase;
    string a, b;
    short numA[1000], numB[1000], numC[1001];

    cin >> totalCase;
    int countCase = totalCase;

    while (countCase--)
    {
        cin >> a >> b;
        
        //     ，   case      
        if (countCase < totalCase - 1) 
            cout << endl;

        cout << "Case " << totalCase - countCase << ":" << endl;
        cout << a << " + " << b << " = ";
        
        //    。        ？
        clearArray(numA, 1000);
        clearArray(numB, 1000);

        for (int i = 0; i < a.length(); i++)
            numA[i] = (short) (a[a.length() - i - 1] - 48);

        for (int i = 0; i < b.length(); i++)
            numB[i] = (short) (b[b.length() - i - 1] - 48);

        int finalSize = a.length() > b.length() ? a.length() : b.length();
        int carry = 0;
        for (int i = 0; i < finalSize; i++)
        {
            if (numA[i] + numB[i] + carry > 9)
            {
                numC[i] = numA[i] + numB[i] + carry - 10;
                carry = 1;
            }
            else
            {
                numC[i] = numA[i] + numB[i] + carry;
                carry = 0;
            }
        }

        //          
        if (carry != 0)
        {
            numC[finalSize] = carry;
            finalSize++;
        }

        //output     
        for (int i = finalSize - 1; i >= 0; i--)
        {
            cout << numC[i];
        }
        cout << endl;
    }

    return 0;
}