首页 > > 程序设计 > C/C++ >

【ACM】求高精度幂

2018-06-17 23:44:19来源：未知阅读 ()

题目来源：http://poj.org/problem?id=1001&lang=zh-CN

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　求高精度幂

Time Limit: 500MS		Memory Limit: 10000K
Total Submissions: 160807		Accepted: 39157

Description

对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。

现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(Rⁿ)，其中n 是整数并且 0 < n <= 25。

Input

T输入包括多组 R 和 n。 R 的值占第 1 到第 6 列，n 的值占第 8 和第 9 列。

Output

对于每组输入，要求输出一行，该行包含精确的 R 的 n 次方。输出需要去掉前导的 0 后不要的 0 。如果输出是整数，不要输出小数点。

Sample Input

Sample Output

548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201



求解思路：
1、使用数组存储数据，保证数组的元素不大于9，不存储小数点，通过一个整型变量记录小数位的位数。用string接受输入流的数据，再转换成整型数组（不含“.”）,作为第一次乘法计算的一个因子，并生成一个整数作为另一个因子。
2、核心函数是 void multiplicationCompute(vector<int> &ivecA, unsigned int &pointPosA, const int &intR, const int &pointPosR)，计算数组存储的大整数与底数的乘积。
   为了方便计算，大整数存储在数组的高位— —低位。计算的时候，从数组低位— —高位开始遍历，每一位数组元素（非-1占位符）与底数相乘，并将结果依次存入数组。对于ivecA[index] 与底数的乘积，其个位存入index位，其更高位依次存入index--位。循环调用函数计算，其最终结果存储在ivecA中。
3、输出控制。整数不输出小数点；小数位后缀0不输出；纯小数不输出小数点前面的0；如果ivecA存储的实数位小于小数位，则需要在前面补0。


不过很惭愧的是下面的代码提交未能通过。在本机测试结果都正确，但是提交结果却是wrong answer，一时半会也没找到错误原因，待回头再来看吧。

  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 
  5 using namespace std;
  6 
  7 
  8 // Element == -1 ? reset 0 !
  9 inline void resetElement(int &ival)
 10 {
 11     if (ival == -1)
 12     {
 13         ival = 0;
 14     }
 15 }
 16 
 17 // Element > 10 ? deal element!
 18 inline void dealElement(vector<int> &ivec, vector<int>::size_type index)
 19 {
 20     while (ivec[index] >= 10)
 21     {
 22         int temp = ivec[index];
 23         ivec[index] %= 10;
 24         index--;
 25         resetElement(ivec[index]);
 26         ivec[index] += (temp / 10);
 27     }
 28 }
 29 
 30 // ivecR[index] * intR 
 31 void multiplicationCompute(vector<int> &ivecA, unsigned int &pointPosA, const int &intR, const int &pointPosR)
 32 {
 33     vector<int>::size_type currIndex = 0;
 34     unsigned int val = 0;
 35 
 36     for (vector<int>::size_type index = 0;  index != ivecA.size(); ++index)
 37     {
 38         if (ivecA[index] != -1)
 39         {
 40             currIndex = index;
 41             val = ivecA[index] * intR;
 42 
 43             ivecA[index] = 0;   //  +=
 44 
 45             while (val)
 46             {
 47                 resetElement(ivecA[currIndex]);
 48                 ivecA[currIndex] += (val % 10);
 49                 dealElement(ivecA, currIndex);
 50                 val /= 10;
 51                 currIndex--;
 52             }
 53         }        
 54     }
 55     pointPosA = pointPosA + pointPosR;
 56 }
 57 
 58 
 59 int main(int argc, char *argv[])
 60 {
 61 
 62     string strR;
 63     unsigned int n;
 64 
 65     while (cin >> strR >> n)
 66     {
 67         unsigned int intR = 0;
 68         vector<int> ivecR; 
 69         vector<int> ivecA(200, -1);
 70         unsigned int pointPositionR = 0;
 71         unsigned int pointPositionA = 0;
 72 
 73 
 74         //将R转换为int型的vector，pointPositionR记录小数点位置（其值代表小数位的位数）
 75         for (string::size_type index = 0; index != strR.size(); ++index)
 76         {
 77             if (strR[index] != '.')
 78             {
 79                 ivecR.push_back(strR[index] - '0');
 80             }
 81             else
 82             {
 83                 pointPositionR = strR.size() - 1 - index;
 84             }
 85         }
 86 
 87         //将ivecR转换成intR
 88         for (vector<int>::size_type index = 0; index != ivecR.size(); ++index)
 89         {
 90             intR = intR *10 + ivecR[index];
 91         }
 92 
 93         
 94         //将ivecR复制到ivecA，高位——低位存储，pointPositionA = pointPositionR
 95         for(int indexA = ivecA.size() - 1, indexR = ivecR.size() - 1; indexA >= 0 && indexR >= 0; --indexA, --indexR)
 96         {
 97             ivecA[indexA] = ivecR[indexR];
 98         }
 99         pointPositionA = pointPositionR;
100 
101         //if (n = 0)
102         //{
103         //    cout << 1 << endl;
104         //    return 0;
105         //}
106 
107         while (n >= 2)   //若 n = 1， 则 ivecA就是结果
108         {
109             multiplicationCompute(ivecA, pointPositionA, intR, pointPositionR);
110             n--;
111         }
112 
113 
114         //纯小数,小数位超过ivecA的实数位则补0
115         for (vector<int>::size_type index = ivecA.size() - 1; index >= ivecA.size() - pointPositionA; --index)
116         {
117             if (ivecA[index] == -1)
118             {
119                 ivecA[index] = 0;
120             }
121             
122         }
123 
124         //后缀0处理
125         for (int index = ivecA.size() - 1; index >= 0 && ivecA[index] == 0; --index)
126         {
127             ivecA[index] = -1;
128         }
129 
130 
131         vector<int>::size_type indexBegin = 0;
132         while (indexBegin != ivecA.size() && ivecA[indexBegin] == -1)
133         {
134             indexBegin++;
135         }
136 
137         if (indexBegin == ivecA.size())
138         {
139             cout << 0 << endl;
140         }
141         else
142         {
143             for(vector<int>::size_type index = indexBegin; index != ivecA.size(); ++index)
144             {
145                 if (ivecA[index] != -1)
146                 {
147                     if (index == ivecA.size() - pointPositionA)
148                     {
149                         cout << ".";
150                     }
151                     cout << ivecA[index];
152                 }
153             }
154             cout << endl;
155         }
156     }
157     return 0;
158 }