高精度算法
高精度，就是实现两个大整数四则运算的算法。其实本质就是模拟我们小学学过的竖式运算。原理可以说是非常简单，但是写起代码就不太好写了。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<string> 5 #include<vector> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 struct bign 10 { 11 string a; 12 int s[100100]; 13 int l; 14 friend bign operator + (bign x,bign y) 15 { 16 x.l = (int)x.a.size(); 17 y.l = (int)y.a.size(); 18 for(int i = 0;i < x.l;i++) x.s[x.l - 1 - i] = x.a[i] - '0'; 19 for(int i = 0;i < y.l;i++) y.s[y.l - 1 - i] = y.a[i] - '0'; 20 bign ans; 21 ans.l = max(x.a.size(),y.a.size()); 22 for(int i = 0;i < ans.l;i++) 23 { 24 ans.s[i] = x.s[i] + y.s[i]; 25 } 26 for(int i = 0;i < ans.l;i++) 27 if(ans.s[i] >= 10) 28 { 29 ans.s[i + 1] += ans.s[i] / 10; 30 ans.s[i] %= 10; 31 } 32 while(ans.s[ans.l] != 0) ans.l++; 33 return ans; 34 } 35 }; 36 void print(bign a) 37 { 38 for(int i = a.l - 1;i >= 0;i--) printf("%d",a.s[i]); 39 return; 40 } 41 int main() 42 { 43 freopen("bigadd.in","r",stdin); 44 freopen("bigadd.out","w",stdout); 45 bign x,y; 46 cin >> x.a; 47 cin >> y.a; 48 print(x + y); 49 }加法
减法，两数相减，不妨设左边的比右边的大，如果反之则交换并输出负号，然后运算就行。最后处理借位的问题。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。然而有一个特例，如果两数相等，必须输出0而不是-0QAQ
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<string> 5 #include<vector> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 struct bign 10 { 11 string a; 12 int s[100100]; 13 int l; 14 friend bool operator == (bign &x,bign &y) 15 { 16 if(x.l != y.l) return 0; 17 for(int i = x.l - 1;i >= 0;i--) 18 if(x.s[i] != y.s[i]) return 0; 19 return 1; 20 } 21 friend bool operator < (bign &x,bign &y) 22 { 23 if(x.l != y.l) return x.l < y.l; 24 for(int i = x.l - 1;i >= 0;i--) 25 if(x.s[i] != y.s[i]) return x.s[i] < y.s[i]; 26 } 27 friend bign operator - (bign &x,bign &y) 28 { 29 bign ans; 30 ans.l = x.l; 31 for(int i = 0;i < ans.l;i++) 32 { 33 ans.s[i] = x.s[i] - y.s[i]; 34 } 35 for(int i = 0;i < ans.l - 1;i++) 36 while(ans.s[i] < 0) 37 { 38 ans.s[i] += 10; 39 ans.s[i + 1]--; 40 } 41 while(ans.s[ans.l - 1] == 0) ans.l--; 42 return ans; 43 } 44 }; 45 void print(bign a) 46 { 47 for(int i = a.l - 1;i >= 0;i--) printf("%d",a.s[i]); 48 return; 49 } 50 int main() 51 { 52 //freopen("test.in","r",stdin); 53 //freopen("test.out","w",stdout); 54 bign x,y; 55 cin >> x.a; 56 cin >> y.a; 57 x.l = (int)x.a.size(); 58 y.l = (int)y.a.size(); 59 for(int i = 0;i < x.l;i++) x.s[x.l - 1 - i] = x.a[i] - '0'; 60 for(int i = 0;i < y.l;i++) y.s[y.l - 1 - i] = y.a[i] - '0'; 61 if(x == y) 62 { 63 printf("0"); 64 return 0; 65 } 66 if(x < y) 67 { 68 swap(x,y); 69 printf("-"); 70 } 71 print(x - y); 72 return 0; 73 }减法
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<string> 5 #include<vector> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 struct bign 10 { 11 string a; 12 int s[30000]; 13 int l; 14 friend bign operator * (bign x,bign y) 15 { 16 x.l = (int)x.a.size(); 17 y.l = (int)y.a.size(); 18 for(int i = 0;i < x.l;i++) x.s[x.l - 1 - i] = x.a[i] - '0'; 19 for(int i = 0;i < y.l;i++) y.s[y.l - 1 - i] = y.a[i] - '0'; 20 bign ans; 21 ans.l = x.l + y.l + 10; 22 for(int j = 0;j < y.l;j++) 23 { 24 for(int i = 0;i < x.l;i++) 25 { 26 ans.s[i + j] += x.s[i] * y.s[j]; 27 } 28 } 29 for(int i = 0;i < ans.l;i++) 30 { 31 if(ans.s[i] >= 10) 32 { 33 ans.s[i + 1] += ans.s[i] / 10; 34 ans.s[i] %= 10; 35 } 36 } 37 while(ans.s[ans.l - 1] == 0) ans.l--; 38 return ans; 39 } 40 }; 41 void print(bign a) 42 { 43 for(int i = a.l - 1;i >= 0;i--) printf("%d",a.s[i]); 44 return; 45 } 46 int main() 47 { 48 freopen("t.in","r",stdin); 49 freopen("t.out","w",stdout); 50 bign x,y; 51 cin >> x.a; 52 cin >> y.a; 53 print(x * y); 54 }乘法
更多精彩
