好久沒上帖了，現在把昨天一個晚上和今天一上午的努力寫出來，大家互相交流下。
題目的描述我就直接COPY了：
Exponentiation
Time Limit: 500MS Memory Limit: 10000K
Total Submissions: 121122 Accepted: 29574
Description
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.
Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.
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
覺得這道題目最難的地方就在於，沒有哪個數據類型可以容得下最後那幾十位的運算結果。這時候，你可能會脫口而出“用數組不就ok 了”。恩，這是一種很好的想法，可是當你用數組來容納最後的結果時，有沒有感覺那個結果是從何而來的了。一個95.123^12 該怎麼去算，才能得到結果了。
下面將我的想法說一下：
運算的過程我是在數組中進行，那麼如何在數組中進行計算了。大家小時候還沒計算器的時候都是用筆算兩數相乘的，即如果 35 * 35 是怎樣的一個運算過程了？
即一位的確定 = 兩數相乘的低位 + 低位來的進位
那麼我們在做兩個一位數相乘需要做的工作有：一、相乘+低位
二、向高位進位，如果沒有則進位為0
三、最後確定一位的結果為對十求余後的數
那麼我們就可以看看最後的代碼：
for(i = 0; i < n; i++)
{
for(f = 0, j = 0; j <= d || f > 0; j++ )
{
x = a[j] * b + f;
f = x / 10;
a[j] = x % 10;
}
while(a[j] == 0) j--; // 去除前導 的 0
d = j; // d 表示數組中已經被重置的個數
}
數組a[] 為存放最後結果，即35*35之後的1225. 而去除前導的零 是因為在運算前數組被初始化為0， 而用一個d 記錄數組中被重置的個數，其實就是最後所得結果的位數，像在35*35之中， 那麼d 就等於 4；
須的注明的是，在數組中進行運算的都是單位整型數據，即當輸入的數為浮點型時，要先將其一個一個將數字提取出來置入待運算的數組。
#include <iostream>
#include <string>
/*定義輸入的最大數范圍是10個*/
#define MAX 10
using std::cin;
using std::cout;
using std::endl;
/* 拿到小數的位數，例如1.234 那麼該函數返回的是3*/
int GetNumForDigit(char *str)
{
int i;
int flag = 0;
char *original = str;
int digit;
for(i=0; i < MAX; i++)
{
if(*str != '?')
str++;
else{
flag = i;
break;
}
}
/*因為在字符串中是以'\0'來結尾的，所以最後求得的位數比原始位大一位*/
flag--;
str = original;
for(i=0; i < MAX; i++)
{
if(*str != '.')
str++;
else{
digit = i;
break;
}
}
digit ++;
//begin
/* 這裡進行的運算是處理後置無效零的情況，例如1.0100 ， 2.4500000*/
int num = 0;
str = original;
while(*str != '?')
{
num++;
str++;
}
num--;
str = original;
int count = 0;
str += num;
str--;
for(int i=0; i<MAX; i++)
{
if(*str == '0')
{
count++;
}else{
break;
}
str--;
}//end
return flag-digit-count;
}
/*字符轉換數，例如1.23 則轉換成123, 特殊的當是1.0100 時 則轉換成101，去除後面的無效零*/
int CharTransformInt(char *str)
{
char *original = str;
int num = 0;
int result = 0;
char temp = NULL;
while(*str != '?')
{
num++;
str++;
}
num -= 2;
/*begin 去除後置無效零*/
str = original;
bool flag = false;
for(int i=0; i < MAX; i++)
{
if(*str == '.')
{
flag = true;
break;
}
str++;
}
str = original;
if(flag)
{
str += num;
for(int i=0; i<MAX; i++)
{
if(*str == '0')
{
num--;
}
else {
break;
}
str--;
}
}//end
int num_size = 1;
while(--num != 0)
{
num_size *= 10;
}
str = original;
for(int i = 0; i<MAX; i++)
{
if(*str != '.' && *str != '?')
{
temp = *str;
/*atoi函數需要注意它的參數是以何種方式結束的*/
result += atoi(&temp) * num_size;
num_size /= 10;
}
str++;
}
return result;
}
int main()
{
int digit = 0, digits = 0, i;
char str[MAX];
int n;
int a[1000];
for(i=0; i < MAX; i++)
{
str[i] = '?';
}
for(i = 0; i < 1000; i++) //將數組全部置 0
{
a[i] = 0;
}
while(cin>>str>>n)
{
digit = GetNumForDigit(str); /* 得到小數的位數 */
for(i = 0; i < n; i++) // digits 是得到相乘之後所有的小數位數
{
digits += digit;
}
int b = CharTransformInt(str);
int d = 0;
a[0] = 1;
int j,k,x,f;
/*將數置於數組中進行運算，算法思想就是筆算的兩數相乘的過程*/
for(i = 0; i < n; i++)
{
for(f = 0, j = 0; j <= d || f > 0; j++ )
{
x = a[j] * b + f;
f = x / 10;
a[j] = x % 10;
}
while(a[j] == 0) j--; // 去除前導 的 0
d = j; // d 表示數組中已經被重置的個數
}
/*這裡處理的情況是當 m < 1 的情況*/
if(d < (digits-1)){
cout << '.';
for(k = 0; k < (digits-1)-d; k++)
cout << 0;
}
/*這裡處理的情況是當 m > 1 的情況*/
for(i = d; i >= 0; i--)
{
if(i == (digits-1)) cout << '.' ;
cout << a[i];
}
cout << endl;
//begin 重置數據 為下一輪循環做准備
for(i=0; i < MAX; i++)
{
str[i] = '?';
}
for(i = 0; i < 1000; i++) //將數組全部置 0
{
a[i] = 0;
}
digit = 0;
digits = 0;//end
}
return 0;
}
