1.大数相加
1.1 思路:
数组模拟小学加法过程 就行
首先将 str1 ,str2 逆序存入 a[ ],b[ ],c[ ] 记录结果
Max=( str1,str2 ) + 1
for 0 to Max-1
a[ i ] 加入,b[ i ] 加入
c[ i + 1 ] = c [ i ] /10; //进位
c[ i ] = c[ i ] %10;
end
删除前导零
1.2 代码模板:
#include<iostream> #include<algorithm> #include<cstring> #include<string> using namespace std; int c[205],num; void Plus(string A,string B){ int a[205],b[205]; int sa=A.size(),sb=B.size(); num=max(sa,sb)+1; for(int i=0;i<sa;i++) a[i]=A[sa-i-1]-'0'; for(int i=0;i<sb;i++) b[i]=B[sb-i-1]-'0'; c[0]=0; for(int i=0;i<num;i++){ if(i<sa)c[i]+=a[i]; if(i<sb)c[i]+=b[i]; c[i+1]=c[i]/10; c[i]%=10; } while(!c[num]&&num>=1)num--; } int main(){ string A,B; cin>>A>>B; Plus(A,B); for(int i=num;i>=0;i--) cout<<c[i]; cout<<endl; return 0; }
1.3 函数主体
int c[205],num; void Plus(string A,string B){ int a[205],b[205]; int sa=A.size(),sb=B.size(); num=max(sa,sb)+1; for(int i=0;i<sa;i++) a[i]=A[sa-i-1]-'0'; for(int i=0;i<sb;i++) b[i]=B[sb-i-1]-'0'; c[0]=0; for(int i=0;i<num;i++){ if(i<sa)c[i]+=a[i]; if(i<sb)c[i]+=b[i]; c[i+1]=c[i]/10; c[i]%=10; } while(!c[num]&&num>=1)num--; }
1.4 其他模板(更简单)
string Plus(string str1,string str2){ string str; int len1=str1.size(),len2=str2.size(); if(len1<len2){ for(int i=1;i<=len2-len1;i++){ str1="0"+str1; } } else{ for(int i=1;i<=len1-len2;i++){ str2="0"+str2; } } len1=str1.size(); int num=0; int t; for(int i=len1-1;i>=0;i--){ t=str1[i]-'0'+str2[i]-'0'+num; num=t/10;//进位 t%=10; str=char(t+'0')+str; } if(num==1){ str='1'+str; } while(str[0]=='0'&&str.size()>1)str.erase(0,1);//删除前导零 return str; }
2.大数相减
1.1 思路:
模拟减法运算
g 记录借位
place 当前位置的值
place=a[ i ] - g - b[ i ] ;//先减去上一位的借位
if(place>=0) g=0;
else {
g=1;
place+=10;
}
ans=char(place+'0')+ans;
2.2 代码:
字符串
#include<bits/stdc++.h> #define ll long long using namespace std; const int MA=1e5+5; string Minus(string a,string b){ string ans=""; bool flag=true; if(a.size()<b.size()||(a.size()==b.size()&&a.compare(b)<0)){ swap(a,b); flag=false; } ll x1=a.size(),x2=b.size(); if(x1>x2){ for(ll i=1;i<=x1-x2;i++){ b='0'+b; } } x2=b.size(); int g=0; for(ll i=x1-1;i>=0;i--){ int place=a[i]-'0'-g;//减去借位 place-=b[i]-'0'; if(place>=0) g=0; else{ g=1; place+=10; } ans=char(place+'0')+ans; } while(ans[0]=='0'&&ans.size()>1)ans.erase(0,1);//注意删除前导零 if(!flag)ans='-'+ans; return ans; } int main(){ string a,b; cin>>a>>b; string c; c=Minus(a,b); cout<<c<<endl; return 0; }
数组
#include<iostream> #include<algorithm> #include<string> #include<cstring> using namespace std; const int MA=1e7+5; int c[MA]; int array_a[MA],array_b[MA]; int num; void Minus(string A,string B){ //只进行A>B的操作,A<B在主函数进行 int lena=A.size(),lenb=B.size(); for(int i=0;i<lena;i++) array_a[i]=A[lena-i-1]-'0'; for(int i=0;i<lenb;i++) array_b[i]=B[lenb-i-1]-'0'; num=0; int g=0; //借位操作时使用 for(int i=0;i<max(lena,lenb);i++){ int place=array_a[i]-g; //数减上一位借的数(0,1) if(i<lenb) place-=array_b[i]; if(place>=0) g=0; else{ g=1; //向后一位借1 place+=10; } c[num++]=place; } while(!c[num]&&num>=1)num--; //去除前导零 } int main() { string A,B; cin>>A>>B; if(A.size()<B.size()||(A.size()==B.size()&&A.compare(B)<0)){ swap(A,B); cout<<"-"; } Minus(A,B); for(int i=num;i>=0;i--) cout<<c[i]; cout<<endl; return 0; }
3.高精度乘法
3.1思路
3.2代码
#include<bits/stdc++.h> #define ll long long using namespace std; string multiplication(string a,string b){ string ans="0"; ll x1=a.size(),x2=b.size(); ll k=ans.size()-1; for(ll i=x1-1;i>=0;i--){ k=ans.size()-1-(x1-1-i); for(ll j=x2-1;j>=0;j--){ int place=(a[i]-'0')*(b[j]-'0')+ans[k]-'0'; if(k-1<0){ ans='0'+ans; k++; } ans[k-1]=char((ans[k-1]-'0'+place/10)+'0'); ans[k]=char(place%10+'0'); k--; } } while(ans[0]=='0'&&ans.size()>1)ans.erase(0,1); return ans; } int main(){ string a,b; cin>>a>>b; cout<<multiplication(a,b)<<endl; return 0; }
3.3函数主体
string multiplication(string a,string b){ string ans="0"; ll x1=a.size(),x2=b.size(); ll k=ans.size()-1; for(ll i=x1-1;i>=0;i--){ k=ans.size()-1-(x1-1-i); for(ll j=x2-1;j>=0;j--){ int place=(a[i]-'0')*(b[j]-'0')+ans[k]-'0'; if(k-1<0){ ans='0'+ans; k++; } ans[k-1]=char((ans[k-1]-'0'+place/10)+'0'); ans[k]=char(place%10+'0'); k--; } } while(ans[0]=='0'&&ans.size()>1)ans.erase(0,1); return ans; }
4.高精度除法
4.1高精度 ÷ 高精度
#include<iostream> #include<cstring> using namespace std; int a[100],b[100],c[100]; int compare(int a[],int b[])//比较a、b,若a>b为1;若a<b为-1;若a=b为0 { 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 subduction(int a[],int b[])//计算a=a-b { int flag; int 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)//删除前导0 a[0]--; return; } } int main() { char str1[100],str2[100]; int i,j; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); cin>>str1>>str2; a[0]=strlen(str1);//a[0]存储串1的位数 b[0]=strlen(str2);//b[0]存储串2的位数 for(i=1;i<=a[0];i++) a[i]=str1[a[0]-i]-'0'; for(i=1;i<=b[0];i++) b[i]=str2[b[0]-i]-'0'; int temp[100]; c[0]=a[0]-b[0]+1; for(i=c[0];i>0;i--) { memset(temp,0,sizeof(temp)); for(j=1;j<=b[0];j++)//从i开始的地方,复制数组b到数组temp temp[j+i-1]=b[j]; temp[0]=b[0]+i-1; while(compare(a,temp)>=0)//用减法模拟 { c[i]++; subduction(a,temp); } } while(c[0]>0&&c[c[0]]==0)//删除前导0 c[0]--; cout<<"商为:"; if(c[0]==0)//输出结果 cout<<0<<endl; else { for(i=c[0];i>0;i--) cout<<c[i]; cout<<endl; } cout<<"余数为:"; if(a[0]==0)//输出余数 cout<<0<<endl; else { for(i=a[0];i>0;i--) cout<<a[i]; cout<<endl; } return 0; }
4.2高精度 ÷ 低精度
r为余数
int r; string chu(string a,int b){ string ans=""; int x1=a.size(); r=0; for(int i=0;i<x1;i++){ r=r*10+a[i]-'0'; ans=ans+char(r/b+'0'); r%=b; } while(ans[0]=='0'&&ans.size()>1)ans.erase(0,1); return ans; }
高精度阶乘计算
模拟一下就好,记住每次乘完要将进位while()
1 #include<bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 string fac(int n){ 5 string ans="1"; 6 if(n==0)return ans; 7 for(int k=2;k<=n;k++){ 8 LL c=0; 9 for(int i=ans.size()-1;i>=0;i--){ 10 LL s=(LL)(ans[i]-'0')*k+c; 11 c=s/10; 12 ans[i]=(char)(s%10+'0'); 13 } 14 while(c){ 15 int t=c%10; 16 ans=(char)(t+'0')+ans; 17 c/=10; 18 } 19 } 20 return ans; 21 } 22 int main(){ 23 int n; 24 cin>>n; 25 cout<<fac(n)<<endl; 26 return 0; 27 }