Problem 748 Exponentiation，小數次方

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

舉個例子，22.24 的 2 次方是 494.6176(2224² = 4946176)，當中，本來小數點的左邊數過來的第 2 位，2 次方之後是在第 4 位，我們可以觀察之後的次方並不難發覺小數點跟次方有成正比的相關。3 次方為 11000.295424(2224³ = 11000295424)、4 次方為 244646.57022976(2224⁴ = 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題庫目錄
回首頁