中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-3-21
- 最后登录
- 1970-1-1
|
尴尬了,才发现自己没有注册课程!压根提交不了代码!
完成了WEEK 1的Karatsuba Multiplication
实现的大概思路无非就是用string去存储大数,然后按部就班就好
但是这里有个实现的细节值得注意,由于我们这里mult的实现是对数字进行不断二分,所以我们需要把长度补齐为n的二次幂,这个并不会影响算法的复杂度(顶多常数变大而已)
- #include<cstdio>
- #include<iostream>
- #include<string>
- #include<cstring>
- using namespace std;
- string add(string a, string b)
- {
- int n = max(a.length(), b.length());
- while (n > a.length())
- {
- a = "0" + a;
- }
- while (n > b.length())
- {
- b = "0" + b;
- }
- int tmp[100];
- string ret;
- memset(tmp, 0, sizeof(tmp));
- int next = 0;
- for (int i=0; i<n; i++)
- {
- int cur = a[n-i-1] + b[n-i-1] - '0' - '0' + next;
- next = 0;
- if (cur >= 10)
- {
- cur -= 10;
- next = 1;
- }
- ret = char(cur + '0') + ret;
- }
- if (next != 0)
- {
- ret = "1" + ret;
- }
- while (ret[0] == '0') ret = ret.substr(1, ret.length()-1);
- return ret;
- }
- string subt(string a, string b)
- {
- int n = max(a.length(), b.length());
- while (n > a.length())
- {
- a = "0" + a;
- }
- while (n > b.length())
- {
- b = "0" + b;
- }
- int tmp[100];
- string ret;
- memset(tmp, 0, sizeof(tmp));
- int next = 0;
- for (int i=0; i<n; i++)
- {
- int cur = a[n-i-1] - b[n-i-1] + next;
- next = 0;
- if (cur < 0)
- {
- cur += 10;
- next = -1;
- }
- ret = char(cur + '0') + ret;
- }
- while (ret[0] == '0') ret = ret.substr(1, ret.length()-1);
- return ret;
- }
- string add_zero(string arr, int n)
- {
- for (int i=0; i<n; i++)
- {
- arr = arr + "0";
- }
- return arr;
- }
- string calc(string x, string y)
- {
- // cout << "-----------------------------------\n";
- int n = max(x.length(), y.length());
- int cnt = 1;
- while (cnt < n)
- {
- cnt <<= 1;
- }
- n = cnt;
- while (n > x.length())
- {
- x = "0" + x;
- }
- while (n > y.length())
- {
- y = "0" + y;
- }
- if (x.length() == 1 and y.length() == 1)
- {
- string ret = "";
- int num = (x[0] - '0') * (y[0] - '0');
- if (num/10 != 0)
- {
- ret += char(num / 10 + '0');
- }
- num %= 10;
- ret += char(num + '0');
- return ret;
- }
- if (n == 0)
- {
- return "0";
- }
- // cout << "n:" << n << "\n";
- string a = x.substr(0, n / 2);
- string b = x.substr(n / 2, n / 2);
- string c = y.substr(0, n / 2);
- string d = y.substr(n / 2, n / 2);
- // cout << "x:" << x << "\ty:" << y << "\n";
- // cout << "a:" << a << "\tb:" << b << "\tc:" << c << "\td:" <<d << "\n";
- string ac = calc(a, c);
- string bd = calc(b, d);
- string sum = calc(add(a, b), add(c, d));
- string mid_term = subt(subt(sum, ac), bd);
- ac = add_zero(ac, n);
- mid_term = add_zero(mid_term, n/2);
- // cout << "ac:" << ac << "\tbd:" << bd << "\tmid_term:" << mid_term << "\tsum:" << sum << "\n";
- return add(add(ac, mid_term), bd);
- }
- int main()
- {
- freopen("in.txt", "r", stdin);
- ios::sync_with_stdio(false);
- string a, b;
- cin >> a >> b;
- cout << calc(a, b) << "\n";
- return 0;
- }
复制代码 |
|