求高精度幂
| Time Limit: 500MS | Memory Limit: 10000K | |
| Total Submissions: 87719 | Accepted: 20833 |
Description
对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。
现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999)，要求写程序精确计算 R 的 n 次方(R n)，其中n 是整数并且 0 < n<= 25。
现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999)，要求写程序精确计算 R 的 n 次方(R n)，其中n 是整数并且 0 < n<= 25。
Input
T输入包括多组 R 和 n。 R 的值占第 1 到第 6 列，n 的值占第 8 和第 9列。
Output
对于每组输入，要求输出一行，该行包含精确的 R 的 n 次方。输出需要去掉前导的 0 后不要的 0。如果输出是整数，不要输出小数点。
Sample Input
95.123 12 0.4321 20 5.1234 15 6.7592 9 98.999 10 1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721 .00000005148554641076956121994511276767154838481760200726351203835429763013462401 43992025569.928573701266488041146654993318703707511666295476720493953024 29448126.764121021618164430206909037173276672 90429072743629540498.107596019456651774561044010001 1.126825030131969720661201
分析：在计算机上进行高精度计算，首先要处理好以下几个基本问题：
1、数据的接收与存储；
2、计算结果位数的确定；
3、进位处理和借位处理；
4、商和余数的求法；
输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组和字符串。
（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；优点：每一位都是数的形式，可以直接加减；运算时非常方便缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；
（2）字符串：字符串的最大长度是255，可以表示255位。优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便（注意‘0’的问题）。
优化:
一个数组元素存放四位数
注意：是加减法时可以用interger，但是当是乘法的时候，就要用int64，否则会出现越界的情况。
还有就是：输出时对非最高位的补零处理。
另一个问题：
存储顺序
正序？？
逆序？？
还有就是一定不要忘了初始化！！
计算结果位数的确定
两数之和的位数最大为较大的数的位数加1。
乘积的位数最大为两个因子的位数之和。
阶乘：lgn!=lgn+lg(n-1)+lg(n-2)...................+lg3+lg2+lg1
=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+................+ln3/ln10+ ln2/ln10+ln1/ln10
=trunc(1/ln10*(lnn+ln(n-1)+ln(n-2)+...........+ln3+ln2+ln1)
乘方：lg(a?^b)=trunc(lg(a^b))+1
=trunc(b*lga)+1
=trunc(b*lna/ln10)+1
高精度的加法
ncarry=0;
for (i=0;i<=len;i++)
{
k=a[i]+b[i]+ncarry;
a[i+1]+=k/N;
ncarry=k%N;
}
当最后ncarry>0时，len会变化！！
高精度的减法
先比较大小，大的为a，用一个变量记录符号。
ncarry=0;
for (i=0;i<=len;i++)
{
if (a[i]-b[i]-ncarry>=0)
a[i]=a[i]-b[i]-ncarry,ncarry=0;
else
a[i]=a[i]+N-b[i]-ncarry,ncarry=1;
}
高精度的乘法
For (i=0;i<=lena;i++)
for (j=0;j<=lenb;j++)
c[i+j]+=a[i]*b[j];
For (i=0;i<=lena+lenb;i++)
{
c[i+j+1]+=c[i+j]/N;
c[i+j]=c[i+j]/N;
}
高精度的除法
A÷B精确值有两种情况：①、A能被B整除，没有余数。②、A不能被B整除，对余数进行处理。首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和余数。
可以用减法代替除法运算：不断比较A[1..n]与B[1..n]的大小，如果A[1..n]>=B[1..n]则商C[1..n]+1→C[1..n]，然后就是一个减法过程：A[1..n]-B[1..n]→A[1..n]。
由于简单的减法速度太慢，故必须进行优化。
设置一个位置值J，当A[1..n]>B[1..n]时，B[1..n]左移→B[0..n]，j:=j+1，即令B[1..n]增大10倍。这样就减少了减法的次数。当j>0且A[1..n]<B[1..n]时，B[0..n]右移
求n！
一个例子：计算5*6*7*8
方法一：顺序连乘
5*6=30，1*1=1次乘法
30*7=210，2*1=2次乘法
210*8=1680，3*1=3次乘法
方法二：非顺序连乘
5*6=30，1*1=1次乘法
7*8=56，1*1= 1次乘法
30*56=1680，2*2=4次乘法
若“n位数*m位数=n+m位数”，则n个单精度数。
无论以何种顺序相乘，乘法次数一定为n(n-1)/2次。（n为积的位数）
证明：
设F(n)表示乘法次数，则F(1)=0，满足题设
设k<n时，F(k)=k(k-1)/2，现在计算F(n)
设最后一次乘法计算为“k位数*(n-k)位数”，则
F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（与k的选择无关）
考虑k+t个单精度数相乘
a1*a2*…*ak *ak+1*…*ak+t
设a1*a2*…*ak结果为m位高进制数（假设已经算出）
ak+1*…*ak+t结果为1位高进制数
若顺序相乘，需要t次“m位数*1位数” ，共mt次乘法
可以先计算ak+1*…*ak+t，再一起乘，只需要m+t次乘法
在设置了缓存的前提下，计算m个单精度数的积，如果结果为n位数，则乘法次数约为n(n–1)/2次，与m关系不大
设S=a1*a2*…*am，S是n位高进制数
可以把乘法的过程近似看做，先将这m个数分为n组，每组的积仍然是一个单精度数，最后计算后面这n个数的积。时间主要集中在求最后n个数的积上，这时基本上满足“n位数*m位数=n+m位数”，故乘法次数可近似的看做n(n-1)/2次
10!=28*34*52*7
n!分解质因数的复杂度远小于nlogn，可以忽略不计
与普通算法相比，分解质因数后，虽然因子个数m变多了，但结果的位数n没有变，只要使用了缓存，乘法次数还是约为n(n-1)/2次
因此，分解质因数不会变慢（这也可以通过实践来说明）
分解质因数之后，出现了大量求乘幂的运算，我们可以优化求乘幂的算法。这样，分解质因数的好处就体现出来
二分法求乘幂
a2n+1=a2n*a
a2n=(an)2
其中，a是单精度数
二分法求乘幂之优化平方算法
怎样优化
(a+b)2=a2+2ab+b2
例：123452=1232*10000+452+2*123*45*100
把一个n位数分为一个t位数和一个n-t位数，再求平方
怎样分
设求n位数的平方需要F(n)次乘法
F(n)=F(t)+F(n-t)+t(n-t)，F(1)=1
用数学归纳法，可证明F(n)恒等于n(n+1)/2
所以，无论怎样分，效率都是一样
将n位数分为一个1位数和n–1位数，这样处理比较方便
优化：
计算S=ax+kbx=(ab)xak
当k<xlogab时，采用(ab)xak比较好，否则采用ax+kbx更快
可以先计算两种算法的乘法次数，再解不等式，就可以得到结论
也可以换一个角度来分析。其实，两种算法主要差别在最后一步求积上。由于两种方法，积的位数都是一样的，所以两个因数的差越大，乘法次数就越小
∴当axbx–ak>ax+k–bx时，选用(ab)xak，反之，则采用ax+kbx。
∴axbx–ak>ax+k–bx
∴(bx–ak)(ax+1)>0
∴bx>ak
这时k<xlogab
这道题：
1.处理小数点问题，以及反序。
2.进行n次乘法。
3.进行输出，并加上小数点。
代码：
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string mlp; //乘数
int power; //乘数的幂
int r[151]; //保存结果
int hdot;
while(cin>>mlp>>power)
{
hdot=0;
for(int t=0;t<150;t++)
{
r[t]=-1;
}
if(mlp.find(".")!=string::npos)
hdot=mlp.length()-mlp.find(".")-1;
string::iterator itr=mlp.end()-1;
while(hdot>0&&itr>=mlp.begin())
{
if(*itr!='0')
{break;}
hdot--;
itr--;
}
int cn=0;
while(itr>=mlp.begin())
{
if(*itr!='.')
{
r[cn]=*itr-'0';
cn++;
}
itr--;
}
int k=cn-1;
int m=0; //保存临时数；
while(k>-1)
{
m=m*10+r[k];
k--;
}
for(int i=1;i<power;i++)
{
int j=0;
while(r[j]>-1)
{
r[j]=r[j]*m;
j++;
}
j=0;
while(r[j]>-1)
{
if(r[j+1]==-1&&r[j]>=10)
r[j+1]=r[j]/10;
else
r[j+1]+=r[j]/10;
r[j]=r[j];
j++;
}
}
hdot=hdot*power;
int cnt=0;
while(r[cnt]>-1)
{
cnt++;
}
if(hdot>=cnt)
{
cout<<".";
while(hdot>cnt)
{
cout<<"0";
hdot--;
}
hdot=0;
}
for(k=cnt-1;k>=0;k--)
{
if((k+1)==hdot&&hdot!=0)
cout<<".";
cout<<r[k];
}
cout<<endl;
}
return 0;
}
