精确乘幂

1. 算法思想

精确乘幂的思想秉承于大數乘法，但其實質仍是大數的相乘。隻不過，由于底數可以為小數，相比較于大數相乘，需要處理小數點的問題。但是我們可以将采用分離的思想，記錄小數點所在的位數（從右往左數，且從0開始）并去除小數點，先将小數換為大數，求出大數的成績，再填入小數點。

2. 問題描述

2.1 問題描述

對一個實數R(R為0~1000之間的實數)，編寫程式精确計算R的N次方，其中N是整數且0<=N<=25.

2.2 輸入

輸入R和N，用空格分隔。

2.3 輸出

R的N次方精确值，輸出無需去掉無用的0，如果輸出結果為整數，不要輸出小數點。

3. 問題要點

在本題中，需要把握的要點有三點：

1）一個n位的整數和一個m位的整數相乘的結果，其位數最高為m+n；

2）兩數相乘之後的小數點問題，可以遷移為：小數點位于第i位（從右往左數，且i從0開始，i=0代表該數為整數），相當于将小數點向左移動了i位。

那麼，兩個小數a和b相乘，a和b的小數點在第i，j位，那麼處理完之後的結果中，小數點位于i+j位；

3）處理最終結果中無效的零，包括整數部分的0和小數部分的0.

4. 算法實作

4.1 重要函數聲明

大數相乘算法聲明

//大數相乘
//乘數：numsA，numsB
//長度：lenA， lenB
int BigNumberMultiplication(int * numsA, int lenA, int * numsB, int lenB, int *
                            results);
           

字元串向int轉換函數實作

//change the string to the big-int and save them in array
//傳回值：小數點的位數
//src: the String
//number: the array
//length: string's length
int string2int(char * src, int * number, int length);
           

4.2 算法完整實作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//change the string to the big-int and save them in array
//傳回值：小數點的位數
//src: the String
//number: the array
//length: string's length
int string2int(char * src, int * number, int length);

int string2int(char * src, int * number, int length)
{
    int flag=;
    //define the buffer to store the data
    char * str = (char *)malloc(sizeof(char)*(length+));
    memset(str, '\0', length+);
    memcpy(str, src, length);
    /*  puts(str);*/
    strrev(str);
    /*  puts(str);*/
    //transfer string to int
    //int temp = *number; //原有的資料不為零時，也需要考慮
    int i, j;
    for (i=, j=; i<length; i++)
    {
        //temp *= 10;
        //原有資料為字元'A'，顧需要減去'0'
        if (str[i]!='.')
        {
            number[j++] += (int)(str[i] - '0');
        }
        else
        {
            flag = j;
        }

    }
    //return the transfer number
    //*number = temp;
    //clear the dynamic memory
    free(str);
    str = NULL;
    return flag;
}

//大數相乘
//乘數：numsA，numsB
//長度：lenA， lenB
int BigNumberMultiplication(int * numsA, int lenA, int * numsB, int lenB, int *
                            results);
int BigNumberMultiplication(int * numsA, int lenA, int * numsB, int lenB, int * results)
{
    int i, j;
    //multi procedure
    for (i=; i<lenB; i++)
    {
        for (j=; j<lenA; j++)
        {
            //the i,j place number multi, and the result is on the i+j place
            results[i+j] += numsA[j] * numsB[i];
        }
    }
    //process the result
    for (i=; (i<lenA+lenB); i++)
    {
        if (results[i]>=)  //the low place to the high place, if the low number is >=
            
        {
            results[i+] += results[i] /;
            results[i] %= ;
        }
    }
    //calcute lenA
    for (i=lenA+lenB-; i>=; i--)
    {
        if (results[i] != )
        {
            break;
        }
    }
    return i+;
}

int main()
{
    char str[] = {'\0'};
    int numsB[] = {};
    int n;
    scanf("%s %d", str, &n);
    int length = strlen(str);
    //擷取小數點的位數
    int PointPlace = string2int(str, numsB, length);
    if (PointPlace!=) // reduce the . nums
    {
        length--;
    }

    int * pNumsA = (int *)malloc(length*n*sizeof(int));
    int * pResults = (int *)malloc(length*n*sizeof(int));
    memset(pNumsA, , length*n*sizeof(int));
    memset(pResults, , length*n*sizeof(int));
    memcpy(pNumsA, numsB, length*sizeof(int));
    // int i;
    // for (i=0; i<length; i++)
    // {
    //      printf("%d", pNumsA[i]);
    // }
    // printf("-%d\n", PointPlace);
    int lenA = length;
    /*printf("%d", lenA);*/
    int i, j;
    int bIsBegin = ;
    char * pString = (char *)malloc(sizeof(char)*length*n+);
    memset(pString, '\0', sizeof(char)*length*n+);
    if (n==)
    {
        printf("%s", str);
    }
    else
    {
        //求幂
        for (i=; i<n; i++)
        {
            lenA = BigNumberMultiplication(pNumsA, lenA, numsB, length,
                                           pResults);
            memcpy(pNumsA, pResults, lenA*sizeof(int));
            memset(pResults, , lenA*sizeof(int));
            //printf("LenA---%d\n", lenA);
        }

        //将結果由數組轉化為字元串并添加小數點
        i=;
        j = ;
        while (i<length*n)
        {
            if (pNumsA[i]==)
            {
                if (==bIsBegin)
                {
                    if ( i==(PointPlace*n) )
                    {
                        if (i!=)
                            pString[j++] = '.';
                    }
                    pString[j++] = pNumsA[i++] + '0';
                }
                else
                    i++;

            }
            else
            {
                bIsBegin = ; begin from the first non-zero value

                if ( i==(PointPlace*n) )
                {
                    if (i!=)
                    {
                        pString[j++] = '.';
                    }

                }

                pString[j++] = pNumsA[i++] + '0';
            }
        }

        free(pNumsA);
        free(pResults);
        //反轉字元串：之前的字元串一直是倒叙的
        strrev(pString);

        //輸出結果：主要是處理小數點前0的個數
        if (PointPlace==)
        {
            for (i=; i<length*n; i++)
            {
                if (pString[i]!='0')
                    break;
            }
            printf("%s", &pString[i]);
        }
        else
        {
            for (i=; i<length*n; i++)
            {
                if (pString[i]!='0')
                {
                    if (pString[i]=='.')
                    {
                        i--;
                        break;
                    }
                    else
                    {
                        break;
                    }

                }

            }
            printf("%s", &pString[i]);
        }
    }

    free(pString);

    return ;
}