高精度模拟算法
- 高精度加法
extern string m,n;
extern int a[MAX],b[MAX],ans[MAX];
void addition(){
int _m=max(m.size(),n.size());
reverse(m.begin(),m.end()),reverse(n.begin(),n.end());//转置原字符串
for(int i=0;i<m.size();i++) a[i]=m[i]-'0';//字符型以ASCII码存储，需要转换为整形
for(int i=0;i<n.size();i++) b[i]=n[i]-'0';
//核心部分
for(int i=0;i<_m;i++){
ans[i]+=(a[i]+b[i]);
ans[i+1]+=ans[i]/10;//处理进位 (进位可能不止1,故不写ans[i+1]++)
ans[i]%=10;//确定最终结果
}
while((c[_m]==0&&_m>0)) _m--;//删前导零
for(int i=_m;i>=0;i--) cout<<ans[i];
}
- 高精度减法
extern string m,n;
extern int a[MAX],b[MAX],ans[MAX];
extern bool flag;//标识原结果为负，最后需输出负号
void subtractive(){
int _m=max(m.size(),n.size());
//交换两字符串，使被减数>减数
if(m.size()<n.size()) swap(m,n),flag=1;//位数小的直接交换
else if(m.size()==n.size())//位数相等逐位比较
for(int i=0;i<_m;i++)
if(m[i]<n[i]) swap(m,n),flag=1;
reverse(m.begin(),m.end()),reverse(n.begin(),n.end());//转置原字符串
for(int i=0;i<m.size();i++) a[i]=m[i]-'0';//字符型以ASCII码存储，需要转换为整形
for(int i=0;i<n.size();i++) b[i]=n[i]-'0';
//核心部分
for(int i=0;i<_m;i++){
if(a[i]<b[i]){//处理借位
a[i+1]--;//下一位被借1个
a[i]+=10;//本位+10
}
ans[i]=a[i]-b[i];
}
if(flag) cout<<'-';
while(ans[_m]==0&&_m>0) _m--;//删除前导零 注意减法相同数字相减为0 因此可能有多个前导零
for(int i=_m;i>=0;i--) cout<<ans[i];
}
- 高精度乘法
extern string m,n;
extern int a[MAX],b[MAX],ans[2*MAX];//两数相乘结果最长为两数长之和
void subtraction(){
int _m=m.size()+n.size();//两数相乘结果最长为两数长之和
reverse(m.begin(),m.end()),reverse(n.begin(),n.end());//转置原字符串
for(int i=0;i<m.size();i++) a[i]=m[i]-'0';
for(int i=0;i<n.size();i++) b[i]=n[i]-'0';
for(int i=0;i<m.size();i++){
for(int j=0;j<n.size();j++){
ans[i+j]+=b[j]*a[i];//每位相乘,结果索引为每位索引之和
ans[i+j+1]+=ans[i+j]/10;//处理进位 由于进位可能不止1,故不写ans[i+1]++
ans[i+j]%=10;//确定最终结果
}
}
while(ans[_m]==0&&_m>0) _m--;//删前导零
for(int i=_m;i>=0;i--) cout<<ans[i];
}
- 高精度除法
低精度/低精度 商为高精度型(保留小数点后 n n n位问题)
extern int a,b,n,t;//a:被除数 b:除数 n:小数点后保留位数 t:余数 extern string ans; void division(){ ans+=to_string(a/b)+'.'; t=a%b;//更新余数 while(n--){ ans+=to_string(t*10/b); t=t*10%b;//更新余数t } cout<<ans; }高精度/低精度型(逐位试商法)
extern string m;//m:被除数 extern long long n,a[MAX],ans[MAX],x;//n:除数 x:余数 void division(){ int _m=m.size();//商的最大长度为被除数长度 for(int i=0;i<_m;i++) a[i]=m[i]-'0'; for(int i=0;i<_m;i++){ ans[i]=(x*10+a[i])/n;//商=(余数*10+本位)/除数 x=(x*10+a[i])%n;//更新余数=(余数*10+本位)%除数 } int i=0; while(ans[i]==0&&i<_m-1) j++;//删前导零 注意不能把0全删了 for(;i<_m;i++) cout<<ans[i]; }高精度/高精度型(减法模拟法)
#include <bits/stdc++.h> using namespace std; // 减法部分 int a[101],b[101],c[101],d,i; void inp(int a[]){ // 读入 string s; cin >> s; //读入字符串 a[0] = s.size(); //a[0]储存字符串的长度 for (i = 1;i <= a[0];i++) a[i] = s[a[0] - i] - '0'; } void pri(int a[]){ // 输出 if (a[0] == 0){ cout << "0" << endl; return; } for (i = a[0];i > 0;i--) cout << a[i]; cout << endl; return; } int cmp(int a[],int b[]){//比较a和b的大小关系，若a>b则为1，若a<b则为-1，若a=b则为0 if (a[0] > b[0]) return 1; //若a的位数大于b，则a>b if (a[0] < b[0]) return -1; //若a的位数小于b，则a<b 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 pd = cmp(a,b); // 比较大小 if (pd == 0){ // 相等 a[0] = 0; return; }else if (pd == 1){ for (i = 1;i <= a[0];i++){ if (a[i] < b[i]) a[i + 1]--,a[i] += 10; // 借位 if (a[i] >= b[i]) a[i] -= b[i]; } while((a[a[0]] == 0) && (a[0] > 0)) a[0]--; return; } } void numcpy(int p[],int q[],int det){ for (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[101]; c[0] = a[0] - b[0] + 1; for (i = c[0];i > 0;i--){ memset(tmp,0,sizeof(tmp)); numcpy(b,tmp,i); while (cmp(a,tmp) >= 0){ c[i]++; jian(a,tmp); } } while((c[c[0]] == 0) && (c[0] > 0)) c[0]--; } // 应用部分 int main(){ inp(a),inp(b); chugao(a,b,c); pri(c),pri(a); return 0; }
