算法-----高精度2（高精度乘法，高精度除法，高精度斐波那锲数列）

高精度乘法

对于高精度乘法来说似乎不像高精度加减法那样简单了，我们似乎得一个一个加了，因为我们都知道
a×b=a+a+a+a+a…+a(b个a)。如果真要这要的话那1e9*1e9不得超时啊，所以不能这样，我们还是得从乘法竖式入手

这样看似乎看不出来什么，那我们可以对其改变下模式可以进行撤位看看

这样就撤位成功了，但肯定不是 最后结果，每一位都要化成一位数。但是我们可以先等等，观察一下规律。不难发现当逆序存储后，我们做乘法竖式模拟时，c[i+j]+=a[i]*b[j](下标从零开始）。

最后我们只需进下位就行了。
所以我们的思路来了：
1.枚举a枚举b,相乘再加到c里
2.加完之后再进位
3,别忘去掉前导零

好的开始代码环节
初始化（不多说）

string s1,s2;
const int N=2050;
int a[N],b[N],c[N],len1,len2,len3;

读入

void Read(){cin>>s1>>s2;len1=s1.size(),len2=s2.size();len3=len1+len2;              //c数组的长度，因为公式是c[i+j]+=a[i]*b[j],所以i+j的最大值就是c的长度for(int i=0;i<len1;i++) a[i]=(s1[len1-i-1]-'0');for(int j=0;j<len2;j++) b[j]=(s2[len2-j-1]-'0');
}

模拟竖式

void count(){for(int i=0;i<len1;i++){//枚举afor(int j=0;j<len2;j++){//枚举bc[i+j]+=a[i]*b[j];//公式}} for(int i=0;i<len3;i++){//进位if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}}while(len3>0&&c[len3-1]==0) len3--;  //去前导零
}

输出

void print(){for(int i=len3-1;i>=0;i--) cout<<c[i];
}

总代码

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
const int N=2050;
int a[N],b[N],c[N],len1,len2,len3;
void Read(){cin>>s1>>s2;len1=s1.size(),len2=s2.size();len3=len1+len2;for(int i=0;i<len1;i++) a[i]=(s1[len1-i-1]-'0');for(int j=0;j<len2;j++) b[j]=(s2[len2-j-1]-'0');
}
void count(){for(int i=0;i<len1;i++){for(int j=0;j<len2;j++){c[i+j]+=a[i]*b[j];}} for(int i=0;i<len3;i++){if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}}while(len3>0&&c[len3-1]==0) len3--;
}
void print(){for(int i=len3-1;i>=0;i--) cout<<c[i];
}
int main()
{
Read();
count();
print();return 0;
}

高精度除法

高精度除以低精度

因为除数是低精度，所以我们不用竖式就能解，用逐位相除法。

初始化+读入（因为是除法所以不用逆序存储，正着就行）

string s;
const int N=1050;
int a[N],c[N],b,len,lenc=1,x;
void Read(){cin>>s>>b;len=s.size();for(int i=1;i<=len;i++) a[i]=s[i-1]-'0';//顺着存
}

运算
因为除法如果不够除的话是填零（或是有余），我们可以将不够除（或除完的余数）的放入后面让他和后面的数一起除，不过要注意*10因为他们的单位不同,当然有时候我们会求余数，所以我们可以带入余数让计算的更简单些。

void count(){for(int i=1;i<=len;i++){c[i]=(x*10+a[i])/b;//带着余数除当除到最后一位时%后就是余数x=(x*10+a[i])%b;}while(lenc<len&&c[lenc]==0) lenc++;
}

输出

void print(){while(lenc<=len) cout<<c[lenc++];cout<<"\n";cout<<x;
}

总代码

#include<bits/stdc++.h>
using namespace std;
string s;
const int N=1050;
int a[N],c[N],b,len,lenc=1,x;
void Read(){cin>>s>>b;len=s.size();for(int i=1;i<=len;i++) a[i]=s[i-1]-'0';
}
void count(){for(int i=1;i<=len;i++){c[i]=(x*10+a[i])/b;x=(x*10+a[i])%b;}while(lenc<len&&c[lenc]==0) lenc++;
}
void print(){while(lenc<=len) cout<<c[lenc++];cout<<"\n";cout<<x;
}
int main()
{
Read();
count();
print();return 0;
}

高精度除以高精度

高精度除以高精度，第一眼肯定是竖式，但你用竖式算过后会发现，似乎难找到怎么做。所以我们得从其他方面入手，先看看除法算式a/b，平平无奇，写下结果后呢？a/b=c…d,看到这个算式大家应该有点印象了，二三年级时我们学习的除法各个元素之间的关系：
1.a=b×c+d
2.b=(a-d)/c
3.c=(a-d)/b
4.d=a-b×c
随后我们再回顾下除法的定义：把一个数平均分成几份。根据这几条不难发现，a/b,不就是a-c个b吗
所以我们便能开始写代码了
初始化+读入（注意这里出现减法了得倒序）

#define N 1050
int a[N],b[N],c[N],d,i;
void init(int a[]){string s;cin>>s;a[0]=s.size();for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';
}

判断大小函数（因为是减法替除法，要判断下，如果a<b就要终止）

int compare(int a[],int b[]){  int i;if(a[0]>b[0]) return 1;if(a[0]<b[0]) return -1;for(i=a[0];i>0;i--){if(a[i]>b[i]) return 1;if(a[i]<b[i]) return -1;}return 0;
}

移动函数，因为单位不统一，要将单位统一才能做减法

void numcpy(int p[],int q[],int det){for(int i=1;i<=p[0];i++) q[i+det-1]=p[i];q[0]=p[0]+det-1;
}

减法函数与除法函数

void jian(int a[],int b[]){int flag,i;flag=compare(a,b);if(flag==0){a[0]=0;return;}if(flag==1){for(i=1;i<=a[0];i++){if(a[i]<b[i]){a[i+1]--;a[i]+=10;}a[i]-=b[i]; }while(a[0]>0&&a[a[0]]==0) a[0]--;return; }
}
void chugao(int a[],int b[],int c[]){int i,tmp[N];c[0]=a[0]-b[0]+1;for(i=c[0];i>0;i--){memset(tmp,0,sizeof tmp);numcpy(b,tmp,i);while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}}while(c[0]>0&&c[c[0]]==0) c[0]--;return;
}

最后输出

void print(int a[]){int i;if(a[0]==0){cout<<0<<endl;return;}for(i=a[0];i>0;i--) cout<<a[i];cout<<endl;return;
}

总代码

#include<bits/stdc++.h>
using namespace std;
#define N 1050
int a[N],b[N],c[N],d,i;
void init(int a[]){string s;cin>>s;a[0]=s.length();for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';
}
void print(int a[]){int i;if(a[0]==0){cout<<0<<endl;return;}for(i=a[0];i>0;i--) cout<<a[i];cout<<endl;return;
}
int compare(int a[],int b[]){  int i;if(a[0]>b[0]) return 1;if(a[0]<b[0]) return -1;for(i=a[0];i>0;i--){if(a[i]>b[i]) return 1;if(a[i]<b[i]) return -1;}return 0;
}
void jian(int a[],int b[]){int flag,i;flag=compare(a,b);if(flag==0){a[0]=0;return;}if(flag==1){for(i=1;i<=a[0];i++){if(a[i]<b[i]){a[i+1]--;a[i]+=10;}a[i]-=b[i]; }while(a[0]>0&&a[a[0]]==0) a[0]--;return; }
}
void numcpy(int p[],int q[],int det){for(int i=1;i<=p[0];i++) q[i+det-1]=p[i];q[0]=p[0]+det-1;
}
void chugao(int a[],int b[],int c[]){int i,tmp[N];c[0]=a[0]-b[0]+1;for(i=c[0];i>0;i--){memset(tmp,0,sizeof tmp);numcpy(b,tmp,i);while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}}while(c[0]>0&&c[c[0]]==0) c[0]--;return;
}
int main()
{
init(a);
init(b);
chugao(a,b,c);
print(c);
print(a);//通过减法最后的a就是余数return 0;
}

