[复习]高精度算法

今天又复习了一下高精度（高精度减、加、乘）

仍然用结构体来存储

数据结构：

typedef struct HP{

int w[10001] //储存数据，0下标储存有多少位

}HP；

注意：高精度为了进位需要反着存储

例如：原数 a 123 -int

高精度数 b 3 |2|1 –int[]

加法

先将最大的位数+1，然后按位相加，每次加完进位，最后删除前导0

减法

和高精度加法类似，相当于就是加上一个负数，只是需要借位

在之前需要预处理一下，一定保证用大数减小数

乘法

虽然复习的是高精度乘单精度，但是我还是觉得直接用高精度乘比较简单

例如下面这个竖式：

1 2 3

× 1 2

-------------------------

2 4 6

1 2 3

------------------------

1 4 7 6

我们可以发现当HP a与HP b相乘时，a[i]*b[j]得到的是（i + j - 1）位上的数

下面附上源代码：

  1 /*
  2 
  3  * [输入文件] hp.in
  4 
  5  * 共三行
  6 
  7  * 第一行和第二行是两个高精度数
  8 
  9  * 第三行是一个符号（+ -或*）
 10 
 11  * [输出文件] hp.out
 12 
 13  * 仅一行，运算的结果
 14 
 15  */
 16 
 17 #include<iostream>
 18 
 19 #include<string>
 20 
 21 #include<cstring>
 22 
 23 #include<cstdio>
 24 
 25 using namespace std;
 26 
 27 FILE *fp;
 28 
 29 #ifndef _HPDEF_H_
 30 
 31 #define _HPDEF_H_
 32 
 33 typedef int HPI;
 34 
 35 //高精度类
 36 
 37 typedef struct
 38 
 39 {
 40 
 41       int w[10005];    
 42 
 43 }HP;
 44 
 45 #endif
 46 
 47 #ifndef _HP_H_
 48 
 49 #define _HP_H_
 50 
 51 //带成员函数的hp类
 52 
 53 class hp{
 54 
 55       public:
 56 
 57       static HP hps(string str);
 58 
 59       static HP add(HP *p1,HP *p2);
 60 
 61       static HPI cmp(HP *p1,HP *p2);
 62 
 63       static HP rem(HP *p1,HP *p2);
 64 
 65       static void fout(HP *p);
 66 
 67       static HP chen(HP *p1,HP *p2);
 68 
 69 }hp;
 70 
 71 /**
 72 
 73  * 将字符串转化成高精度数
 74 
 75  * @param str 要转化的字符串
 76 
 77  * @return 转化后的高精度数
 78 
 79  */
 80 
 81 HP hp::hps(string str)
 82 
 83 {
 84 
 85       HP h;
 86 
 87       memset(h.w,0,sizeof(h.w));
 88 
 89       h.w[0]=str.size();
 90 
 91       for(int i=h.w[0];i>=1;i--){
 92 
 93            h.w[i]=str[(h.w[0]-i)]-'0';
 94 
 95       }
 96 
 97       return h;
 98 
 99 }
