Exponentiation
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2475 Accepted Submission(s): 669
Problem 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.
感觉这种大数处理的题目越来越多了，但是也是越来越喜欢这种进位的算法了，还有数组，字符等的处理，感觉以后也会越来越熟练的。下面是我根据网上的代码做出了相应的详解，也是越来越了解该类的编程思维了吧。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int num[10], result[200], len, flag = 0, cnt1;
int char_to_int( char *s ) /*将字符型数组s中的数据复制到整型数组num中，且返回小数位数*/
{
int i, dian = 0, j, jihao;
memset(num,0,10*sizeof(int)); //将数组num内的各个数据设为0
len = strlen(s); //len为字符数组s的长度
//printf( "%s\n", s );
//printf( "%d\n", len );
cnt1 = 0; //cnt为0
for( j = len - 1; j >= 0; j-- )
if( s[j] == '.' ) //找到字符数组s中‘.’的地址，即为jihao
jihao = j;
for( j = len - 1; j > jihao; j-- )
if( s[j] != '0' ) //将j指向数组s中数据的起始位置，既有s【0~j】内存放的为有效数据
break;
//printf( "%d\n", j )
for( i = j; i >= 0; i--)
if( s[i] != '.' )
num[cnt1++] = s[i] - '0'; //将字符型数据转化为整型并放入num中，忽略小数点，并且从高位到低位的顺序为j-1~0；
else
dian = j - i;
/*for( i = 0; i < cnt1; i++ )
printf( "%d", num[i] );
printf( "\n%d\n", dian );*/
return dian; //返回有几位小数
}
int bignummulti( ) //将result数组乘上上num数组，调整好位数状态，将结果存入result数组
{
int i, j, temp[200];
memset(temp, 0 ,200*sizeof(int)); //初始化temp数组为零数组
for( i = 0; i < len; i++ ) //按乘法竖式来思考的到的是result数组与怒骂数组的乘积
for( j = 0; j < 200; j++ )
temp[i+j] += result[j] * num[i];
for( i = 0; i < 200; i++ ) //temp数组的进位操作
if( temp[i] >= 10 )
{
temp[i+1] += temp[i] / 10;
temp[i] = temp[i] % 10;
}
for( i = 0; i < 200; i++ ) //temp数组内的数据全部复制给result数组。
result[i] = temp[i];
return 0;
}
int main(int argc, char *argv[])
{
int n, dian, i, cnt, j;
char s[10];
memset(s,0,sizeof(s));
while( scanf( "%s %d", &s, &n )!=EOF )
{
dian = char_to_int( s ) * n;
memset(result,0,200 * sizeof(int));
result[0] = 1;
for( i = 1; i <= n; i++ ) //进行n次自乘，达到指数方程的解。
bignummulti();
for( i = 199; i >= 0; i-- ) //i和j分别指向高位的有效数字和低位的有效数字，为了防止多余的0输出
if( result[i] != 0 )
break;
for( j = 0; j < dian; j++ )
if( result[j] != 0 )
break;
if( dian > i ) //如果得到的结果是纯小数，需要在dian的前面补一个零，
{ //输出小数点，之后再补零，直到补到i之后再依次输出数字。
if( i == -1 )
printf( "0" );
else
printf( "." );
cnt = dian - (i + 1);
while( cnt-- )
printf( "0" );
for( ; i >= j; i-- )
printf( "%d", result[i] );
}
else //如果不是纯小数，依次输出每位i到j数字，
for( ; i >= j; i-- )
{ //如果遇到dian，输出小数点，如果没有遇到，则说明是整数。
if( i == dian-1 )
printf( "." );
printf( "%d", result[i] );
}
printf( "\n" );
}
//system("PAUSE");
return 0;
}
