高精度模拟算法

高精度模拟算法

• 高精度加法

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];
}

• 高精度除法

1. 低精度/低精度 商为高精度型(保留小数点后$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;
   }
   

2. 高精度/低精度型(逐位试商法)

   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];
   }
   

3. 高精度/高精度型(减法模拟法)

   #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则为0if (a[0] > b[0]) return 1;  //若a的位数大于b，则a>bif (a[0] < b[0]) return -1;  //若a的位数小于b，则a<bfor (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;
   }