C++少儿编程（17）高精度算法（乘除法）

1. # include <bits/stdc++.h> 
2. using namespace std; 
3. // 声明数组A、B，存储两个乘数的数位 
4. int A[101], B[101]; 
5. // 数组C存储B中数位与A的乘积（注意长度翻倍） 
6. int C[202]; 
7. // 每次得出C，将C累加到SUM中（注意长度与初始值） 
8. int SUM[202] = {1}; 
9. // 预处理：记录数位、分离数字、倒序存储 
10. void fen_li(string s, int a[]) { 
11.     // 将字符串长度存入数组的0号元素里 
12.     a[0] = s.size(); 
13.     // 从字符串中分离出数字，倒序存入数组中 
14.     for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0'; 
15.     return; 
16. } 
17. //声明加法运算函数（将C累加到SUM中） 
18. void big_plus(int C[], int SUM[]) { 
19.     SUM[0] = max(C[0], SUM[0]); // SUM[0]存储加数的最高数位 
20.     int j = 0;                  // 声明变量j存储进位数字，默认为0 
21.     for (int i = 1; i <= SUM[0]; i++) { 
22.         SUM[i] += C[i] + j;     // 计算当前数位两个加数与进位之和 
23.         j = SUM[i] / 10;        // 先计算新的进位 
24.         SUM[i] %= 10;           // 再处理结果（和）的当前数位 
25.     } 
26.     if (j > 0) {            // 如果最后的进位数字大于0 
27.         SUM[0]++;           // 结果的数位加1 
28.         SUM[SUM[0]] = j;    // 结果的最高数位设为进位数字 
29.     } 
30.     return; 
31. } 
32. // 声明乘法运算函数（B中第n数位与A相乘） 
33. void big_multiply(int n, int A[]) { 
34.     // 初始化数组C（所有元素设为0） 
35.     for (int i = 0; i < 202; i++) C[i] = 0; 
36.     C[0] = A[0] + n - 1;    // 设定当前乘积的数位 
37.     int j = 0;              // 进位默认为0 
38.     for (int i = 1; i <= A[0]; i++) {   // 遍历A中每一位 
39.         C[i+n-1] = B[n] * A[i] + j;     // 计算B[n]与A[i]的乘积再加进位数 
40.         j = C[i+n-1] / 10;              // 计算进位数 
41.         C[i+n-1] %= 10;                 // 计算当前数位 
42.     } 
43.     if (j > 0) {        // 如果最后的进位大于0 
44.         C[0]++;         // 结果的数位加1 
45.         C[C[0]] = j;    // 结果的最高数位这位进位数字 
46.     } 
47.     return; 
48. } 
49. int main() { 
50.     string a, b; 
51.     cin >> a >> b;      // 输入高精度乘数a、b的值 
52.     fen_li(a, A);       // 字符串预处理 
53.     fen_li(b, B); 
54.     for (int i = 1; i <= B[0]; i++) {   // 遍历B中的每个数位 
55.         big_multiply(i, A);      // 将当前遍历到的数与A相乘 
56.         big_plus(C, SUM);       // 将乘积C累加到SUM中 
57.     } 
58.     for (int i = SUM[0]; i > 0; i--) { 
59.         cout << SUM[i];     // 倒序输出SUM中的数位 
60.     } 
61.     cout << endl; 
62.     return 0; 
63. } 

【高精度乘法 - 示例程序】解析算法m0N100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. # include <bits/stdc++.h> 
2. using namespace std; 
3. string a, b;        // 声明字符串变量a、b存储两个乘数 
4. int A[101], B[101];     // 声明数组A、B，存储两个乘数的数位 
5. int C[202];     // 数组C存储B中数位与A的乘积（注意长度翻倍） 
6. void fen_li(string s, int a[]) {    // 预处理 
7.     a[0] = s.size();                // 记录数位、分离数字、倒序存储 
8.     for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0'; 
9.     return; 
10. } 
11. // 声明乘法运算函数：解析算法（A与B相乘，结果存入到C中） 
12. void big_multiply() { 
13.     C[0] = A[0] + B[0];     // 设定乘积的数位 
14.     int jw;         // 声明进位变量 
15.     for (int i = 1; i <= B[0]; i++) {   // 遍历B中每一位数字 
16.         jw = 0;     // 每轮内循环开启之前，进位值默认设为0 
17.         for (int j = 1; j <= A[0]; j++) {   // 遍历A中每一位数字 
18.             C[i+j-1] += A[j] * B[i] + jw;   // 根据解析公式计算C中数位 
19.             jw = C[i+j-1] / 10;     // 计算本次的进位值 
20.             C[i+j-1] %= 10;         // 计算当前数位 
21.         } 
22.         C[i+A[0]] = jw;     // 无论进位值是否为0，最后都存储一次进位值 
23.     } 
24.     while (C[C[0]] == 0 && C[0] > 1) C[0]--;    // 清空前导0 
25.     return; 
26. } 
27. int main() { 
28.     cin >> a >> b;      // 输入高精度乘数a、b的值 
29.     fen_li(a, A);       // 字符串预处理 
30.     fen_li(b, B); 
31.     big_multiply();     // 调用公式执行计算 
32.     // 倒序输出C中的每个数位 
33.     for (int i = C[0]; i > 0; i--) cout << C[i]; 
34.     cout << endl; 
35.     return 0; 
36. } 

