前言
第一次写技术博客,请大家多多指教,谢谢!
问题描述
本题目是关于非常高精度数字的通用计算的问题。此题需要你写一个程序,精确的计算R的n次方,R是一个实数,范围0.0<R<99.999,n是一个整数,范围0<n<=25
输入为一对值R和n,R的值占据1~6位,n的值占据8~9位
输出为R^n的结果。不要输出没有意义的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
问题分析
这道题要高精度的乘方运算,并且不希望略去任何小数点的位数。那么,我们要思考的问题是,第一,计算机如何去存储任意精度和长度的数字?第二,怎样去模拟高精度的小数运算?
对于第一个问题,因为一般的编程语言(如C和Java)只提供了最大64bit的数据长度,不能满足此题的需求,而有些动态语言如Python允许任意长度的整数存储,但是不提供对任意常数的小数的支持,因此我们必须自己来设计一种数据结构,存储任意长度实数。我首先想到的是使用数组来做存储,数据的长度根据输入的数据来确定,是否可行,需要结合高精度小数的计算方法来衡量。
对于第二个问题,我们怎么来做高精度的小数的运算呢?我们知道,x86体系的CPU在计算整数乘法的时候有内建的指令支持,速度很快,而浮点数的乘法运算即使目前有CPU的指令级的支持,但对比乘法运算,依然要慢很多(这方面的内容大家可以google了解更多),因此在考虑计算方法的时候优先考虑使用整数运算来模拟小数的运算。
如果我们从输入的数据中记录下小数点的位数,我们就可以根据乘方的次数计算出运算结果的小数点的位置。
这样,就可以将小数的运算转换成整数的运算,即整数的大数运算问题。
任何一个整数按十进制进行展开,可以化作:
A0*10^0 + A1*10^1 + ... + An*10^n
而整数的相乘,则可以化作多项式的乘法,而指数n的大小就是多项式相乘的次数。
我们用数组来存储十进制多项式,数组的索引就是多项式的幂,而数组的元素就是多项式的系数。这样,数据结构和算法就算基本确定下来了。接下来直接贴出代码来描述计算的过程:
int[] dstDigits = new int[numLength * exp]; //被乘数
int[] midRst = new int[numLength * exp]; //存储中间结果
int[] srcDigits = new int[numLength]; //乘数
int dotPos = dotLength * exp; //小数点的位置
dstDigits[0] = 1; // 被乘数初始化为1
int highFlag = 0 + 1; //指示最高位
for (int i = 0; i < numLength; i++) { // 初始化乘数多项式
srcDigits[i] = (int)inteNum.charAt(numLength - i - 1) - '0';
}
// 开始运算
for (int z = 0; z < exp; z++) {
int times = highFlag;
for (int dPos = 0; dPos < times; dPos++) {
for (int sPos = 0; sPos < srcDigits.length; sPos++) {
int pos = dPos + sPos;
// update highFlag
if (pos + 1 > highFlag) highFlag = pos + 1;
midRst[pos] += dstDigits[dPos] * srcDigits[sPos];
if (midRst[pos] / 10 > 0) {
int tmp = midRst[pos];
midRst[pos] = tmp % 10;
midRst[pos + 1] += tmp / 10;
// update highFlag
if (pos + 1 + 1 > highFlag) highFlag = pos + 1 + 1;
}
}
}
for (int s = 0; s < highFlag; s++) {
dstDigits[s] = midRst[s];
midRst[s] = 0;
}
}
// 结果的输出
if (dotPos > highFlag) {
int zeroCnt = dotPos - highFlag;
System.out.print('.');
for (int x = 0; x < zeroCnt; x++) {
System.out.print('0');
}
}
for (int i = highFlag; i > 0; i--) {
if (i == dotPos) System.out.print('.');
System.out.print(dstDigits[i - 1]);
}
运行结果:
95.123 12
548815620517731830194541.899025343415715973535967221869852721
0.4321 20
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
5.1234 15
43992025569.928573701266488041146654993318703707511666295476720493953024
6.7592 9
29448126.764121021618164430206909037173276672
98.999 10
90429072743629540498.107596019456651774561044010001
1.0100 12
1.126825030131969720661201
分享到:
相关推荐
poj 1001 Exponentiation用字符串操作的
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
三道几何题:hdu 1007、hdu 2289、poj 3714
如题所示,亲测可用。求高精度幂,不会的同学可以参考下,会做的同学可以给挑挑毛病!大家以代码会友!
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
北京大学online judge题号3601,解答及其实验报告
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
POJ1048,加强版的约瑟夫问题 难度中等
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
POJ14_MONI2.zip
poj两道题的c++实现。已经测试过可以通过oj
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
O(nlogn)凸包问题 poj2187
POJ1753 Flip Game题目完整代码及报告
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)