【ACM】求高精度冪，acm高精度冪
題目來源：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)，其中n 是整數並且 0 < n <= 25。
Input
T輸入包括多組 R 和 n。 R 的值占第 1 到第 6 列，n 的值占第 8 和第 9 列。
Output
對於每組輸入，要求輸出一行，該行包含精確的 R 的 n 次方。輸出需要去掉前導的 0 後不要的 0
。如果輸出是整數，不要輸出小數點。
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
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 }
View Code
