大整数的存储与高精度运算

798236606

1. #include<cstdio>
   
2. #include<cstring>
   
3. 
   
4. typedef struct BIGN{                                         //定义大整数类型
   
5.     int num[1000];                                        //从低位到高位存储大整数
   
6.     int len;
   
7.     bool is_neg;
   
8.    
   
9.     BIGN()                                                        //初始化构造函数                                       
   
10.     {
    
11.         memset(num, 0, sizeof(num));
    
12.         len = 0;
    
13.         is_neg = false;
    
14.     };
    
15. }bign;
    
16. 
    
17. bign str2bign(char *s)                                        //字符串转大整数
    
18. {
    
19.     bign a;
    
20.    
    
21.     a.len = strlen(s);
    
22.    
    
23.     if (s[0] == '-')
    
24.     {
    
25.         a.is_neg = true;
    
26.         a.len--;
    
27.         s++;
    
28.     }
    
29.    
    
30.     for (int i = 0; i < a.len; i++)
    
31.         a.num[i] = s[a.len - 1 - i] - '0';
    
32.         
    
33.     return a;
    
34. }
    
35. 
    
36. void print_bign(bign a)                                //打印大整数
    
37. {
    
38.     if (a.is_neg)
    
39.         putchar('-');
    
40.         
    
41.     for (int i = a.len - 1; i >= 0; i--)
    
42.         printf("%d", a.num[i]);
    
43. }
    
44. 
    
45. int u_campare(bign a, bign b)                        //无符号比较大小,a > b则返回1，a < b返回-1，a == b返回0
    
46. {   
    
47.     if (a.len > b.len)
    
48.         return 1;
    
49.         
    
50.     if (a.len < b.len)
    
51.         return -1;
    
52.         
    
53.     for (int i = a.len - 1; i >= 0; i--)
    
54.     {
    
55.         if (a.num[i] > b.num[i])
    
56.             return 1;
    
57.         
    
58.         if (a.num[i] < b.num[i])
    
59.             return -1;
    
60.     }
    
61.    
    
62.     return 0;
    
63. }
    
64. 
    
65. int campare(bign a, bign b)                                //有符号比较大小
    
66. {
    
67. 
    
68.     if (a.is_neg == b.is_neg)
    
69.         return a.is_neg ? -u_campare(a, b) : u_campare(a, b);
    
70.     else
    
71.         return a.is_neg ? -1 : 1;
    
72. }
    
73. 
    
74. bign u_add(bign a, bign b)                                //无符号加
    
75. {
    
76.     bign c;
    
77.     int carry = 0;
    
78.    
    
79.     for (int i = 0; i < a.len || i < b.len; i++)
    
80.     {
    
81.         int temp = a.num[i] + b.num[i] + carry;
    
82.         
    
83.         c.num[c.len++] = temp % 10;
    
84.         carry = temp / 10;
    
85.     }
    
86.    
    
87.     if (carry)
    
88.         c.num[c.len++] = carry;
    
89. 
    
90.     return c;
    
91. }
    
92. 
    
93. bign u_sub(bign a, bign b)                                //无符号减
    
94. {
    
95.     bign c;
    
96.    
    
97.     if (u_campare(a, b) < 0)
    
98.     {
    
99.         bign temp = a;
    
100.         
     
101.         a = b;
     
102.         b = temp;
     
103.         c.is_neg = true;
     
104.     }
     
105.    
     
106.     for (int i = 0; i < a.len || i < b.len; i++)
     
107.     {
     
108.         if (a.num[i] < b.num[i])
     
109.         {
     
110.             a.num[i + 1]--;
     
111.             a.num[i] += 10;
     
112.         }
     
113.         
     
114.         c.num[c.len++] = a.num[i] - b.num[i];
     
115.     }
     
116.    
     
117.     while (c.len > 1 && !c.num[c.len - 1])
     
118.         c.len--;
     
119. 
     
120.     return c;
     
121. }
     
122. 
     
123. bign muti(bign a, int b)                                //有符号乘（大整数乘整形）
     
124. {
     
125.     bign c;
     
126.     int carry = 0;
     
127.    
     
128.     if (!b)
     
129.     {
     
130.         c.len++;
     
131.         c.is_neg = a.is_neg;
     
132.         
     
133.         return c;
     
134.     }
     
135.    
     
136.     if (a.is_neg + (b < 0) == 1)
     
137.         c.is_neg = true;
     
138.         
     
139.     if (b < 0)
     
140.         b = -b;
     
141.         
     
142.     for (int i = 0; i < a.len; i++)
     
143.     {
     
144.         int temp = a.num[i] * b + carry;
     
145.         
     
146.         c.num[c.len++] = temp % 10;
     
147.         carry = temp / 10;
     
148.     }
     
149. 
     
150.     while (carry)
     
151.     {
     
152.         c.num[c.len++] = carry % 10;
     
153.         carry /= 10;
     
154.     }   
     
155. 
     
156.     return c;
     
157. }
     
158. 
     
159. bign divi(bign a, int b)                                        //有符号除（大整数除整形）
     
160. {
     
161.     bign c;
     
162.     int r = 0;
     
163.    
     
164.     if (!b)
     
165.     {
     
166.         puts("0 can not be divisor!!");
     
167.         
     
168.         return c;
     
169.     }
     
170.    
     
171.     if (a.is_neg + (b < 0) == 1)
     
172.         c.is_neg = true;
     
173.         
     
174.     if (b < 0)
     
175.         b = -b;
     
176.    
     
177.     c.len = a.len;   
     
178.     for (int i = a.len - 1; i >= 0; i--)
     
179.     {
     
180.         r = r * 10 + a.num[i];
     
181.         c.num[i] = r / b;
     
182.         r = r % b;
     
183.     }
     
184.    
     
185.     while (c.len > 1 && !c.num[c.len - 1])
     
186.         c.len--;
     
187. 
     
188.     return c;
     
189. }
     
190. 
     
191. bign add(bign a, bign b)                                //有符号加
     
192. {
     
193.     bign c;
     
194.    
     
195.     if (a.is_neg == b.is_neg)
     
196.     {
     
197.         c = u_add(a, b);
     
198.         
     
199.         if (a.is_neg)
     
200.             c.is_neg = true;        
     
201.     }
     
202.     else
     
203.         c = a.is_neg ? u_sub(b, a) : u_sub(a, b);
     
204. 
     
205.     return c;
     
206. }
     
207. 
     
208. bign sub(bign a, bign b)                                //有符号减
     
209. {
     
210.     bign c;
     
211.    
     
212.     if (a.is_neg != b.is_neg)
     
213.     {
     
214.         c = u_add(a, b);
     
215.         
     
216.         if (a.is_neg)
     
217.             c.is_neg = true;        
     
218.     }
     
219.     else
     
220.         c = a.is_neg ? u_sub(b, a) : u_sub(a, b);
     
221. 
     
222.     return c;
     
223. }
     
224. 
     
225. int main(void)
     
226. {
     
227.     char s1[100] = "-123";
     
228.     char s2[100] = "23";
     
229.     bign a = str2bign(s1), b = str2bign(s2);
     
230.    
     
231.     print_bign(divi(a, 12));
     
232.    
     
233.     return 0;
     
234. }
     

复制代码

相关题目：

PTA B_1017 A除以B
https://fishc.com.cn/thread-154914-1-1.html

PTA A_1023 Have Fun with Numbers
https://fishc.com.cn/thread-154917-1-1.html

PTA A_1024 Palindromic Number
https://fishc.com.cn/thread-154921-1-1.html