POJ 1001 – Exponentiation
求高精度幂
时间限制：500毫秒 内存限制：10000KB
【问题描述】
对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。
现在要你解决的问题是：对一个实数R(0.0 < R < 99.999)，要求写出程序精确计算R的n次方(Rn)，其中n是整数并且0 < n <= 25。
【输入格式】
输入包括多组R和n。R的值占第1到第6列，n的值占第8和第9列。
【输出格式】
对于每组输入，要求输出一行，该行包含精确的R的n次方。输出需要去掉前导的0和后面不要的0。如果输出是整数，不要输出小数点。
【输入样例】
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
【输出样例】
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
【解题思路】
看到这道题，首先第一个想到的应该是，直接用C++的double类型计算的话是无法达到题目要求的精度的。那么，要怎样进行编程才能达到这么高的精度呢？
第二个直接的想法就是，按照我们手算的过程来解这道题。手算的过程又是什么样的呢？这个…貌似是小学生都知道的事情。举个例子，如果我们要算1234×1234，那么我们会在草稿纸上排出下面这个算式：
这个算式是什么意思相比大家都很清楚，就不多加解释了。首先，你不得不承认的是，这么算出来的肯定是最精确的。于是，我们就有了这样的想法，让程序跑一遍这样的方法来计算幂的值，不就是最精确的结果了么。
所以，要实现程序的这种算法，需要把一个数的每一位都分离出来成为一个单独的数。而最方便的方法就是字符串读取。即，把"95.123"当成一个字符串读取，这样，要获得哪一位的数字直接获取字符串的对应位置的字符就行了。
然后，我们可以发现，这道题的小数乘法完全可以先按照整数乘法来进行运算，计算完之后再确定小数点的位置就可以了（事实上，我们手算两个数相乘的时候也是先不管小数点的位置，算完之后再点上小数点就可以了）。
这样，我们便将小数运算转换成了字符整数运算。我们知道，字符里的0~9的ASCII码比数字0~9要大48。也就是说，字符'7'（7的ASCII码为55）减去48就是数字7，其它数字也是这样。循着这个思路，我们可以发现，两个整数相乘，我们第一步做的是将乘数的各位乘以被乘数，然后列成一个斜着的式子，最后相加。例如，1234×1234，我们首先做的就是先分别计算1234×4，1234×3，1234×2，1234×1，分别算出这些乘法的答案之后，再根据特定的规则相加，就像上面的式子列出来的那样。这个过程的原理用数学式子来表示的话是下面这个样子的：
了解过程之后，我们的第一个任务就是要实现一个函数，这个函数要能够计算多位数乘以一位数，也就是上面等式的第一步。这个函数的实现代码如下：
// 计算 多 乘以 一 的情况，例如，1234 * 4
// many: 多位数
// one: 单位数
// offset: 乘10偏移
// return: 返回计算结果
char * MMO(char * many, char one, int offset)
{
int mLength; // 多位数的长度
char * res; // 计算结果
int i;
int n1, n2; // 逐位相乘的两个乘数
int sres; // 逐位相乘的积
int carry; // 进位
// 初始化各变量
n2 = one - 48;
carry = 0;
// 获取多位数的位数
mLength = -1;
while(many[++mLength]);
// 计算运算结果的位数并分配空间
res = new char[mLength + 1 + offset + 1];
// 初始化结果为0
for(i=0; i < mLength + offset + 1; i++)
{
res[i] = '0';
}
res[mLength + offset + 1] = 0; // 字符串结尾
// 逐位相乘
for(i = mLength - 1; i >= 0; i--)
{
n1 = many[i] - 48;
// 1. 将两个乘数相乘
sres = n1 * n2;
// 2. 将结果再加上进位
sres += carry;
// 3. 将计算得到的结果分成10进位和个位
res[i + 1] = sres % 10 + 48; // 个位，直接存在计算结果中
carry = sres / 10; // 十位，保存在进位中
}
// 将进位存入最高位
res[0] = carry + 48;
// 返回计算结果
return res;
}
这个函数有三个参数，第一个参数是存储被乘数的字符串，比如"1234"，第二个参数是乘数的某一位，比如个位"4"。第三个参数说明乘数乘以的是哪一位。0表示当前是个位，1表示的是十位，2表示的是百位，以此类推。计算的结果也是以字符串的形式存储，并且根据当前的位标识offset在结果的后面补0。举个例子，要计算1234×1234，需要调用该函数4次，分别是：
-
调用：MMO("1234", '4', 0)，返回 "04936"；
-
调用：MMO("1234", '3', 1)，返回 "037020"；
-
调用：MMO("1234", '2', 2)，返回 "0246800"；
-
调用：MMO("1234", '1', 3)，返回"01234000"。
返回结果最前面的0是为最高位进位所保留的一位，因为，一个4位数乘以一个1位数答案很有可能是一个5位数。之所以需要offset指定位数，由上面的结果可以看出，按照指定的offset在末尾加上等同的0之后，这四个数直接相加就是我们要的结果。
那么，看看这个函数具体是怎么实现的，首先注意到这两行：
mLength = -1;
while(many[++mLength]);
这两行的作用是计算many这个字符串一共有多少位。其实，可以直接调用strlen函数来获取一个字符串的长度，但是我为了找找编程的感觉，就自己去实现了这个功能。这种写法不大常见，可能看上去有点奇怪。但是，你只要注意到，这是一个循环体只有一句空语句（";"）的while循环，你就明白是什么意思了。上面的程序相当于下面这种写法：
mLength = -1;
do{
mLength = mLength + 1;
}while(many[mLength]);
最后，mLength存储的就是many这个字符串的长度。废话有点多了，那么，看这个函数的核心部分。
首先，函数为结果字符串res分配了空间。一个n位数乘以一个1位数，结果最多只能是n+1位数，然后需要在末尾补上offset个0，再加上1位保存字符串结束符0，所以res的空间长度为：mLength + 1 + offset + 1。
然后，利用一个for循环来计算。计算的时候，是从被乘数的个位开始，分别乘以乘数，产生一个个位结果和一个进位，然后再用十位的数乘以乘数，加上进位后，又产生一个个位和进位。如果这个过程不明白，你手算一遍就知道了。
for(i = mLength - 1; i >= 0; i--)
{
n1 = many[i] - 48;
// 1. 将两个乘数相乘
sres = n1 * n2;
// 2. 将结果再加上进位
sres += carry;
// 3. 将计算得到的结果分成10进位和个位
res[i + 1] = sres % 10 + 48; // 个位，直接存在计算结果中
carry = sres / 10; // 十位，保存在进位中
}
这段代码就是实现的过程。i从many字符串的末尾朝前移动。然后，通过many[i]来获取某一位上的数字的字符表示，减去48之后就是这一位的数字。将这一位和乘数相乘，再加上上一次计算得到的进位，可以获得一个最大是两位数的结果，这个两位数的个位就是最终结果当前计算位置的数值，而这个两位数的十位就是下一次计算要用到的进位。
进过上面的过程之后，再进行一些简单的调整，结果就计算出来了。
在每一位都和被乘数相乘之后，需要将这些结果加起来。所以，还需要实现一个多位数和多位数相加的函数。函数实现如下：
// 计算两个多位数相加，将结果存入m1，并释放m2
// m1: 多位数1
// m2: 多位数2
// 需要注意的是，多位数1的位数一定要大于等于两数和的位数
void MPM(char * m1, char * m2)
{
int l1, l2; // 两个多位数的长度
char * res; // 计算结果
int i;
int lRes; // 结算结果的长度
int carry; // 进位
int n1, n2; // 两个单位加数位
// 初始化变量
carry = 0;
// 获取两个加数的长度
l1 = l2 = -1;
while(m1[++l1]);
while(m2[++l2]);
// 实现两数相加
for (i=1; i <= l1; i++)
{
n1 = m1[l1 - i] - 48;
if(l2 - i < 0)
n2 = 0;
else
n2 = m2[l2 - i] - 48;
// 计算两数和并存入m1中
m1[l1 - i] = (n1 + n2 + carry) % 10 + 48;
carry = (n1 + n2 + carry) / 10;
}
// 将进位存入首位
if(l1 != l2)
m1[l1 - l2 - 1] = carry + 48;
// 释放被加数
delete m2;
}
因为后面程序动态分配空间管理的需要，这里实现的多位数相加是将计算结果直接覆盖到被加数上，而不重新新建一个字符串并返回。为什么这么做，你将整个程序连起来看一遍就能明白了。
相加的过程和相乘的过程有点像，就是分别从被加数和加数的个位开始，获取那一位上的数字，相加，将计算结果分成个位和十位，个位保存在结果字符串中，十位则作为进位供下一次计算使用。由于被加数和加数的位数不一定是一样长的，所以在加的时候需要判断一下，如果加数的位数少于被加数的位数的时候，就在计算缺少的高位的时候将那一位补上一个0。那么，会不会是被加数的位数少于加数的位数呢？开玩笑！如果被加数位数比加数位数少，那么被加数又怎么可能存得下两个数相加的结果呢？
实现了上面两个函数之后，就可以编写我们最终要实现的多位数乘以多位数的函数了。函数的实现如下：
// 计算两个多位数相乘
// m1: 乘数1
// m2: 乘数2
// return: 返回两数相乘结果
char * MMM(char * m1, char * m2)
{
int l1, l2; // 两个多位数的长度
char * res; // 计算结果
int i;
int lRes; // 结算结果的长度
int carry; // 进位
int n1, n2; // 两个单位乘数位
// 初始化变量
carry = 0;
// 获取两个加数的长度
l1 = l2 = 0;
while(m1[l1++]);
while(m2[l2++]);
l1--;
l2--;
// 为了减少计算乘法次数，将位数较少的数作为乘数
if(l1 < l2)
{
char * tp = m2;
m2 = m1;
m1 = tp;
int tpl = l2;
l2 = l1;
l1 = tpl;
}
// 为计算结果分配空间
// 两数相乘的结果的位数 = 被乘数的位数 + 乘数的位数
lRes = l2 + l1;
res = new char[lRes + 1];
// 初始化结果为0
for (i=0; i < lRes; i++)
{
res[i] = '0';
}
res[lRes] = 0;
// 进行逐位相乘
for(i=1; i <= l2; i++)
{
char * sr = MMO(m1, m2[l2 - i], i-1);
MPM(res, sr);
}
// 返回计算结果
return res;
}
在进行相乘之前，为了减少调用函数的次数，我们做了一个判断，将位数较少的数作为乘数，位数较多的数作为被乘数，这样就可以减少调用MMO函数和MPM函数的次数了。
// 进行逐位相乘
for(i=1; i <= l2; i++)
{
char * sr = MMO(m1, m2[l2 - i], i-1);
MPM(res, sr);
}
上面这段代码就是多位数相乘的核心部位，可以看出，其算法思想是先通过MMO函数计算得到被乘数和乘数的某一位相乘的结果，并存在一个临时的字符数组sr中，sr的存储空间是在MMO函数中进行分配的。
随后，将MMO得到的结果sr和保存最终结果的res字符数组相加，结果存入res中。仔细看MPM函数的代码可以发现，sr的临时空间在MPM的最后一句话中被正确释放掉了。而res的空间则是在一开始就分配好的。MPM(res, sr)的作用相当于执行了：
res = res + sr;
delete sr;
而res的空间是在计算之前就可以获知的。你可以试着想想看，一个m位数乘以一个n位数，最终的结果最多是几位数？
字符串的多位数相乘实现了，后面的也就好说了很多。接下来，就需要写一个函数来实现我们的最终目标，计算R的n次方。函数代码如下：
// 计算 R 的 N 次方，R和N均为整数
// return: 返回未修饰的计算结果
char * RN(char * R, int N)
{
if(N < 2)
return R;
char * res = MMM(R, R);
for(int i=0; i < N-2; i++)
{
char * res2 = res;
res = MMM(res, R);
delete res2;
}
return res;
}
这个计算函数的思想很简单，就是让结果不断的乘以R，最后返回这个结果就行了。其实，幂计算是可以进一步优化提升速度了。因为这里n最大也只有25，所以我就懒得去优化了。就这么着吧。
到这里，整数的n次方已经可以非常精确的计算出来了，并且计算的结果是字符串的形式。现在面临的问题是，怎么确定小数点的位置。这个问题其实并不困难，如果输入R的小数位数是4，经过6次方计算后，结果的小数位数用肚子想也应该是24位。只有从整数计算结果的后面往前的24位前加一个"."就行了。
最后一个麻烦的事情就是怎样按照题目的要求输出对应格式的答案了。这个格式是要去掉所有不必要的前导0和后导0，这个"不必要的"包括小数点前面的那个0。而我们计算的结果，前后可能都会出现很多不必要的0，而且还没有小数点。所以，为了格式化输出，我专门写了一个函数如下：
// 规范化输出计算结果，加上小数点，并去掉多余的0
void OutputRes(char * res, int pNum)
{
int lRes;
int i;
bool flag;
// 获取输出字符串的长度
lRes = -1;
while(res[++lRes]);
// 计算输出区间
flag = false;
if(pNum > 0)
{
// 过滤首尾不用输出的0
for (i=0; i < lRes - pNum; i++)
{
if(res[i] != '0')
break;
else
res[i] = '#';
}
for(i=1; i <= pNum; i++)
{
if(res[lRes - i] != '0')
break;
else
res[lRes - i] = '#';
}
if(i > pNum) // 小数部位不用输出
flag = true;
}else{
flag = true;
for (i=0; i < lRes; i++)
{
if(res[i] != '0')
break;
else
res[i] = '#';
}
for (i=1; i <= lRes; i++)
{
if(res[lRes - i] != '0')
break;
else
res[lRes - i] = '#';
}
}
// 输出结果
for(i=0; i < lRes; i++)
{
if((i == lRes - pNum) && (!flag))
cout<<".";
if(res[i] != '#')
{
cout<<res[i];
}
}
cout<<endl;
}
这个函数的工作过程如下：
-
首先计算结果的长度，这步其实可以用一个strlen搞定；
-
判断小数位数，如果小数位数为0（也就是本来计算的就是整数的n次方）：
-
去掉所有的前置0和后置0，直接输出结果就行。
如果小数为师不为0：
-
找到小数点的位置；
-
将小数点前面的所有0去掉；
-
将小数点后面的所有0去掉；
-
如果去掉0之后小数点后面没有数字了，则设置flag，不输出小数点；
-
根据flag标志输出最后结果。
-
在这个函数中，"去掉0"的方法就是将不输出的'0'字符替换成'#'字符，然后在输出的时候遇到'#'的时候不输出就行了。
那么，到这里，这道题也就差不多解决了。下图展示了程序的运行结果：
【程序源码】
#include <iostream>
using namespace std;
// 计算 多 乘以 一 的情况，例如，1234 * 4
// many: 多位数
// one: 单位数
// offset: 乘10偏移
// return: 返回计算结果
char * MMO(char * many, char one, int offset)
{
int mLength; // 多位数的长度
char * res; // 计算结果
int i;
int n1, n2; // 逐位相乘的两个乘数
int sres; // 逐位相乘的积
int carry; // 进位
// 初始化各变量
n2 = one - 48;
carry = 0;
// 获取多位数的位数
mLength = -1;
while(many[++mLength]);
// 计算运算结果的位数并分配空间
res = new char[mLength + 1 + offset + 1];
// 初始化结果为0
for(i=0; i < mLength + offset + 1; i++)
{
res[i] = '0';
}
res[mLength + offset + 1] = 0; // 字符串结尾
// 逐位相乘
for(i = mLength - 1; i >= 0; i--)
{
n1 = many[i] - 48;
// 1. 将两个乘数相乘
sres = n1 * n2;
// 2. 将结果再加上进位
sres += carry;
// 3. 将计算得到的结果分成10进位和个位
res[i + 1] = sres % 10 + 48; // 个位，直接存在计算结果中
carry = sres / 10; // 十位，保存在进位中
}
// 将进位存入最高位
res[0] = carry + 48;
// 返回计算结果
return res;
}
// 计算两个多位数相加，将结果存入m1，并释放m2
// m1: 多位数1
// m2: 多位数2
// 需要注意的是，多位数1的位数一定要大于等于两数和的位数
void MPM(char * m1, char * m2)
{
int l1, l2; // 两个多位数的长度
char * res; // 计算结果
int i;
int lRes; // 结算结果的长度
int carry; // 进位
int n1, n2; // 两个单位加数位
// 初始化变量
carry = 0;
// 获取两个加数的长度
l1 = l2 = -1;
while(m1[++l1]);
while(m2[++l2]);
// 实现两数相加
for (i=1; i <= l1; i++)
{
n1 = m1[l1 - i] - 48;
if(l2 - i < 0)
n2 = 0;
else
n2 = m2[l2 - i] - 48;
// 计算两数和并存入m1中
m1[l1 - i] = (n1 + n2 + carry) % 10 + 48;
carry = (n1 + n2 + carry) / 10;
}
// 将进位存入首位
if(l1 != l2)
m1[l1 - l2 - 1] = carry + 48;
// 释放被加数
delete m2;
}
// 计算两个多位数相乘
// m1: 乘数1
// m2: 乘数2
// return: 返回两数相乘结果
char * MMM(char * m1, char * m2)
{
int l1, l2; // 两个多位数的长度
char * res; // 计算结果
int i;
int lRes; // 结算结果的长度
int carry; // 进位
int n1, n2; // 两个单位乘数位
// 初始化变量
carry = 0;
// 获取两个加数的长度
l1 = l2 = 0;
while(m1[l1++]);
while(m2[l2++]);
l1--;
l2--;
// 为了减少计算乘法次数，将位数较少的数作为乘数
if(l1 < l2)
{
char * tp = m2;
m2 = m1;
m1 = tp;
int tpl = l2;
l2 = l1;
l1 = tpl;
}
// 为计算结果分配空间
// 两数相乘的结果的位数 = 被乘数的位数 + 乘数的位数
lRes = l2 + l1;
res = new char[lRes + 1];
// 初始化结果为0
for (i=0; i < lRes; i++)
{
res[i] = '0';
}
res[lRes] = 0;
// 进行逐位相乘
for(i=1; i <= l2; i++)
{
char * sr = MMO(m1, m2[l2 - i], i-1);
MPM(res, sr);
}
// 返回计算结果
return res;
}
// 计算 R 的 N 次方，R和N均为整数
// return: 返回未修饰的计算结果
char * RN(char * R, int N)
{
if(N < 2)
return R;
char * res = MMM(R, R);
for(int i=0; i < N-2; i++)
{
char * res2 = res;
res = MMM(res, R);
delete res2;
}
return res;
}
// 规范化输出计算结果，加上小数点，并去掉多余的0
void OutputRes(char * res, int pNum)
{
int lRes;
int i;
bool flag;
// 获取输出字符串的长度
lRes = -1;
while(res[++lRes]);
// 计算输出区间
flag = false;
if(pNum > 0)
{
// 过滤首尾不用输出的0
for (i=0; i < lRes - pNum; i++)
{
if(res[i] != '0')
break;
else
res[i] = '#';
}
for(i=1; i <= pNum; i++)
{
if(res[lRes - i] != '0')
break;
else
res[lRes - i] = '#';
}
if(i > pNum) // 小数部位不用输出
flag = true;
}else{
flag = true;
for (i=0; i < lRes; i++)
{
if(res[i] != '0')
break;
else
res[i] = '#';
}
for (i=1; i <= lRes; i++)
{
if(res[lRes - i] != '0')
break;
else
res[lRes - i] = '#';
}
}
// 输出结果
for(i=0; i < lRes; i++)
{
if((i == lRes - pNum) && (!flag))
cout<<".";
if(res[i] != '#')
{
cout<<res[i];
}
}
cout<<endl;
}
int main(){
char R[10], Rin[10]; // 读入的乘幂运算的底
int N; // 读入的乘幂运算的指数
int pNum; // 读入的小数位数
// 读入并计算
while(cin>>Rin>>N)
{
// 获得小数点的位数，并获取去掉小数点后的整数
int l;
int ll;
l = ll = 0;
pNum = -1;
while(Rin[l])
{
if(Rin[l] == '.')
{
pNum = l + 1;
}else{
R[ll++] = Rin[l];
}
l++;
}
R[ll] = 0;
if(pNum != -1)
pNum = l - pNum;
else
pNum = 0;
pNum = pNum * N;
// 计算并输出结果
char * s = RN(R, N);
OutputRes(s, pNum);
if(s != R)
delete s;
}
return 0;
}
