分治策略实现大整数乘法

c++对输入的两个超过计算机计算范围的2n位大整数x和y，用递归的方式实现乘积运算，设计并使时间复杂度为o（n1.59）

#include <iostream>
#include <string>
using namespace std;

string karatsuba(string x, string y) {
    int n = x.length();
    if (n == 1) {
        return to_string(stoi(x) * stoi(y));
    }
    string a = x.substr(0, n/2);
    string b = x.substr(n/2);
    string c = y.substr(0, n/2);
    string d = y.substr(n/2);
    string ac = karatsuba(a, c);
    string bd = karatsuba(b, d);
    string abcd = karatsuba(to_string(stoi(a)+stoi(b)), to_string(stoi(c)+stoi(d)));
    string adbc = to_string(stoi(abcd)-stoi(ac)-stoi(bd));
    string zeros(2*n, '0');
    string ans = zeros;
    ans.replace(0, ac.length(), ac);
    ans.replace(n, bd.length(), bd);
    ans.replace(n/2, adbc.length(), adbc);
    return ans;
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << karatsuba(x, y) << endl;
    return 0;
}

• 这篇博客: 冒泡排序C++实现中的 冒泡排序貌似是最简单的排序方法了，因为其破解时间复杂度为O(n^2),在数组比较大的时候，很少用到。其思想是：将 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 但既然简单，也就简单的实现以下，只当是练习了一遍打字 ^_^
  还是直接贴代码：

  //冒泡排序
  void BubbleSort(vector<int> &a)
  {
      int i,j;
      for (i=0;i<a.size();i++)    //每次循环确定一个最大值
      {
          for(j=0;j<a.size()-i-1;j++)     //第i次循环，已经将i+1个元素排列好了
          {
              if (a[j]>a[j+1])             //与相邻元素比较
                  //体会 “冒泡”二字，就是最大的元素逐渐的 “沉”  下去
                  swap_ele(&a[j],&a[j+1]);
          }
      }
  
  }

  以上代码是将大数“沉”下去，若想将小数“浮”上来，只需从尾部开始遍历。