Why high precision calculations
For C++, the largest data is long long (64b, 8 bits). For data exceeding 8B, C++ has no corresponding data type. So we need to know high precision calculations. More detailed explanation, you can refer to this web page blog.csdn.net/justidle/ar…
High precision addition calculation principle
When we were in primary school, we used the vertical method of addition, as shown in Figure 1. In this way, we can easily write the algorithm for adding two integers.
We can simulate this vertical addition in C++. We can consider using C++ arrays to store the corresponding data. Suppose we use array A to store each bit of 856. Specifically, A1 stores the bits 6, A2 stores the tens 5, and A3 stores the hundreds 8. Array A: 255; array B: 255; Similar to the structure of array A, C is used to store the corresponding and 1111. The result of adding the two numbers is shown in Figure 2. So, in theory, we can calculate infinitely large numbers. As shown in Figure 2, the following table shows the corresponding storage methods.
Conclusion: Use array storage, break through the limitations of storage. Each location stores data between 0 and 9.
High precision addition implementation
Train of thought
1. Define storage arrays.
2. Read data into an array. Notice it’s in reverse order, so the ones place is at the index zero.
3. Start from the ones place to simulate the process of vertical addition and complete the entire addition.
4. Delete leading 0. A leading zero is something like 01234, which you don’t really need.
5. Output the result of addition. Output the result array C of addition in reverse order, because our ones bits are stored at subscript 0.
Technical Details
Defining a storage array
Define an array as the problem dictates. This part of the code is as follows:
const int MAXN = 1e5+4; // According to the maximum value of the problem. Char s1[MAXN] = {}; Char s2[MAXN] = {}; Int a[MAXN] = {}; Int b[MAXN] = {}; Int c[MAXN] = {}; // Store and BCopy the codeRead data into an array
Data is read in the same way as a string, and then written in reverse order to the corresponding array. This part of the code is as follows:
scanf("%s %s", s1, s2); Int len1 = strlen(s1); int len1 = strlen(s1); for (int i=0; i<len1; I ++) {a[I] = s1[len1-i-1] - '0'; } // Write A string to array A int len2 = strlen(s2); for (int i=0; i<len2; I ++) {// write in reverse order b[I] = s2[len2-i-1] - '0'; }Copy the codeNote: We need to save the maximum length of the addends A and B. Because vertical addition requires.
Simulate vertical addition
There are two technical details: 1. 2, how to solve the highest carry. This part of the code is as follows:
Int jw=0; Int len = Max (len1, len2)+1; For (int I =0; i<len; i++) { c[i] = a[i] + b[i] + jw; Jw = c[I] / 10; jw = c[I] / 10; C [I] %= 10; // Can only store data from 0 to 9}Copy the codeDelete leading zeros
Because the addition operation can have the highest carry, we simulated vertical addition by adding an extra bit, so we need to determine whether we need to remove leading zeros. This part of the code is as follows:
For (int I =len-1; i>=0; If (0==c[I] &&len >1) {if (0==c[I] &&len >1) {if (0==c[I] &len >1) {if (0==c[I] &len >1) { In the special case where the addition is 00, we actually want to print 0. len--; } else {// the first bit is not the highest bit of zero, end delete break; }}Copy the codeOutput calculation results
The output is in reverse order, because our data is stored in reverse order structure, that is, the low position is in front.
For (int I =len-1; i>=0; i--) { printf("%d", c[i]); } printf("\n");Copy the codeExamples and AC code
The title
Title links to a general OJ: ybt. Ssoier. Cn: 8088 / problem_sho…
My own OJ: http://47.110.135.197/problem.php? Id = 1215.
Topic describes
Find the sum of two non-negative integers up to 200 digits.
The input
There are two lines, each of which is a non-negative integer with no more than 200 digits and may have extra leading zeros.
The output
One row, which is the sum. There can be no extra leading 0 in the result, that is, if the result is 342, then 0342 cannot be printed.
The sample input
22222222222222222222, 33333333333333333333,
Sample output
55555555555555555555
Analysis of the
And they tell us that MAXN is equal to 200 digits, or MAXN is equal to 200 plus 4.
AC code
#include <bits/stdc++.h> using namespace std; const int MAXN = 200+4; // According to the maximum value of the problem. Char s1[MAXN] = {}; Char s2[MAXN] = {}; Int a[MAXN] = {}; Int b[MAXN] = {}; Int c[MAXN] = {}; // store and B int main() {scanf("%s %s", s1, s2); Int len1 = strlen(s1); int len1 = strlen(s1); for (int i=0; i<len1; I ++) {a[I] = s1[len1-i-1] - '0'; } // Write A string to array A int len2 = strlen(s2); for (int i=0; i<len2; I ++) {// write in reverse order b[I] = s2[len2-i-1] - '0'; } // int jw=0; Int len = Max (len1, len2)+1; For (int I =0; i<len; i++) { c[i] = a[i] + b[i] + jw; Jw = c[I] / 10; jw = c[I] / 10; C [I] %= 10; For (int I =len-1; i>=0; If (0==c[I] &&len >1) {if (0==c[I] &&len >1) {if (0==c[I] &len >1) {if (0==c[I] &len >1) { In the special case where the addition is 00, we actually want to print 0. len--; } else {// the first bit is not the highest bit of zero, end delete break; For (int I =len-1; i>=0; i--) { printf("%d", c[i]); } printf("\n"); return 0; }Copy the codeCopyright notice: This article is an original article BY CSDN blogger “Hard Lao Zhou”. It follows CC 4.0 BY-SA copyright agreement. Please attach the source link of the original article and this statement. The original link: blog.csdn.net/justidle/ar…