1. Introduction
In the process of solving problems in C language, we often encounter some problems that require large number processing.
Large numbers defined here are integers with hundreds of digits.
The usual approach is to convert large numbers into one-dimensional arrays and then perform four arithmetic operations.
Among the four arithmetic operations, division is the most difficult to achieve efficiently.
This article provides a templated solution to this high-precision large number division problem.
2. Algorithm implementation
(1) Data reading
First, our idea is to convert large numbers into one-dimensional arrays and store them. However, reading directly into the array will cause a problem. For example, if we define an array arr[1000] and read it directly, the highest bit of the large number will be stored in the array space with the subscript zero, which is arr[0]. This does not conform to our natural logic for numbers, and will also cause difficulties in subsequent processing. Therefore, among the numbers involved below, including the dividend, divisor, quotient, and remainder, we all use the reverse reading method, that is, the ones digit is stored in arr[0] and the tens digit is stored. In arr[1], and so on.
Define the array first
char beiChuShuStr[1004] = { 0 };
char chuShuStr[1004] = { 0 };
int beiChuShu[1004] = { 0 };
int chuShu[1004] = { 0 };
int shang[1004] = { 0 };
int yuShu[1004] = { 0 };
Why are two more string arrays defined here?
Because our processing idea is to first read the large number in the form of a string, and then reversely assign it to the numeric array
The specific implementation is as follows:
scanf("%s", beiChuShuStr);
scanf("%s", chuShuStr);
int len1 = strlen(beiChuShuStr);
int len2 = strlen(chuShuStr);
for (int i = 0; i < len1; i + + ) {//Input the string array into the integer array, and adjust the order so that the elements with subscripts are zero
beiChuShu[i] = beiChuShuStr[len1 - 1 - i] - '0';//corresponds to the ones digit, and the element with the subscript one corresponds to the tens digit
}
for (int i = 0; i < len2; i + + ) {
chuShu[i] = chuShuStr[len2 - 1 - i] - '0';
}
In this way, our large numbers have been successfully stored
Students can learn how to convert characters into numbers, just subtract 0’.
After completing the data reading, it is now time to determine the specific implementation of the algorithm.
A very simple idea is that division itself is the superposition of many subtractions. Then you just need to subtract the divisor from the dividend until it can no longer be subtracted, right? However, the efficiency of this idea is very low, because if the number of digits of the dividend is several hundred digits, and the number of digits of the divisor is dozens of digits, the quotient after division will most likely also be several hundred digits. It is equivalent to a computer having to perform calculations of 10 to the power of several hundred, which is very inefficient.
Let’s return to simplicity and see how we first calculated division by hand.
The answer is vertical division.
(2) Determine whether the first lb digit of the dividend can be subtracted from the divisor
A very important step in vertical division is to determine whether the first lb digits of the current dividend can be subtracted from the divisor, where lb is the length of the divisor. Right, especially for large numbers of hundreds of digits, this judgment needs to be performed hundreds of times, so we encapsulate a function to perform this judgment.
bool ability_to_subtraction(int a[], int b[], int last_weishu, int lb) {
if (a[last_weishu + lb] != 0)return true;
for (int i = lb; i > 0; i--) {
if (a[last_weishu + i - 1] > b[i - 1])return true;
if (a[last_weishu + i - 1] < b[i - 1])return false;
}
return true;
}
The blogger’s English is not good and he can only think of such a function name. It means the ability to subtract.
The passed-in last_weishu parameter has a size of la-lb and is used to describe the position of the smallest digit in the first lb digit of the dividend.
This statement means that if the length of the dividend obtained is larger than the divisor, then it can be subtracted;
if (a[last_weishu + lb] != 0)return true;
The meaning of this statement is to judge from the largest digit. If the digit of the dividend is greater than the divisor, it can be subtracted. If the digit of the dividend is smaller than the divisor, it cannot be subtracted;
for (int i = lb; i > 0; i--) {
if (a[last_weishu + i - 1] > b[i - 1])return true;
if (a[last_weishu + i - 1] < b[i - 1])return false;
}
The last statement return true means that if every digit taken out of the dividend is equal to the number in the position corresponding to the divisor, it can also be subtracted, and the result is zero.
(3) Repeat the subtraction operation with the new processed dividend
for (int i = 0; i < la; i + + ) {//Protect the dividend from changing, and finally get the result by changing the remainder
yuShu[i] = beiChuShu[i];
}
for (int i = la - lb; i >= 0; i--) {
while (ability_to_subtraction(yuShu, chuShu, i, lb)) {
for (int j = 0; j < lb; j + + ) {
yuShu[i + j] -= chuShu[j];
if (yuShu[i + j] < 0) {
yuShu[i + j] + = 10;
yuShu[i + j + 1] -= 1;
}
}
shang[i] + + ;
}
}
final output result
for (lc = 1004; lc >= 0; lc--)
if (yuShu[lc - 1] != 0)break;
for (ld = 1004; ld >= 0; ld--)
if (shang[ld - 1] != 0)break;
for (int i = 0; i < lc; i + + ) {
printf("%d", yuShu[i]);
}
printf("\
");
for (int i = 0; i < ld; i + + ) {
printf("%d", shang[i]);
}
3. Practical cases
Number of singles
The so-called “single” here does not mean single~ It refers to numbers composed entirely of ones, such as 1, 11, 111, 1111, etc. Legend has it that any bachelor can be divisible by an odd number that does not end with 5. For example, 111111 is divisible by 13. Now, your program needs to read an integer x. This integer must be odd and not end in 5. Then, after calculation, two numbers are output: the first number s means that x multiplied by s is a bachelor, and the second number n is the number of digits of this bachelor. Of course, such a solution is not unique. The question requires you to output the smallest solution.
Tip: An obvious solution is to gradually increase the number of digits until x is divisible. But the difficulty is that s may be a very large number – for example, if the program inputs 31, it will output 3584229390681 and 15, because the result of multiplying 31 by 3584229390681 is 111111111111111, a total of 15 ones.
Input format:
The input gives a positive odd number x (<1000) in a line that does not end in 5.
Output format:
Output the corresponding minimum s and n on one line, separated by 1 space.
Input sample:
31
Output sample:
3584229390681 15
Because this question obviously involves large numbers, we can directly learn from high-precision large number division.
Students can try it themselves, reference code is attached.
#include<stdio.h>
#include<string.h>
int ability_to_subtraction(int a[], int b[], int last_weishu, int lb) {
if (a[last_weishu + lb] != 0)return 1;
for (int i = lb; i > 0; i--) {
if (a[last_weishu + i - 1] > b[i - 1])return 1;
if (a[last_weishu + i - 1] < b[i - 1])return 0;
}
return 1;
}
int main() {
char N[4] = { 0 };
int n;
int flag = 0;
int yuShu[1002] = { 0 };
int chuShu[4] = { 0 };
int shang[1002] = { 0 };
scanf("%s", & amp;N);
int lb = strlen(N);
int ld;
for (int i = 0; i < lb; i + + ) {
chuShu[i] = N[lb - 1 - i] - '0';
}
//for (lb = 3; lb >= 0; lb--)
// if (chuShu[lb-1] != 0)break;
for (n = 1; n < 1000 & amp; & amp; !flag; n + + ) {
flag = 1;
memset(yuShu, 0, sizeof(yuShu));
memset(shang, 0, sizeof(shang));
for (int i = 0; i < n; i + + ) {//Generate the number of bachelors
yuShu[i] = 1;
}
for (int i = n - lb; i >= 0; i--) {
while (ability_to_subtraction(yuShu, chuShu, i, lb)) {
for (int j = 0; j < lb; j + + ) {
yuShu[i + j] -= chuShu[j];
if (yuShu[i + j] < 0) {
yuShu[i + j] + = 10;
yuShu[i + j + 1] -= 1;
}
}
shang[i] + + ;
}
}
for (int i = 0; i < 4; i + + ) {
if (yuShu[i] != 0)flag = 0;
}
}
if (flag) {
for (ld = 1002; ld >= 0; ld--)
if (shang[ld - 1] != 0)break;
for (int i = ld - 1; i >= 0; i--) {
printf("%d", shang[i]);
}
printf(" %d", n-1);
}
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57182 people are learning the system