精确乘幂

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 
#include 
#include //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=0;//define the buffer to store the datachar * str = (char *)malloc(sizeof(char)*(length+1));memset(str, '\0', length+1);memcpy(str, src, length);/*  puts(str);*/strrev(str);/*  puts(str);*///transfer string to int//int temp = *number; //原有的数据不为零时，也需要考虑int i, j;for (i=0, j=0; 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 memoryfree(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 procedurefor (i=0; ifor (j=0; j//the i,j place number multi, and the result is on the i+j placeresults[i+j] += numsA[j] * numsB[i];}}//process the resultfor (i=0; (iif (results[i]>=10)  //the low place to the high place, if the low number is >=10{results[i+1] += results[i] /10;results[i] %= 10;}}//calcute lenAfor (i=lenA+lenB-1; i>=0; i--){if (results[i] != 0){break;}}return i+1;
}int main()
{char str[7] = {'\0'};int numsB[5] = {0};int n;scanf("%s %d", str, &n);int length = strlen(str);//获取小数点的位数int PointPlace = string2int(str, numsB, length);if (PointPlace!=0) // reduce the . nums{length--;}int * pNumsA = (int *)malloc(length*n*sizeof(int));int * pResults = (int *)malloc(length*n*sizeof(int));memset(pNumsA, 0, length*n*sizeof(int));memset(pResults, 0, length*n*sizeof(int));memcpy(pNumsA, numsB, length*sizeof(int));// int i;// for (i=0; i// {//      printf("%d", pNumsA[i]);// }// printf("-%d\n", PointPlace);int lenA = length;/*printf("%d", lenA);*/int i, j;int bIsBegin = 0;char * pString = (char *)malloc(sizeof(char)*length*n+2);memset(pString, '\0', sizeof(char)*length*n+2);if (n==1){printf("%s", str);}else{//求幂for (i=1; imemcpy(pNumsA, pResults, lenA*sizeof(int));memset(pResults, 0, lenA*sizeof(int));//printf("LenA---%d\n", lenA);}//将结果由数组转化为字符串并添加小数点i=0;j = 0;while (iif (pNumsA[i]==0){if (1==bIsBegin){if ( i==(PointPlace*n) ){if (i!=0)pString[j++] = '.';}pString[j++] = pNumsA[i++] + '0';}elsei++;}else{bIsBegin = 1; begin from the first non-zero valueif ( i==(PointPlace*n) ){if (i!=0){pString[j++] = '.';}}pString[j++] = pNumsA[i++] + '0';}}free(pNumsA);free(pResults);//反转字符串：之前的字符串一直是倒叙的strrev(pString);//输出结果：主要是处理小数点前0的个数if (PointPlace==0){for (i=0; iif (pString[i]!='0')break;}printf("%s", &pString[i]);}else{for (i=0; iif (pString[i]!='0'){if (pString[i]=='.'){i--;break;}else{break;}}}printf("%s", &pString[i]);}}free(pString);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！