向量vector

洛谷原题 https://www.luogu.com.cn/problem/P1009
洛谷这道题目要求用高精度写阶乘，但是我还没有学过。从网上扒各种资料和网课，发现在学习高精度之前，需要知道vector这个容器。

什么是vector

vector是一个封装了动态大小数组的顺序容器，属于C++STL。可以简单认为。vector是一个能够存放任意类型的动态数组。

使用vector

使用vector需要在文件开头加上
#include< vector >
using namespace std;

原文链接：https://blog.csdn.net/qq_38654981/article/details/81907134
https://blog.csdn.net/w_linux/article/details/71600574
vector的初始化：

1. vector<类型>标识符 //vector a
2. vector<类型>标识符(最大容量) //vectora(10)
3. vector<类型>标识符(最大容量,初始所有值) //vectora(10,1)
4. int b[7]={1,2,3,4,5,9,8}; vector a(b,b+7); //从数组中获得初值
5. vector< vector< int> >v; 二维向量 //这里最外的<>要有空格。否则在比较旧的编译器下无法通过
6. vector a(b); //用b向量来创建a向量，整体复制性赋值

vector函数合集
https://blog.csdn.net/w_linux/article/details/71600574

高精度计算

学完vector后开始学习高精度计算

高精度计算实际上就是将大数据存储到字符串中，手动进行运算和重新储存。其原理大致相同，算法不同。

高精度加法

#include <iostream>
//<vector>自带一个size函数求长度 
#include <vector> 
using namespace std;
//数组长度+10防止边界问题 
const int N=1e6+10;
//写一个方法返回vector类型 
//这里取地址符是因为引用类型更快 
//C=A+B
vector<int> add(vector<int> &A,vector<int> &B){vector<int> C;int t =0;//这是进位，同时用来存放数据 for (int i=0;i<A.size()||i<B.size();i++){if(i<A.size()) t+=A[i];if(i<B.size()) t+=B[i];//当前位只能储存数据t的个位数 C.push_back(t%10);//让t整除10 t/=10;}//如果此时t仍然有数，则进1 if(t) C.push_back(1);return C;
}
int main(){//数字太长，用字符串读取 string a,b;vector<int>A,B;cin>>a>>b; //a="123456"for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');//倒序存储//字符变整数减去'0' for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');auto C = add(A,B);//逆序输出 for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0; 
}

高精度减法

高精度减法与加法在main函数中主要是输入和输出，没有什么差别，所以为了方便，只放入函数模板片段。

vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){   //t用来存放数据t = A[i] - t; //可能前面有借位if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);//t+10 因为t-B[i]后有可能是负数//如果t<0则记录，向高位借1: 回到 t=A[i]-t t=1时，高位数字减少1if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();//判断最高位是否为0return C;
}

高精度乘低精度

高精度乘法和平时做的乘法式子有区别，平时我们做乘法是，比如123*12，是123*2+123*10。
而高精度乘法的，比如123*12
3*12=36，进位3，最后一位为6。
2*12+3=27，进位2倒数第二位为7。
1*12+2=14，进位1，倒数第三位是4。
0*12+1=1，第一位是1。
组合起来为1476。

代码实现如下：

#include <iostream>
//<vector>自带一个size函数求长度
#include <vector>
using namespace std;
//数组长度+10防止边界问题
const int N=1e6+10;
//写一个方法返回vector类型
//这里取地址符是因为引用类型更快
vector<int> mul(vector<int> &A,int b)
{vector<int> C;if (b==0){ //因为是字符串类型，不加if判断会导致在*0时输出00000C.push_back(0);return C;}int t =0;for (int i =0;i<A.size();i++){t+=A[i]*b;  //t=t+A[i]*b 第一个t=表示数据,t+的t表示前面运算的进位C.push_back(t%10);  //t的个位数t=t/10;    //t的进位}if (t) C.push_back(t);  //加上进位数return C;
}
int main(){//a数字太长，用字符串读取，b可直接读入string a;int b;//将a存入vectorvector<int> A;cin>>a>>b;//从低位开始存入for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');auto C = mul(A,b);//从vector末尾开始输出for(int i =C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;
}

mul函数部分可以简化如下：

vector<int> mul(vector<int> &A,int b)
{vector<int> C;if (b==0){ //同样，0数据需要特判C.push_back(0);return C;}int t =0;for (int i =0;i<A.size()||t;i++){  //加了一个"||t"条件判断，要么i没有循环完，要么t不为0if (i<A.size()) t+=A[i]*b;  //因为上面加了条件，所以下面多个判断i是否在A的范围内C.push_back(t%10);  //t的个位数t=t/10;    //t的进位}return C;
}

高精度除低精度

思路整理：
138/12
从最高位开始1/12=0…1，1掉到下一位
上式余数*10+第二位：(1*10+3)/12=1…1，1到下一位
同理得：(1*10+8)/12=1…6
得到答案011，去掉最高位0，答案为11…6

除法除了返回商，还会返回余数：
代码实现如下：

#include <iostream>
//<vector>自带一个size函数求长度
#include <vector>
#include <algorithm>  //这个头文件包含函数reverse
using namespace std;
//数组长度+10防止边界问题
const int N=1e6+10;
//写一个方法返回vector类型
//这里取地址符是因为引用类型更快
vector<int> div(vector<int> &A,int b,int &r)//r是余数,用了取地址符，直接改变r的值
{vector<int> C;r=0;for(int i=A.size()-1;i>=0;i--){   //除法需要从高位数开始除，所以for是正着循环r=r*10+A[i];C.push_back(r/b);r=(r%b);}reverse(C.begin(),C.end());  //因为C最后得到的结果是正序的，而C输出是倒序，所以要反过来while (C.size()>1&& C.back()==0) C.pop_back(); //去除前导0  这句话需要放在reverse后面！return C;
}
int main(){//a数字太长，用字符串读取，b可直接读入string a;int b,r;//将a存入vectorvector<int> A;cin>>a>>b;//从低位开始存入for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');auto C = div(A,b,r);//从vector末尾开始输出for(int i =C.size()-1;i>=0;i--) printf("%d",C[i]);cout<<endl<<r<<endl;return 0;
}

其实高精度计算的输入输出部分都差不了太多，主要在于函数模板那一块

特别注意，高精度除法需要在函数中设置余数。