title:算法归纳date: 2021-2-22 8：15
tags: C++
categories: 便签

大数乘法

  1. #include <iostream>
  2. #include <string> 
  3. #include <vector> 
  4. #include <algorithm>
  5. using namespace std;
  6. #define Up(i,a,b) for(int i = a;i < b;i++)
  8. int main() {
  9.     string a,b;
  10.     int t = 0;
  11.     cin>>a>>b;
  12.     reverse(a.begin(),a.end());
  13.     reverse(b.begin(),b.end());
  14.     vector<int> v(a.length() + b.length(),0);
  16.     Up(i, 0, a.length()){
  17.         Up(j, 0, b.length()){
  18.             t = (a[i] - '0') * (b[j] - '0') + v[i + j];
  19.             v[i + j] = t % 10;
  20.             v[i + j + 1] += t / 10;
  21.             //for(int k = v.size() - 1;k >= 0;k--) cout<<v[k]<<' ';
  22.             //cout<<endl;
  23.         }
  24.     }
  25.     int i;
  26.     for(i = v.size() - 1;v[i] == 0;i--);
  27.     for(int j = i;j >= 0;j--){
  28.         cout<<v[j];
  29.     }
  30.     return 0;
  31. }

v[i + j + 1] += t / 10;

最大公约数和最小公倍数

  1. #include <iostream>
  2. using namespace std;
  3. typedef long long LL;
  5. LL gcd(LL a, LL b){
  6.     if(b == 0) return a;
  7.     else return gcd(b, a%b);
  8. }
  10. int main() {
  11.     LL a,b;
  12.     cin>>a>>b;
  13.     //求最大公约数
  14.     cout<<gcd(a, b)<<endl;
  15.     //求最小公倍数
  16.     cout<<a*b/gcd(a, b); 
  17.     return 0;
  18. }

最大公约数用辗转相除法 两数相乘再除以最大公约数得最小公倍数

二分查找

  1. /*二分查找*/
  2. int qSearch(int a[], int len, int x) {  //返回的是坐标
  3.     int left = 0;
  4.     int right = len  - 1;
  5.     int ans = -1;
  7.     while (left <= right) {
  8.         int mid = (left + right) / 2;
  9.         if (a[mid] == x) { ans = mid; break; }
  10.         else if (a[mid] > x) right = mid - 1;
  11.         else left = mid + 1;
  12.     }
  13.     return ans;
  14. }

递归排序（mergeSort）

  1. void msort(int l, int r) {
  2.     if (l == r) return;  //第一部分，递归
  3.     int mid = (l + r) / 2;
  4.     msort(l, mid);
  5.     msort(mid + 1, r);
  7.     int i = l;  //第二部分，归并
  8.     int j = mid + 1;
  9.     int k = l;
  10.     while (i <= mid && j <= r) {
  11.         if (v1[i] <= v1[j]) v2[k++] = v1[i++];
  12.         else {
  13.             v2[k++] = v1[j++];
  14.         }
  15.     }
  16.     while (i <= mid) v2[k++] = v1[i++];
  17.     while (j <= r) v2[k++] = v1[j++];
  18.     for (int i = l; i <= r; i++) v1[i] = v2[i];
  19. }

快速排序

  1. void QSort(int L[], int left, int right)  //快速排序
  2. {
  3.     if (left >= right)    return;    //条出循环
  4.     int temp = L[left];    //采用最左边的数作为支点
  5.     int    i = left, j = right;
  6.     while (i < j)
  7.     {
  8.   while (i < j && L[j] >= temp)  j--;
  9.   L[i] = L[j];    //将比支点小的数移到低端
  10.   while (i < j && L[i] <= temp)    i++;
  11.   L[j] = L[i];    //将比支点大的数移到高端
  12.     }
  13.     L[i] = temp;    //支点移到i位置上**易错点**
  14.     QSort(L, left, i - 1);    //递归处理左边的数
  15.     QSort(L, i + 1, right);    //递归处理右边的数
  16. }