1. #include <bits/stdc++.h> 
2. using namespace std; 
3. // 求5000以内的阶乘（低精度与高精度相乘） 
4. int ret[100000];   // 使用数组存储结果 ret，默认为10万位 
5. int n, k, jw;   // n为输入数字，k为结果的数位个数，jw表示进位值 
6. int main() { 
7.     k = 1; 
8.     ret[1] = 1; 
9.     cin >> n; 
10.     // 特殊情况处理 
11.     if (n < 0) cout << "输入有误" << endl; 
12.     if (n < 2) cout << 1 << endl; 
13.     // 循环2~n之间的每个数，分别与ret相乘（低精度乘以高精度） 
14.     for (int i = 2; i <= n; i++) { 
15.         jw = 0;     // 每轮内层循环开启之前，都要将进位重置为0 
16.         for (int j = 1; j <= k; j++) {  // 遍历ret的每个数位 
17.             int tmp = ret[j] * i + jw;  // 将相乘之积与进位之和存入tmp临时变量中 
18.             jw = tmp / 10;              // 计算当前进位值 
19.             ret[j] = tmp % 10;          // 计算当前结果数位 
20.         } 
21.         while (jw > 0) {        // 每次内层循环结束之后，只要进位值大于0 
22.             k++;                // 就将数位个数加1 
23.             ret[k] = jw % 10;   // 将第k为数字设为进位的末位数字 
24.             jw /= 10;           // 去除进位值的末位数字 
25.         } 
26.     } 
27.     // 输出结果：倒序输出数组ret中的元素 
28.     for (int i = k; i > 0; i--) cout << ret[i]; 
29.     cout << endl; 
30.     return 0; 
31. } 

1. #include <bits/stdc++.h> 
2. using namespace std; 
3. // 求a^b（a、b均为低精度），低精度与高精度的乘法 
4. int ret[100000]; // 使用数组存储结果 ret，默认为10万位 
5. int a, b, k, jw;    // a、b为输入数字，k为结果的数位个数，jw表示进位值 
6. int main() { 
7.     k = 1;          // 默认数位为 1 
8.     ret[1] = 1;     // 第一位的数位值为 1 
9.     cin >> a >> b;  // 输入a、b、的值 
10.     // 特殊情况处理 
11.     if (b < 0) 
12.         cout << "输入有误" << endl; 
13.     // 循环b次，分别与ret相乘（低精度乘以高精度） 
14.     for (int i = 1; i <= b; i++) { 
15.         jw = 0; // 每轮内层循环开启之前，都要将进位重置为0 
16.         for (int j = 1; j <= k; j++) {  // 遍历ret的每个数位 
17.             int tmp = ret[j] * a + jw; // 将相乘之积与进位之和存入tmp临时变量中 
18.             jw = tmp / 10;             // 计算当前进位值 
19.             ret[j] = tmp % 10;         // 计算当前结果数位 
20.         } 
21.         while (jw > 0) {      // 每次内层循环结束之后，只要进位值大于0 
22.             k++;              // 就将数位个数加1 
23.             ret[k] = jw % 10; // 将第k为数字设为进位的末位数字 
24.             jw /= 10;         // 去除进位值的末位数字 
25.         } 
26.     } 
27.     // 输出结果：倒序输出数组ret中的元素 
28.     for (int i = k; i > 0; i--) cout << ret[i]; 
29.     cout << endl; 
30.     return 0; 
31. }