===
Index
大整数加法
求两个不超过200位非负整数的和
// s = "123234", t = "32313342";
// ans = 32436576
string sum(string s, string t) {
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
int n = s.size(), m = t.size(), carry = 0, i = 0;
string ans;
while (i < n || i < m || carry) {
int a = i >= n ? 0 : s[i] - '0', b = i >= m ? 0 : t[i] - '0';
int sm = a + b + carry;
carry = sm / 10;
ans += (sm % 10) + '0';
i++;
}
reverse(ans.begin(), ans.end());
return ans;
}
大整数减法
s = “32436576”, t = “32313342”; ans = “123234”,
string sub(string s, string t) {
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
int n = s.size(), m = t.size();
string ans;
for (int i = 0; i < n - 1; ++i) {
if (s[i] < t[i]) {
s[i + 1]--;
s[i] = s[i] + 10;
}
ans += s[i] - t[i] + '0';
}
while(ans.size() && ans.back() == '0') ans.pop_back(); // 删除前导0
reverse(ans.begin(), ans.end());
return ans;
}
大整数乘法
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
class Solution {
public:
string multiply(string s, string t) {
int n = s.size(), m = t.size();
if (!n || !m) return "";
if (s[0] == '0' || t[0] == '0') return "0";
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
vector<int> res(n + m);
int carry = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
res[i + j] += (s[i] - '0') * (t[j] - '0');
for (int i = 0; i < n + m; ++i) {
int tmp = res[i] + carry;
res[i] = tmp % 10;
carry = tmp / 10;
}
if (carry) res[n + m - 1] = carry;
int end = n + m -1;
while(res[end] == 0) end--;
string ans;
for (int i = end; i >=0; i--) {
ans += char(res[i] + '0');
}
return ans;
}
};
大整数除法
问题描述
求两个大的正整数相除的商
输入数据
2 行，第 1 行是被除数，第 2 行是除数。
输出
一行输出是相应的整数商
解题思路
基本思想是反复做减法，如何能减的更快一些呢？以7546除以23为例来看一下：开始商为0，先减去 23 的 100 倍，就是 2300，发现够减 3 次，余下 646。于是商的值就增加 300。然后用 646 减去 230，发现够减 2 次，余下 186，于是商的值增加 20。最后用 186 减去 23，够减 8 次。因此最终商就是 328。 所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。 计算除数的 10 倍、100 倍的时候，不用做乘法，直接在除数后面补 0 即可。
