c++.jpg

前言

讲道理刚开始接触算法碰到的第一个“著名”的难题,就是大数相加问题,该问题的描述简要如下:

给你两个数,这两个数远远大于int类型所能存储的范围,现在要求你算出这两个数的和

这题目的要求很简单,就是算加法,但是问题在于:

1. 如何保存超过int类型范围的整数
2. 如何计算这两个通过特殊手段保存的整数

接下来我们依次解决这两个问题。

如何保存数值

对于这类数值溢出的问题,我个人理解上首推字符串(不排除有其他更高级的存储方法),字符串能够保存的字符位数远远超出计算机所能表示的最大整数类型,甚至是浮点数。

用一个字符串保存超长整数是非常合适的。

如何计算两个字符串整数

这是该问题的核心,我直接讲一下我的思路然后可以参考我的代码(代码写的不够好看,经验不足,见谅)

假设有字符串整数AB以及结果字符串C,现步骤如下:

  1. 定义一个整数,其含义为进位。默认为0
  2. AB依次从字符串尾部开始,尾部字符转成数字相加,同时还要加上进位整数,相加结果对10整除,C保存该整除的结果,同时判断结果是否大于等于10,是则让进位整数为1,否则无动作。
  3. 持续步骤2,直至其中一个字符串到字符串开头
  4. 将最后未到开头的字符串,从步骤2结束的位置依次先与进位整数相加并整除10,然后字符串C保存结果,同样,判断相加和是否大于等于10,满足条件则置1
  5. 所有的字符串都到了开头,则最后判断进位整数是否为1,如果是则额外给字符串C添加一个字符1
  6. 最后将字符串C反向输出,则是两字符串整数相加结果

以下是C/C++实现的代码:

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    namespace dashu {
    
        int charToNum(char c) {
            switch (c) {
            case '0':
                return 0;
            case '1':
                return 1;
            case '2':
                return 2;
            case '3':
                return 3;
            case '4':
                return 4;
            case '5':
                return 5;
            case '6':
                return 6;
            case '7':
                return 7;
            case '8':
                return 8;
            case '9':
                return 9;
            default:
                break;
            }
            return 0;
        }
    
        char numToChar(int n) {
            switch (n) {
            case 0:
                return '0';
            case 1:
                return '1';
            case 2:
                return '2';
            case 3:
                return '3';
            case 4:
                return '4';
            case 5:
                return '5';
            case 6:
                return '6';
            case 7:
                return '7';
            case 8:
                return '8';
            case 9:
                return '9';
            default:
                break;
            }
            return '0';
        }
    
        string bigNumCalc(string num1, string num2) {
            vector<char> str;
            string result;
            int addnum = 0;
            auto it1 = num1.rbegin(), it2 = num2.rbegin();
            while (it1 != num1.rend() && it2 != num2.rend()) {
                //两字符串逆序相加直至其中一个到达其字符串开头
                int add = charToNum(*it1) + charToNum(*it2) + addnum;
                str.push_back(numToChar(add % 10));
                if (add >= 10) {
                    addnum = 1;
                }
                else {
                    addnum = 0;
                }
                ++it1;
                ++it2;
            }
            //如果字符串1 / 2没有到开头,则把剩余字符添加到输出字符串中,如有进位则处理进位
            while (it1 != num1.rend()) {
                int add = charToNum(*it1) + addnum;
                str.push_back(numToChar(add % 10));
                if (add >= 10) {
                    addnum = 1;
                }
                else {
                    addnum = 0;
                }
                ++it1;
            }
            while (it2 != num2.rend()) {
                int add = charToNum(*it2) + addnum;
                str.push_back(numToChar(add % 10));
                if (add >= 10) {
                    addnum = 1;
                }
                else {
                    addnum = 0;
                }
                ++it2;
            }
            //如果到了最后仍存在进位,则额外添加一位字符“1”
            if (addnum) {
                str.push_back(numToChar(addnum));
            }
            //将结果字符串逆向整理,得到计算结果
            for (auto it = str.rbegin(); it != str.rend(); ++it) {
                result += *it;
            }
            return result;
        }
    
        void start() {
            int t;
            cin >> t;
            for (int i = 1; i <= t; i++) {
                string num1, num2, result;
                cin >> num1 >> num2;
                result = bigNumCalc(num1, num2);
                cout << "Case " << i << ":" << endl;
                cout << num1 << " + " << num2 << " = " << result << endl;
                if (i != t) {
                    cout << endl;
                }
            }
        }
    }
Last modification:September 5th, 2018 at 07:19 am
If you think my article is useful to you, please feel free to appreciate