首页 > 代码库 > POJ-1001 求高精度幂
POJ-1001 求高精度幂
给定R与n，求Rn的精确值，其中(0.0<R<99.99, n为整数0<n<=25)。
1. 存储结构
由于R最大不超过100，n不会超过25，故Rn不会超过50位，保险起见采用100位的int数组。数组采用与字符串的逆序方式存储，即str=”123456”中str[0]=’1’而存入int数组后，int[0]=’6’。因此，在输入时候，可以通过字符串的字符个数以及是否存在小数点来判断这个数字的位数，根据位数从最高位（str[0]）开始存储数字。这样虽然输入时比较麻烦，但是在计算中扩展位数时会比较方便，高精度运算结构一般都采用这种方法。
另外，还需要有一个记录R的长度的变量length以及记录小数点位数的变量tens，tens代表小数点之后的数字个数，若整数则为0。
2. 高精度乘法
乘法的基本思路是先将两个实数看成整型数进行相乘，之后再处理小数点（处理小数点见后第3点）。两数相乘，乘数从最低位开始，每位分别与被乘数作相乘运算，存入临时变量multinumber中。其中需要注意：
- 乘数的每一位相乘时的最低位不同，rb为乘数相应的位数，也是结果的最低位，见代码中“multinumber.number[i+rb]”；
- 相乘完要及时更新临时变量multinumber的位数；
关键代码如下：
BigNumber BigNumber::operator*(BigNumber &right) const{ ...... for (int rb(0); rb < right.length; rb++) { int over = 0; for (int i(0); over || i < length; i++) { long times = number[i] * right.number[rb] + multinumber.number[i+rb] + over; multinumber.number[i+rb] = times % 10; over = times / 10; } // 修正multinumber的长度 if (multinumber.number[length + rb] != 0) { multinumber.length = length + rb + 1; } else { multinumber.length = length + rb; } } ......}
3. 处理好length与tens
前面提到length是数的长度（数字位数），tens是小数点后的数字位数。做完乘法后，需要对这两个数进行处理。
先看tens，两个数相乘，其结果的小数位数为这两个数小数位数之和，故只需相加即可。
length，由于考虑到0.0000567这样的数，length应该为视为整型数相乘的结果长度与tens的较大者。如下方代码所示，还是刚才的乘法函数，在做完相乘结果后处理length和tens。
BigNumber BigNumber::operator*(BigNumber &right) const{ ...... for (int rb(0); rb < right.length; rb++) { ... } multinumber.tens = tens + right.tens; multinumber.length = max(multinumber.length, multinumber.tens); multinumber.AdjustLength(); ......}
AdjustLength()函数用来删去0.500这样数后面的“0”。这需要特别注意，若是2.5*4，不考虑小数点时结果为25*4=100，考虑小数点后为10.0，此时length为3和tens为1，在删去末尾0时不能两个0都删去，只能删小数点后面的0。（就是这个地方WA了好久。。）
void BigNumber::AdjustLength(){ int index = 0; while (number[index] == 0 &&index < tens
) // index < tens保证不删去小数点前面的0 { index++; } int differ = index; if (differ != 0) { for (index = 0; index < length - differ; index++) { number[index] = number[index + differ]; } for ( ; index < length; index++) { number[index] = 0; } length -= differ; tens -= differ; // 此处的tens也需要与length共同减去differ } }
4. 求幂算法（非递归）
求幂的递归算法采用分治，比较容易编程，但递归过深容易栈溢出，这里采用非递归，希望自己能够记住非递归的快速求幂算法。
number = R;result = "1";while (n > 0){ if (n % 2== 1) { result = result * number; } number = number * number; n = n / 2;}
这道题的知识点就在于高精度乘法的存储及运算方式，小数位数的处理和非递归的快速求幂运算。
虽然书上已经有高精度运算的程序，自己也看过，但真动手写时还是有很多细节，看来以后要多多动手才能加快编码速度。PS，这道题从开始写到最后AC应该花了十几个小时了，不过最后通过的感觉还是棒棒哒！
BigNumber.h文件：
/*BigNumber.h 文件 -- 高精度乘法运算*/#include <iostream>#include <string>#include <cmath>using namespace std;#define MAXBIT 100class BigNumber{public: int number[MAXBIT]; // 数字部分（没有小数点） int tens; // 小数点所在的位数 int length; // 数字部分用的位数 /* ---- 函数成员 ---- */ BigNumber(); void AdjustLength(); BigNumber operator *(BigNumber &right) const; BigNumber operator =(const string right); BigNumber operator =(const BigNumber &right); friend ostream& operator <<(ostream &out, const BigNumber &number);};
BigNumber.cpp 文件：
/*BigNumber.cpp 文件 -- 高精度乘法运算*/#include "BigNumber.h"using namespace std;BigNumber::BigNumber(){ memset(number, 0, sizeof(number)); tens = 0; length = 0;}void BigNumber::AdjustLength(){ int index = 0; while (number[index] == 0 && index < tens) { index++; } int differ = index; if (differ != 0) { for (index = 0; index < length - differ; index++) { number[index] = number[index + differ]; } for ( ; index < length; index++) { number[index] = 0; } length -= differ; tens -= differ; } }BigNumber BigNumber::operator*(BigNumber &right) const{ BigNumber multinumber; for (int rb(0); rb < right.length; rb++) { int over = 0; for (int i(0); over || i < length; i++) { long times = number[i] * right.number[rb] + multinumber.number[i+rb] + over; multinumber.number[i+rb] = times % 10; over = times / 10; } // 修正multinumber的长度 if (multinumber.number[length + rb] != 0) { multinumber.length = length + rb + 1; } else { multinumber.length = length + rb; } } multinumber.tens = tens + right.tens; multinumber.length = max(multinumber.length, multinumber.tens); multinumber.AdjustLength(); return multinumber;}// 初始化时，用字符串传入数字BigNumber BigNumber::operator =(const string numstr){ int len = numstr.length(); if (numstr.find(".") == numstr.npos) { length = len; } else { length = len - 1; } tens = 0; int in = length - 1; for (int i(0); i < len; i++) { if (numstr[i] >= ‘0‘ && numstr[i] <= ‘9‘) { number[in--] = numstr[i] - ‘0‘; } else{ tens = len - i - 1; } } length = number[length-1] == 0? (length - 1) : (length); return *this;}BigNumber BigNumber::operator =(const BigNumber &right){ length = right.length; tens = right.tens; memcpy(number, right.number, sizeof(number)); return *this;}ostream& operator <<(ostream &out, const BigNumber &number){ for (int i(number.length-1); i >= 0; i--) { if (i+1 == number.tens) { out<<"."; } out<<number.number[i]; } return out;}
main.cpp 文件：
/*POJ1001 - - 对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(Rn)，其中n 是整数并且 0 < n <= 25*/#include <iostream>#include <cmath>#include "BigNumber.h"using namespace std;int main(){ string R; int n; while (cin>>R>>n) { BigNumber number, result; number = R; result = "1"; while (n > 0) { if (n % 2== 1) { result = result * number; } number = number * number; n = n / 2; } cout<<result<<endl; } return 0;}
POJ-1001 求高精度幂