高精度斐波那契数列

f[1]=1

f[2]=1

f[i]=f[i−1]+f[i−2]

求f[n]

输入
输入一个整数n

输出
输出一个整数

样例
输入 1
3
输出 1
2
提示
n<=200
【分析】这题目肯定要高精度的因为当n到100时都已经是354224848179261915075（别问我答案哪来的）了，long long 都存不下，所以的用高精度加法一步步加
好的高精度加法模板来了（没有读入）

const int N=1050;
int a[N],b[N],c[N],len=1,len1=1,len2=1;
void count(){int jw=0;for(int i=0;i<len;i++){c[i]=jw+a[i]+b[i];jw=c[i]/10;c[i]%=10;}if(jw==1){c[len]=1;len++;}while(len>1&&c[len-1]==0) len--;
}
void print(){
for(int i=len-1;i>=0;i--) cout<<c[i];
}

然后主函数部分是输出n，
对于这个n我们得先特判掉一些

if(n==1||n==2){cout<<1;return 0;
}

随后因为斐波那锲数列数f(n）=f(n-1)+f(n-2)，我们的先存入前两项

a[0]=1;
b[0]=1;

然后就是动规的模板了

for(int i=3;i<=n;i++){
c=a+b;
a=b;
b=c;
}

简单带入下便是

for(int i=3;i<=n;i++)
{count();len1=len2;for(int i=0;i<len2;i++){//数组赋值a[i]=b[i];}len2=len;for(int i=0;i<len;i++) b[i]=c[i];
}

最后别忘记输出
总代码

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int a[N],b[N],c[N],len=1,len1=1,len2=1;
void count(){int jw=0;for(int i=0;i<len;i++){c[i]=jw+a[i]+b[i];jw=c[i]/10;c[i]%=10;}if(jw==1){c[len]=1;len++;}while(len>1&&c[len-1]==0) len--;
}
void print(){
for(int i=len-1;i>=0;i--) cout<<c[i];
}
int main(){
int n;
cin>>n;
if(n==1||n==2){cout<<1;return 0;
}
a[0]=1;
b[0]=1;
for(int i=3;i<=n;i++)
{count();len1=len2;for(int i=0;i<len2;i++){a[i]=b[i];}len2=len;for(int i=0;i<len;i++) b[i]=c[i];
}
print();
return 0;
}

完结！