2010年4月27日 星期二

Problem 748 Exponentiation,小數次方

此題是要求出 Rn 次方的數值,每個整數或小數必須精準,所以這是一個大數乘法的運算。

舉個例子,22.24 的 2 次方是 494.6176(22242 = 4946176),當中,本來小數點的左邊數過來的第 2 位,2 次方之後是在第 4 位,我們可以觀察之後的次方並不難發覺小數點跟次方有成正比的相關。3 次方為 11000.295424(22243 = 11000295424)、4 次方為 244646.57022976(22244 = 24464657022976)、 ....等等,所以我們只要能求出 2224 的次方,再將小數點點在正確位置就可以了。

首先,讀入一個 R 字串和 n 整數代表 R 和 n,再將字串顛倒轉為整數陣列,順便記錄小數點的位置。C 語言程式碼如下:
#define MAXLEN 100

主程式內...
int decimal[MAXLEN + 20] = {0}, rInt[8] = {0}, pointSite = -1;
for (i = 5, j = 0; i >= 0; i --)
{
if (R[i] != '.') rInt[j] = R[i] - '0',
decimal[j] = R[i] - '0', j ++;
else pointSite = j;
}
再用大數相乘概念將 decimal 陣列累乘 n 次。 C 語言程式碼如下:
int a = n;
a --;
while (a --)
{
int nowDecimal[MAXLEN + 20] = {0};
for (i = 0; i < j; i ++)
{
for (k = 0; k < MAXLEN; k ++)
{
nowDecimal[i + k] += decimal[k] * rInt[i];
if (nowDecimal[i + k] >= 10)
nowDecimal[i + k + 1] += nowDecimal[i + k] / 10, nowDecimal[i + k] %= 10;
}
}
for (k = 0; k < MAXLEN; k ++)
decimal[k] = nowDecimal[k];
}

print(decimal, n * pointSite);
最後寫一函式 print(int dec[], int pS),將待印出整數陣列 dec[] 與小數點位置 pS 傳入就能將它印出,其中,需要判斷它整數部分是否為 0。如果為 0,就不需要印出數字,直接印出小數點。還有,小數部分如果結尾有 0,甚至有很多個 0,也要剔除。C 語言程式碼如下:
void print(int dec[], int pS)
{
int i, j, end;
for (i = MAXLEN - 1; i >= 0; i --)
if (dec[i] > 0) break;
for (end = 0; ; end ++)
if (dec[end] > 0) break;
if (i - (pS - 1) < 0)
{
printf(".");
for (j = 0; j < (pS-1) - i; j ++)
printf("0");
}
for (j = i; j >= end; j --)
{
if (j == pS - 1) printf(".");
printf("%d", dec[j]);
}
printf("\n");
}

By David.K

p748題目連結
回ACM題庫目錄
回首頁

沒有留言: