题目描述

给定两数，求和。

范围

反正unsigned long long装不下。

样例

输入#1

23
37

输出#1

70

提示

请勿使用Python！

算法

(小学竖式) $O(n)$

1.存数

使用std::vector<int>即可。$注$

设有n位数字

v[n-1] v[n-2] . . . v[0]

1 , 5 , . . . , 9

表示 15…9

例子：

vector<int> num(5,0);
num[4]=5,num[3]=3,num[2]=4,num[1]=7,num[0]=9;

表示53479

输入输出时注意反序：

vector<int> read(void){
    string str;
    cin>>str;                                                   //读入
    vector<int> vec(str.size());                                //存数
    for(int i=str.size()-1;i>=0;i--) vec[i]=str[i]-'0';
    reverse(vec.begin(),vec.end());                             //反序
    /*
     *  上面两行也可以用以下代码代替：
     *  
     *  for(int i=0,j=str.size()-1;j>=0;j--,i++)
     *      vec[i]=str[j]-'0';
     */
    return vec;
}

快读：

一点也不快

inline vector<int> read(void){
    vector<int> vec;
    int ch=getchar();
    while(!isdigit(ch)) {ch=getchar(); }
    while(isdigit(ch)) {vec.push_back(ch-'0'); ch=getchar();}   //慢慢读入
    ungetc(ch,stdin);                                           //不懂跳过
    reverse(vec.begin(),vec.end());                             //反序
    return vec;
}

输出：

不难，读者自行尝试。

2.相加

拿出课本

从末位开始加，进位到下一位。

vector<int> add(vector<int>& a,vector<int>& b){
    int sa=a.size(),sb=b.size(),sc=max(sa,sb);
    //sa 表示 a 的大小，sb 表示 b 的大小，sc 表示 要计算的位数。
    vector<int> c(sc+1,0);              //结果，为防像首位进位，多开一位。
    for(int i = 0; i < sc; i++){        //从末位开始加，进位到下一位。
        if(i < sa) c[i]+=a[i];          //注意是 +=，不是 =，因为上一位可能进位。
        if(i < sb) c[i]+=b[i];          //同理。
        if(c[i]>9) c[i+1]++,c[i]-=10;   //处理进位。 
    }
    if(c.size()>1 && c.back()==0) c.pop_back();
    // ↑ 如果首位是0 注意结果为0 时的情况。
    return c; 
}

参考文献

部编小学数学2年级教材

C++ 代码

    //略，上面已经很详细了。 

注

vector

std::vector<type>
    vector<type>(Size,Elem) 构造一个vector储存type,大小Size，元素Elem
    下标访问 [index]        访问第index 个元素，或修改。 
    size()                  大小
    empty()                 是否空
    resize(Size,Elem)       重置大小：（m 可省略。） 
        如果 Size > size() 则 扩容 并 将多出来的空间设为Elem； 
        如果 Size < size() 则 缩容 并 丢弃装不下的元素。 
    push_back(Elem)         向队尾添加元素Elem。
    pop_back()              将队尾元素弹出。
    back()                  访问队尾，或修改。
    front()                 访问队首，或修改。
    clear()                 清空数组。 

    iterator                迭代器，类似于指针。
    begin()                 返回队首迭代器。
    end()                   返回队尾的下一个迭代器。

    insert(Pos,Elem)        在Pos 前插入Elem。 
    erase(Pos)              删除Pos 对应的元素。

    ***
    更详细的功能表参考编译手册！
    ***