100 
101 /**
102 
103  * 将两个高精度数相加
104 
105  * @param p1 第一个高精度数的地址
106 
107  * @param p2 第二个高精度数的地址
108 
109  * @return 计算的结果
110 
111  */
112 
113 HP hp::add(HP *p1,HP *p2)
114 
115 {
116 
117       HP p;
118 
119       memset(p.w,0,sizeof(p.w));
120 
121       if(p1->w[0]>p2->w[0]) p.w[0]=p1->w[0];
122 
123       else p.w[0]=p2->w[0];
124 
125       for(int i=1;i<=p.w[0];i++){
126 
127            p.w[i]+=p1->w[i]+p2->w[i];
128 
129            p.w[i+1]+=p.w[i]/10;
130 
131            p.w[i]%=10;
132 
133       }
134 
135       p.w[0]+=2;
136 
137       while(p.w[0]>1&&p.w[p.w[0]]==0) p.w[0]--;
138 
139       return p;
140 
141 }
142 
143 /**
144 
145  * 比较两个高精度数的大小
146 
147  * @param p1 第一个高精度数的地址
148 
149  * @param p2 第二个高精度数的地址
150 
151  * @return 当*p1大于*p2时，返回1，<br>
152 
153  *           当*p1小于*p2时，返回-1，<br>
154 
155  *         否则返回0
156 
157  */ 
158 
159 HPI hp::cmp(HP *p1,HP *p2){
160 
161       if(p1->w[0]>p2->w[0]) return 1;
162 
163       else if(p1->w[0]<p2->w[0]) return -1;
164 
165       for(int i=p1->w[0];i>=1;i--){
166 
167            if(p1->w[i]>p2->w[i])
168 
169                  return 1;
170 
171            else if(p1->w[i]<p2->w[i])
172 
173                  return -1;
174 
175       }
176 
177       return 0;
178 
179 }
180 
181 /**
182 
183  * 将高精度数输出到文件流fp中
184 
185  * @param p 要输出的高精度数的地址
186 
187  */
188 
189 void hp::fout(HP *p){
190 
191       for(int i=p->w[0];i>=1;i--)
192 
193       fprintf(fp,"%d",p->w[i]);
194 
195 }
196 
197 /**
198 
199  * 将两个高精度数相减
200 
201  * @param p1 被减高精度数的地址
202 
203  * @param p2 减高精度数的地址
204 
205  * @return 计算的结果
206 
207  */
208 
209 HP hp::rem(HP *p1,HP *p2){
210 
211       HP p;
212 
213       memset(p.w,0,sizeof(p.w));
214 
215       p.w[0]=p1->w[0];
216 
217       for(int i=1;i<=p.w[0];i++){
218 
219            if(p1->w[i]<p2->w[i]){
220 
221                  p1->w[i]+=10;
222 
223                  p1->w[i+1]--;
224 
225            }
226 
227            p.w[i]=p1->w[i]-p2->w[i];
228 
229       }
230 
231       while(p.w[0]>1&&p.w[p.w[0]]==0) p.w[0]--;
232 
233       return p;
234 
235 }
236 
237 /**
238 
239  * 将两个高精度数相乘
240 
241  * @param p1 第一个高精度数的地址
242 
243  * @param p2 第二个高精度数的地址
244 
245  * @return 计算的结果
246 
247  */
248 
249 HP hp::chen(HP *p1,HP *p2){
250 
251       HP p;
252 
253       memset(p.w,0,sizeof(p.w));
254 
255       p.w[0]=p1->w[0]+p2->w[0];
256 
257       for(int i=1;i<=p1->w[0];i++){
258 
259            for(int j=1;j<=p2->w[0];j++){
260 
261                  p.w[i+j-1]+=p1->w[i]*p2->w[j];
262 
263                  p.w[i+j]+=p.w[i+j-1]/10;
264 
265                  p.w[i+j-1]%=10;
266 
267            }
268 
269       }
270 
271       p.w[0]+=2;
272 
273       while(p.w[0]>1&&p.w[p.w[0]]==0) p.w[0]--;
274 
275       return p;
276 
277 }
278 
279 #endif
280 
281 int main(int argc,char* argv[])
282 
283 {
284 
285       freopen("gjc1.in","r",stdin);
286 
287       fp=fopen("gjc1.out","w");
288 
289       //局部变量定义
290 
291       string str1,str2;
292 
293       HP hp1,hp2,hp3;
294 
295       char fu;
296 
297       cin>>str1>>str2>>fu;
298 
299       //转化字符串
300 
301       hp1=hp::hps(str1);
302 
303       hp2=hp::hps(str2);
304 
305       fu = '*';
306 
307       //计算
308 
309       switch(fu){
310 
311            case '+':
312 
313                  hp3=hp::add(&hp1,&hp2);
314 
315                  break;
316 
317            case '-':
318 
319                  switch(hp::cmp(&hp1,&hp2)){
320 
321                       case 1:
322 
323                             hp3=hp::rem(&hp1,&hp2);
324 
325                             break;
326 
327                       case 0:
328 
329                             fprintf(fp,"0");
330 
331                             return 0;
332 
333                       case -1:
334 
335                             hp3=hp::rem(&hp2,&hp1);
336 
337                             fprintf(fp,"-");
338 
339                             break;
340 
341                  }
342 
343                  break;
344 
345             case '*':
346 
347                  hp3=hp::chen(&hp1,&hp2);
348 
349                  break;
350 
351       }
352 
353       hp::fout(&hp3);
354 
355       return 0;
356 
357 }