C++ 高精度数计算

zltzlt

高精度数计算

头文件 high_pre.h：

1. #include <iostream>
   
2. #include <cstring>
   
3. #include <cstdlib>
   
4. #include <cmath>
   
5. 
   
6. using namespace std;
   
7. const int digit = 10000; // 最多一万位
   
8. 
   
9. int *input(string prompt = "")
   
10. {
    
11.     /* 询问用户输入高精度数 */
    
12.     int *a = (int *)malloc(digit + 1), i;
    
13.     string s;
    
14.     cout << prompt;
    
15.     getline(cin, s);
    
16.     memset(a, 0, sizeof(a)); // 数组清零
    
17.     a[0] = s.size();         // 位数
    
18.     for (i = 1; i <= a[0]; i++)
    
19.         a[i] = s[a[0] - i] - '0'; // 将字符串转为数字并倒序存储
    
20.     return a;
    
21. }
    
22. 
    
23. void print(int num[], string end = "\n")
    
24. {
    
25.     /* 打印高精度数 */
    
26.     int i = num[0];
    
27.     for (; i > 0; i--)
    
28.         cout << num[i];
    
29.     cout << end;
    
30. }
    
31. 
    
32. int compare(int a[], int b[])
    
33. {
    
34.     /* 比较 a 和 b 的大小关系，若 a > b 则返回 1，a < b 则返回 -1，a == b 则返回 1 */
    
35.     int i;
    
36.     if (a[0] > b[0])
    
37.         return 1; // a 的位数大于 b 的位数，则 a 比 b 大
    
38.     if (b[0] > a[0])
    
39.         return -1; // b 的位数大于 a 的位数，则 b 比 a 大
    
40.     for (i = a[0]; i > 0; i--)
    
41.     {
    
42.         if (a[i] > b[i])
    
43.             return 1;
    
44.         if (a[i] < b[i])
    
45.             return -1;
    
46.     }
    
47.     return 0; // 各位都相等则两数相等
    
48. }
    
49. 
    
50. int *add(int a[], int b[])
    
51. {
    
52.     /* 计算 a + b 并返回 */
    
53.     int i = 1, k = a[0] > b[0] ? a[0] : b[0], *r = (int *)malloc(digit + 1); // k 是 a 和 b 中位数最大的数的位数
    
54.     for (; i <= k; i++)
    
55.     {
    
56.         r[i + 1] = a[i + 1] + (a[i] + b[i]) / 10; // 有进位，先进位
    
57.         r[i] = (a[i] + b[i]) % 10;                // 计算当前位数字
    
58.     }
    
59.     if (r[k + 1] > 0)
    
60.         r[0] = k + 1; // 修正新的数字的位数
    
61.     else
    
62.         r[0] = k;
    
63.     return r;
    
64. }
    
65. 
    
66. int *sub(int a[], int b[])
    
67. {
    
68.     /* 计算 a - b 并返回，如果 a < b 或 a == b 则返回 0 */
    
69.     int flag = compare(a, b), i = a[0], *r = (int *)malloc(digit + 1); // 调用比较函数比较大小
    
70.     if (flag != 1)
    
71.     {
    
72.         r[0] = 1;
    
73.         r[1] = 0;
    
74.         return r;
    
75.     }
    
76.     r[0] = a[0];
    
77.     for (; i > 0; i--)
    
78.         r[i] = a[i];
    
79.     for (i = 1; i <= a[0]; i++)
    
80.     {
    
81.         if (a[i] < b[i])
    
82.         {
    
83.             // 不够减，向上借 1
    
84.             r[i + 1]--;
    
85.             r[i] += 10;
    
86.         }
    
87.         r[i] -= b[i];
    
88.         if (r[i] < 0)
    
89.         {
    
90.             r[i + 1]--;
    
91.             r[i] += 10;
    
92.         }
    
93.     }
    
94.     while (!r[r[0]])
    
95.         r[0]--; // 修正 r 的位数
    
96.     return r;
    
97. }
    
98. 
    
99. int *convert(unsigned long long n)
    
100. {
     
101.     /* 将非负整数转化成高精度数 */
     
102.     int i, dg, *r = (int *)malloc(digit + 1);
     
103.     if (n < 10)
     
104.         dg = 1;
     
105.     else
     
106.     {
     
107.         i = 2;
     
108.         for (;; i++)
     
109.         {
     
110.             if (n < pow(10, i))
     
111.             {
     
112.                 dg = i;
     
113.                 break;
     
114.             }
     
115.         }
     
116.     }
     
117.     r[0] = dg;
     
118.     for (i = 1; i <= dg; i++)
     
119.         r[i] = n % int(pow(10, i)) / int(pow(10, i - 1));
     
120.     return r;
     
121. }
     
122. 
     
123. int *mul(int a[], int b[])
     
124. {
     
125.     /* 计算 a * b */
     
126.     int i, j, *r = (int *)malloc(digit + 1);
     
127.     memset(r, 0, sizeof(r));
     
128.     for (i = 1; i <= a[0]; i++)
     
129.     {
     
130.         for (j = 1; j <= b[0]; j++)
     
131.         {
     
132.             r[i + j - 1] = r[i + j - 1] + a[i] * b[j];
     
133.             r[i + j] = r[i + j] + r[i + j - 1] / 10;
     
134.             r[i + j - 1] = r[i + j - 1] % 10;
     
135.         }
     
136.     }
     
137.     r[0] = a[0] + b[0];
     
138.     if (!r[r[0]])
     
139.         r[0]--;
     
140.     return r;
     
141. }
     
142. 
     
143. int *div_int(int a[], int b)
     
144. {
     
145.     /* 计算 a / b（b 不为高精度数） */
     
146.     int *r = (int *)malloc(digit + 1), k = a[0], i, d = 0;
     
147.     memset(r, 0, sizeof(r));
     
148.     for (i = k; i >= 0; i--)
     
149.     {
     
150.         d = d * 10 + a[i];
     
151.         if (!d)
     
152.             continue;
     
153.         r[i] = d / b;
     
154.         d %= b;
     
155.     }
     
156.     while (!r[k] && k)
     
157.         k--;
     
158.     r[0] = k;
     
159.     return r;
     
160. }

复制代码