POJ-1001 Exponentiation&很大的数相乘高精度数组

Exponentiation

Time Limit: 500MS Memory Limit: 10000KTotal Submissions: 190785 Accepted: 45785

Description

Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.  This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

Input

The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

Output

The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.

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

这个数字，那么大，哪怕是longlonglonglong来个十个八个的也不够用，那这样的，用java语言自带的+-*/那肯定不行，如果行的话考这个也没什么意思了。

所以只能用数组存储。

其实吧，我觉得，要和小学的竖式一样，就无敌了。

核心思想是：

假如两个数相乘

图有点乱，大意就是，int a[] 存储第一个数组，每个位存一个数。int b[]第二个

用int c[]，存储a * b 的值

那么就会发现一个规律，c[1] 是不是等于a[1] * b[1].

c[2]是不是等于a[1]*b[2]+a[2]*b[1].看我在图上画的线，c[3] = a[3]*a[1] + a[1]*b[3];

这样其实就可以把这个值存储起来了

但是一想

着c存的啥呀，这不是162 162 .。。。。

这怎么输出呀。

不用着急，咱们竖式不就满十进一嘛。

如果当前是81，那应该进8个，自己留一个。

也就是说，一个循环判断，从低往高位，满十进一。

c[i+1] += c[i]/10.

c[i] %10;

就行了。这就是算法的核心。

那a[0]位存啥，一个萝卜一个坑，0位拿来存小数点的位置。

import java.util.Scanner; class BigNumber{ int[] result; int[] value; int len; BigNumber(int[] result,int[] value){ this.result = result; this.value = value; } public int[] getResult() { return result; } public void setResult(int[] result) { this.result = result; } } public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s; while(sc.hasNext()) { int[] a = new int[100]; s = sc.next(); //6位的小数 for(int i=s.length()-1,k=0;i>=0;i--) { if(Character.isDigit(s.charAt(i))) { a[++k] = s.charAt(i) - '0'; }else if(s.charAt(i) == '.') { a[0] = k; } } int[] b = filter(a); int power = sc.nextInt(); sc.nextLine(); BigNumber bg = new BigNumber(b,b); while(true) { power--; if(power == 0) break; bg.setResult(mulp(bg.result,bg.value)); } int[] result = filter(bg.getResult()); int len = getLen(result); power = result[0]; if(power > len ) { System.out.print("."); for(int i=0;i<power-len;i++) { System.out.print("0"); } } for(int i=len,count=0;i>=1;i--) { System.out.print(result[i]); if(++count == len-power && power != 0) System.out.print("."); } if(getLen(result) == 0 && result[0] == 0) { System.out.print("0"); } System.out.print("\n"); } } public static int[] mulp(int[] a,int[] b) { int[] c = new int[100]; c[0] = a[0]+b[0]; for(int i=1;i<=getLen(a);i++) { for(int j=1;j<=getLen(b);j++) { c[i+j-1] += a[i]*b[j]; } } for(int i=1;i<=getLen(c);i++) { if(c[i]>9) { c[i+1] += c[i]/10; c[i] %= 10; } } return c; } public static int getLen(int[] a) { int i = a.length-1; while(a[i] == 0 && i > 0) { i--; } return i; } public static int[] filter(int[] a) { int k = 0; for(int i=1;i<=getLen(a);i++) { if(a[i] == 0) { if(a[0] == 0) break; a[0]--; k++; }else { break; } } if(k != 0) { int l = getLen(a); for(int i=k+1;i<=l;i++) { a[i-k] = a[i]; } for(int i=l;i>l-k;i--) { a[i] = 0; } } if(getLen(a) == 0) { a[0] = 0; } return a; } }

思路是很简单的，但是这里可能会有几个坑点。

多测几组数据

0.0000 2

1.0000 2

0.0001 2