hdu Exponentiation高精度实数乘幂（用了带小数…
2019-03-12 08:20:54来源：博客园 阅读 ()
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 }
原文链接:https://www.cnblogs.com/whk19981229/p/10512930.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- HDU-2955-Robberies（0-1背包） 2020-03-30
- 用C++实现：高精度加法 2020-03-18
- 用C++实现：高精度阶乘 2020-03-18
- hdu1455 拼木棍（经典dfs） 2020-02-29
- anniversary party_hdu1520 2020-02-16
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签