【每周一题】2017.3.2 HDU1002 解题报告

题目描述

• 给出两个数A和B，求出A+B的值并输出。（A和B可能会很大，用int是放不下的。）
• 可以把代码提交至这里：http://acm.hdu.edu.cn/showproblem.php?pid=1002

解题分析

• 这道题考察的是大数运算，要求实现两个数字相加的过程，包括读取每一位数字，实现低位向高位进位，最后打印输出。其思路也非常简单。给出一个最常见的解题思路：首先使用字符串读入A和B，将A和B的每一位分解开并从按照低位到高位的顺序存放在int数组里，然后用for循环来对每一位进行相加和进位，最后倒序输出即可。

• 几个需要注意的地方：

  1. 题中说两个数字不超过1000位，但相加后进位可能超过1000位，因此结果数组的长度要超过1001。
  2. 有多个输入数据，因此每次算完后要清空数组。
  3. 需要考虑到A和B的位数不一样的情况。
  4. 不要忘记最高位也有可能进位。
  5. 注意格式，必须跟示例数据的输出格式一模一样。

• 这次的题目相对简单，主要是为了帮助大家熟悉OJ的用法，后续的题目会逐渐增加难度。大家可以购买算法书籍来自学（推荐《算法（第四版）》（ISBN: 9787115293800）以及《算法导论》）。另外，在解题过程中，需要你对时间和空间复杂度有非常熟悉的概念。

思考题

1. 这道题的时间复杂度和空间复杂度是多少？

2. 如何实现大数的减法、乘法和除法？请在脑海中大致形成主要代码段。

例程（C++）

（注：例程只是给出一种解题方法，不是标准程序，也不一定是最完美的解法）

#include <iostream>
#include <string>
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;
}