hdu Exponentiation高精度实数乘幂（用了带小数的高精度模板）
程序员文章站
2022-07-05 15:40:01
1 #include 2 #include 3 #include 4 #include 5 #include 6 #define INT_BIT_MAX 100 7 #define FLOAT_BIT_MAX 100 8 9 class CWTNumber 10 { 11 private: 12 i... ......
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <cmath>
5 #include <cstdlib>
6 #define int_bit_max 100
7 #define float_bit_max 100
8
9 class cwtnumber
10 {
11 private:
12 int intbits; /* 整数数位*/
13 int floatbits; /* 小数有效数位*/
14 char infinite; /* 无穷大*/
15 char sign; /* 符号*/
16 char intpart[int_bit_max]; /* 整数部分*/
17 char floatpart[float_bit_max]; /* 小数部分*/
18 private:
19 char *m_sz;
20
21 public:
22 /* 算术函数指针类型.*/
23 typedef void (*pfncalc)(const cwtnumber &, const cwtnumber &, cwtnumber &);
24 cwtnumber();
25 cwtnumber(const char *sznum);
26 ~cwtnumber();
27 /* 转换成字符串*/
28 char *tostring();
29 void freestring();
30 /* 初始化wtnumber为0.*/
31 void initwtnumbertozero();
32 /* 判断需要多少个字符空间存储wtnumber转换的字符串.*/
33 int strlenbywtnumber();
34 /* 从字符串转换到wtnumber.*/
35 void strtowtnumber(const char *arr);
36 /* 从wtnumber转换到字符串.*/
37 void wtnumbertostr(char *szbuf);
38 /* 调节数位,删除最高整数位是0的和最低小数位是0的数位.*/
39 void adjustbits();
40 /* 移动小数点,delta=0不移动,delta<0往左移动,delta>0往右移动.*/
41 void movefloatpoint(int delta);
42 /* 使无穷大 */
43 void makeinfinite();
44 /* 比较2个数大小 */
45 int wtcompare(const cwtnumber &n) const;
46 /* 判断是否为0 */
47 int iszero() const;
48 /* 赋值号重载*/
49 cwtnumber &operator=(const cwtnumber &n);
50
51 /* 运算符重载 */
52 cwtnumber operator+(const cwtnumber &n);
53 cwtnumber operator-(const cwtnumber &n);
54 cwtnumber operator*(const cwtnumber &n);
55 cwtnumber operator/(const cwtnumber &n);
56 cwtnumber &operator+=(const cwtnumber &n);
57 cwtnumber &operator-=(const cwtnumber &n);
58 cwtnumber &operator*=(const cwtnumber &n);
59 cwtnumber &operator/=(const cwtnumber &n);
60
61 bool operator>(const cwtnumber &n);
62 bool operator>=(const cwtnumber &n);
63 bool operator<(const cwtnumber &n);
64 bool operator<=(const cwtnumber &n);
65 bool operator==(const cwtnumber &n);
66 bool operator!=(const cwtnumber &n);
67 /* 加法*/
68 static void wtadd(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res);
69 /* 乘法*/
70 static void wtmultiply(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res);
71 /* 减法*/
72 static void wtsubtract(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res);
73 /* 除法*/
74 static void wtdivide(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res);
75 /* 根据算术函数返回结果 */
76 static char *result(const char *val1, const char *val2, pfncalc pfncalc);
77 };
78
79 cwtnumber::cwtnumber()
80 {
81 initwtnumbertozero();
82 }
83 cwtnumber::cwtnumber(const char *sznum)
84 {
85 initwtnumbertozero();
86 strtowtnumber(sznum);
87 }
88 cwtnumber::~cwtnumber()
89 {
90 freestring();
91 }
92 void cwtnumber::freestring()
93 {
94 if (m_sz)
95 delete[] m_sz;
96 m_sz = null;
97 }
98 void cwtnumber::initwtnumbertozero()
99 {
100 memset(this, 0, sizeof(cwtnumber));
101 }
102 int cwtnumber::strlenbywtnumber()
103 {
104 int len = floatbits + intbits + 1;
105 if (intbits == 0)
106 len++; /* .1 --> 0.1*/
107 if (floatbits)
108 len++; /* '.'*/
109 if (sign)
110 len++; /* '-'*/
111 if (infinite)
112 return 11; /* #infinite */
113 return len;
114 }
115 void cwtnumber::strtowtnumber(const char *arr)
116 {
117 char *point;
118 initwtnumbertozero();
119 if (*arr == '-') /* 如果是负数*/
120 {
121 arr++;
122 sign = 1;
123 }
124 point = strchr(arr, '.');
125 if (point) /* 找到小数点 */
126 {
127 int n = intbits = point - arr; /* 计算出整数数位 */
128 while (n) /* 整数数位不==0则循环 */
129 {
130 intpart[intbits - n] = arr[n - 1] - '0'; /* 将数字低位存在低下标元素*/
131 n--;
132 }
133 while (*++point)
134 {
135 floatpart[floatbits] = *point - '0';
136 floatbits++;
137 }
138 }
139 else /* 说明没写小数点,全是整数.*/
140 {
141 int n = intbits = strlen(arr);
142 while (n)
143 {
144 intpart[intbits - n] = arr[n - 1] - '0';
145 n--;
146 }
147 }
148 adjustbits();
149 /* 处理-0 和0的情况*/
150 if (floatbits == 0)
151 {
152 if (intbits == 0 || intbits == 1 && intpart[0] == 0)
153 sign = 0;
154 }
155 }
156
157 void cwtnumber::wtnumbertostr(char *szbuf)
158 {
159 int n = intbits, c;
160 memset(szbuf, 0, strlenbywtnumber());
161 if (sign) /* 如果是负数*/
162 {
163 *szbuf++ = '-';
164 }
165 if (infinite)
166 {
167 strcat(szbuf, "#infinite");
168 return;
169 }
170 while (n)
171 {
172 szbuf[intbits - n] = intpart[n - 1] + '0';
173 n--;
174 }
175 c = 0; /* 是否加了0*/
176 if (intbits == 0)
177 {
178 strcat(szbuf, "0");
179 c = 1;
180 }
181 if (floatbits)
182 strcat(szbuf, ".");
183 n = 0;
184 while (n < floatbits)
185 {
186 szbuf[intbits + 1 + n + c] = floatpart[n] + '0';
187 n++;
188 }
189 }
190 void cwtnumber::adjustbits()
191 {
192 while (intbits > 1 && intpart[intbits - 1] == 0)
193 intbits--;
194 while (floatbits && floatpart[floatbits - 1] == 0)
195 floatbits--;
196 }
197 void cwtnumber::movefloatpoint(int delta)
198 {
199 /* delta<0则往左移动小数点,delta>0则向右移动小数点 */
200 if (delta)
201 {
202 cwtnumber n = *this;
203 initwtnumbertozero();
204 sign = n.sign;
205 if (delta < 0)
206 {
207 int i;
208 delta = -delta;
209 for (i = delta; i < n.intbits; i++)
210 {
211 intpart[intbits++] = n.intpart[i];
212 }
213 for (i = delta - 1; i >= 0; i--)
214 {
215 floatpart[floatbits++] = n.intpart[i];
216 }
217 for (i = 0; i < n.floatbits; i++)
218 {
219 floatpart[floatbits++] = n.floatpart[i];
220 }
221 }
222 else
223 {
224 int i;
225 for (i = delta; i < n.floatbits; i++) /* 处理小数部分*/
226 {
227 floatpart[floatbits++] = n.floatpart[i];
228 }
229 for (i = delta - 1; i >= 0; i--) /* 小数到整数的部分*/
230 {
231 intpart[intbits++] = n.floatpart[i];
232 }
233 for (i = 0; i < n.intbits; i++) /* 整数部分*/
234 {
235 intpart[intbits++] = n.intpart[i];
236 }
237 }
238 }
239 adjustbits();
240 }
241 void cwtnumber::makeinfinite()
242 {
243 infinite = 1;
244 }
245
246 int cwtnumber::wtcompare(const cwtnumber &n) const
247 {
248 /* 首先是比较符号*/
249 if (sign == 0 && n.sign != 0) /* pn1是正数,pn2是负数*/
250 return 1; /* >*/
251 else if (sign != 0 && n.sign == 0) /* pn1是负数,pn2是正数*/
252 return -1; /* <*/
253 else /* 同号状态*/
254 {
255 /* 比较整数部分*/
256 if (intbits > n.intbits) /* pn1整数数位多*/
257 return sign ? -1 : 1;
258 else if (intbits < n.intbits)
259 return sign ? 1 : -1;
260 else /* 整数数位相同*/
261 {
262 int i = intbits - 1; /*指到最高位*/
263 while (i >= 0)
264 {
265 if (intpart[i] > n.intpart[i])
266 return sign ? -1 : 1;
267 else if (intpart[i] < n.intpart[i])
268 return sign ? 1 : -1;
269 else
270 i--;
271 }
272 /* 整数部分相同,比较小数部分*/
273 for (i = 0; i < floatbits && i < n.floatbits;)
274 {
275 if (floatpart[i] > n.floatpart[i])
276 return sign ? -1 : 1;
277 else if (floatpart[i] < n.floatpart[i])
278 return sign ? 1 : -1;
279 else
280 i++;
281 }
282 if (i < floatbits)
283 return sign ? -1 : 1;
284 if (i < n.floatbits)
285 return sign ? 1 : -1;
286 return 0; /* 相等*/
287 }
288 }
289 }
290 int cwtnumber::iszero() const
291 {
292 if (floatbits == 0 && intbits == 0)
293 return 1;
294 if (floatbits == 0 && intbits == 1 && intpart[0] == 0)
295 return 1;
296 return 0;
297 }
298
299 void cwtnumber::wtadd(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res)
300 {
301 res.initwtnumbertozero();
302 if (n1.sign ^ n2.sign) /*异号*/
303 {
304 cwtnumber rn2 = n2;
305 rn2.sign = n1.sign;
306 wtsubtract(n1, rn2, res);
307 }
308 else /*同号*/
309 {
310 int maxfloatbits = n1.floatbits > n2.floatbits ? n1.floatbits : n2.floatbits;
311 int addbit = 0; /* 进位值*/
312 int i, j;
313 for (i = maxfloatbits - 1; i >= 0; i--)
314 {
315 int value = n1.floatpart[i] + n2.floatpart[i] + addbit;
316 addbit = value / 10; /* 看看是否超过10. 设置进位值*/
317 res.floatpart[i] = value % 10;
318 }
319 res.floatbits = maxfloatbits;
320 /* 到此,小数部分计算完毕.*/
321 for (j = 0; j < n1.intbits || j < n2.intbits; j++)
322 {
323 int value = n1.intpart[j] + n2.intpart[j] + addbit;
324 addbit = value / 10;
325 res.intpart[j] = value % 10;
326 res.intbits++;
327 }
328 if (addbit > 0)
329 {
330 res.intpart[j] = addbit;
331 res.intbits++;
332 }
333 res.sign = n1.sign; /*决定符号*/
334 res.adjustbits();
335 }
336 }
337
338 void cwtnumber::wtmultiply(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res)
339 {
340 cwtnumber z1 = n1, z2 = n2;
341 cwtnumber sum;
342 int i, j;
343 sum.initwtnumbertozero();
344 res.initwtnumbertozero();
345 z1.movefloatpoint(z1.floatbits);
346 z2.movefloatpoint(z2.floatbits);
347 /* 计算z1*z2 */
348 for (i = 0; i < z2.intbits; i++)
349 {
350 cwtnumber tmp; /* 存放临时乘积*/
351 int addbit = 0;
352 tmp.intbits = z1.intbits + i;
353 for (j = 0; j < z1.intbits; j++)
354 {
355 int value = z2.intpart[i] * z1.intpart[j] + addbit;
356 addbit = value / 10;
357 tmp.intpart[j + i] = value % 10;
358 }
359 if (addbit)
360 {
361 tmp.intpart[j + i] = addbit;
362 tmp.intbits++;
363 }
364 wtadd(sum, tmp, res);
365 sum = res;
366 }
367 res = sum;
368 res.movefloatpoint(-(n1.floatbits + n2.floatbits));
369 /* 判断符号,异号为负*/
370 if (n1.sign ^ n2.sign)
371 res.sign = 1;
372 }
373
374 void cwtnumber::wtsubtract(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res)
375 {
376 res.initwtnumbertozero();
377 if (n1.sign ^ n2.sign) /* 异号情况*/
378 {
379 cwtnumber rn2 = n2;
380 rn2.sign = n1.sign;
381 wtadd(n1, rn2, res);
382 }
383 else /* 同号情况*/
384 {
385 int cmp = n1.wtcompare(n2);
386 int swapflag, i, maxfloatbits, subtractbit;
387 if (cmp == 0)
388 return; /* 相等就没必要再减了.*/
389 swapflag = n1.sign == 0 ? cmp == -1 : cmp == 1;
390 const cwtnumber *pn1 = &n1;
391 const cwtnumber *pn2 = &n2;
392 if (swapflag)
393 {
394 const cwtnumber *t = pn1;
395 pn1 = pn2;
396 pn2 = t;
397 }
398 maxfloatbits = pn1->floatbits > pn2->floatbits ? pn1->floatbits : pn2->floatbits;
399 subtractbit = 0; /* 退位值*/
400 /* 先计算小数部分*/
401 for (i = maxfloatbits - 1; i >= 0; i--)
402 {
403 if (pn1->floatpart[i] - subtractbit < pn2->floatpart[i])
404 {
405 int value = pn1->floatpart[i] - pn2->floatpart[i] - subtractbit + 10;
406 subtractbit = 1;
407 res.floatpart[i] = value;
408 }
409 else
410 {
411 int value = pn1->floatpart[i] - pn2->floatpart[i] - subtractbit;
412 subtractbit = 0;
413 res.floatpart[i] = value;
414 }
415 }
416 res.floatbits = maxfloatbits;
417 /* 至此小数部分计算完毕.*/
418 for (i = 0; i < pn1->intbits || i < pn2->intbits; i++)
419 {
420 if (pn1->intpart[i] - subtractbit < pn2->intpart[i])
421 {
422 int value = pn1->intpart[i] - pn2->intpart[i] - subtractbit + 10;
423 subtractbit = 1;
424 res.intpart[i] = value;
425 }
426 else
427 {
428 int value = pn1->intpart[i] - pn2->intpart[i] - subtractbit;
429 subtractbit = 0;
430 res.intpart[i] = value;
431 }
432 res.intbits++;
433 }
434 res.sign = swapflag ? !n1.sign : n1.sign; /*决定符号*/
435 res.adjustbits();
436 }
437 }
438 void cwtnumber::wtdivide(const cwtnumber &n1, const cwtnumber &n2, cwtnumber &res)
439 {
440 cwtnumber z1 = n1, z2 = n2;
441 int deta = z2.floatbits - z1.floatbits;
442 z1.movefloatpoint(z1.floatbits);
443 z2.movefloatpoint(z2.floatbits);
444 res.initwtnumbertozero();
445 if (n1.iszero())
446 return;
447 if (n2.iszero())
448 {
449 res.sign = n1.sign;
450 res.makeinfinite();
451 return;
452 }
453 z1.sign = z2.sign = 0; /*统一符号,便于比较大小*/
454 while (z1.intbits != z2.intbits)
455 { /*确保数位相等,这步耗费很多时间*/
456 if (z1.intbits < z2.intbits)
457 {
458 z1.movefloatpoint(1);
459 deta--;
460 }
461 else
462 {
463 z2.movefloatpoint(1);
464 deta++;
465 }
466 }
467 while (res.floatbits < (int_bit_max / 2))
468 {
469 int cmp = z1.wtcompare(z2);
470 int n = 10;
471 cwtnumber mulres, subres;
472 if (cmp == -1)
473 { /*z1<z2*/
474 z1.movefloatpoint(1);
475 res.floatpart[res.floatbits++] = 0;
476 continue;
477 }
478 else if (cmp == 0)
479 { /*z1==z2*/
480 res.floatpart[res.floatbits++] = 1;
481 break;
482 }
483 do
484 { /*找商*/
485 cwtnumber tmp;
486 tmp.intpart[0] = --n;
487 tmp.intbits = 1;
488 wtmultiply(z2, tmp, mulres);
489 } while ((cmp = mulres.wtcompare(z1)) == 1);
490 res.floatpart[res.floatbits++] = n;
491 if (cmp == 0)
492 break;
493 wtsubtract(z1, mulres, subres);
494 subres.movefloatpoint(1);
495 z1 = subres;
496 }
497 res.movefloatpoint(1);
498 res.movefloatpoint(deta);
499 /* 判断符号,异号为负*/
500 if (n1.sign ^ n2.sign)
501 res.sign = 1;
502 }
503 char *cwtnumber::result(const char *val1, const char *val2, pfncalc pfncalc)
504 {
505 cwtnumber n1, n2, res;
506 n1.strtowtnumber(val1);
507 n2.strtowtnumber(val2);
508 pfncalc(n1, n2, res);
509 return res.tostring();
510 }
511
512 char *cwtnumber::tostring()
513 {
514 freestring();
515 m_sz = new char[strlenbywtnumber()];
516 wtnumbertostr(m_sz);
517 return m_sz;
518 }
519
520 cwtnumber &cwtnumber::operator=(const cwtnumber &n)
521 {
522 if (this != &n)
523 {
524 freestring();
525 memcpy(this, &n, sizeof(cwtnumber));
526 if (n.m_sz)
527 {
528 m_sz = strdup(n.m_sz);
529 }
530 }
531 return *this;
532 }
533
534 cwtnumber cwtnumber::operator+(const cwtnumber &n)
535 {
536 cwtnumber res;
537 cwtnumber::wtadd(*this, n, res);
538 return res;
539 }
540 cwtnumber cwtnumber::operator-(const cwtnumber &n)
541 {
542 cwtnumber res;
543 cwtnumber::wtsubtract(*this, n, res);
544 return res;
545 }
546 cwtnumber cwtnumber::operator*(const cwtnumber &n)
547 {
548 cwtnumber res;
549 cwtnumber::wtmultiply(*this, n, res);
550 return res;
551 }
552 cwtnumber cwtnumber::operator/(const cwtnumber &n)
553 {
554 cwtnumber res;
555 cwtnumber::wtdivide(*this, n, res);
556 return res;
557 }
558 cwtnumber &cwtnumber::operator+=(const cwtnumber &n)
559 {
560 cwtnumber n1 = *this, n2 = n;
561 cwtnumber::wtadd(n1, n2, *this);
562 return *this;
563 }
564 cwtnumber &cwtnumber::operator-=(const cwtnumber &n)
565 {
566 cwtnumber n1 = *this, n2 = n;
567 cwtnumber::wtsubtract(n1, n2, *this);
568 return *this;
569 }
570 cwtnumber &cwtnumber::operator*=(const cwtnumber &n)
571 {
572 cwtnumber n1 = *this, n2 = n;
573 cwtnumber::wtmultiply(n1, n2, *this);
574 return *this;
575 }
576 cwtnumber &cwtnumber::operator/=(const cwtnumber &n)
577 {
578 cwtnumber n1 = *this, n2 = n;
579 cwtnumber::wtdivide(n1, n2, *this);
580 return *this;
581 }
582 bool cwtnumber::operator>(const cwtnumber &n)
583 {
584 return wtcompare(n) == 1;
585 }
586 bool cwtnumber::operator>=(const cwtnumber &n)
587 {
588 return wtcompare(n) != -1;
589 }
590 bool cwtnumber::operator<(const cwtnumber &n)
591 {
592 return wtcompare(n) == -1;
593 }
594 bool cwtnumber::operator<=(const cwtnumber &n)
595 {
596 return wtcompare(n) != 1;
597 }
598 bool cwtnumber::operator==(const cwtnumber &n)
599 {
600 return wtcompare(n) == 0;
601 }
602 bool cwtnumber::operator!=(const cwtnumber &n)
603 {
604 return wtcompare(n) != 0;
605 }
606 char s[1000];
607 char ss[1000];
608 char ans[1000];
609 int n;
610 int main()
611 {
612 while (scanf("%s %d", s, &n) != eof)
613 {
614 cwtnumber x(s);
615 cwtnumber y("1");
616 for (int i = 0; i < n; i++)
617 {
618 y = y * x;
619 }
620 //printf("%s\n", y.tostring());
621 strcpy(ss, y.tostring());
622
623 if (ss[0] == '0')
624 {
625 printf("%s\n", ss + 1);
626 }
627 else
628 printf("%s\n", ss);
629 }
630 return 0;
631 }