欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

hdu Exponentiation高精度实数乘幂(用了带小数的高精度模板)

程序员文章站 2022-04-08 21:30:26
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 }