1001 test
- 时间限制:
- 500ms
- 内存限制:
- 65536kB
- 描述
-
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.
- 输入
- 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.
- 输出
- 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.
- 样例输入
-
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
这是POJ正式题目的第1题，其实这道题目难度还是颇大的。尤其是紧跟在A+B这道熟悉POJ性质的题目后面，颇有点儿下马威的意思。分析这道题目：中文翻译过来也就是求任意浮点数的n次方精确值的问题，如样例给出的 95.123 的12 次方是
548815620517731830194541.899025343415715973535967221869852721
解题思路如下：
（1）绝对不能使用浮点数直接运算，因为就算是double类型，也不可能保存完整精确结果
（2）采用字符模拟CPU硬件乘法是基本解题思路
（3）采用ASCII码进行运算，如 ('6' -'0')*('5'-'0') = 30，30可以分解为 进位'3' 和 结果'0'
有了这样的解题思路那么我先给出一个解（由于初次尝试POJ的时候没有经验，这道题的这个解是查阅网络得来的，但已经验证通过）：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Len 200
char r[2*Len-1];
//大整数乘法：输入两个数字串，返回一个结果串（去除前导0的）
void lnmp(char *cs,char *bcs)
{
char cjr[Len][Len][2];
int i,j,k,l,cslen,bcslen,rlen,jw=0,temp,out=0;
cslen=strlen(cs);
bcslen=strlen(bcs);
rlen=cslen+bcslen-1;
//生成矩形表（三维数组）
for(i=cslen-1;i>=0;i--)
for(j=bcslen-1;j>=0;j--)
{
temp=(cs[i]-'0')*(bcs[j]-'0');
cjr[j][i][0]=temp/10;
cjr[j][i][1]=temp%10;
}
//求出结果（注意一个规律性的东西，从最后一位到最前一位，为矩形表里头的下标递减的数字之和）
for(l=rlen;l>=0;l--)
{
temp=jw;
for(i=cslen-1;i>=0;i--)
for(j=bcslen-1;j>=0;j--)
for(k=1;k>=0;k--)
if(l==i+j+k) temp=temp+cjr[j][i][k];
jw=temp/10;
r[l]=temp%10+'0';
}
for(l=0;l<rlen;l++)
if(r[l]!='0')
break;
if(l) for(i=l;i<=rlen+1;i++)
r[i-l]=r[i];
}
int main()
{
char R[Len];
int N;
int i,j,k,xsdws,temp,flag;
while(scanf("%s %d",R,&N)!=EOF)
{
i=1,flag=0;
temp=strlen(r);
for(i=0;i<temp;i++)
r[i]='\0';
//求小数点的位置
temp=strlen(R);
for(i=0;i<temp;i++)
if(R[i]=='.')
break;
//如果是小数，先转换成整数，后面再转换回来
if(i!=temp)
{
flag=1;
xsdws=(temp-i-1)*N;
for(j=i;j<=temp;j++)
R[j]=R[j+1];
}
//去除前导零，减少不必要的计算次数
for(i=0;i<temp;i++)
if(R[i]!='0')
break;
if(i) for(j=i;j<=temp;j++)
R[j-i]=R[j];
strcpy(r,R);
for(i=1;i<N;i++)
lnmp(r,R);
temp=strlen(r);
//如果是整数，直接输出结果，否则要考虑几种情况
if(!flag)
{
for(j=0;j<temp;j++)
putchar(r[j]);
}
//为小数时，需要考虑去掉末尾无效的零，如果位数不够，需要补充零，下面将出示比较典型的例子
else
{
i=temp-xsdws;
if(temp>xsdws)
{
i=temp-xsdws;
for(j=0;j<i;j++)
putchar(r[j]);
for(k=temp-1;k>=0;k--)
if(r[k]!='0')
break;
if(i<=k)
putchar('.');
for(j=i;j<k+1;j++)
putchar(r[j]);
}
else
{
i=xsdws-temp;
putchar('.');
for(j=0;j<i;j++)
putchar('0');
for(k=temp-1;k>=0;k--)
if(r[k]!='0')
break;
for(j=0;j<k+1;j++)
putchar(r[j]);
}
}
putchar('\n');
}
return 0;
}
我后来自己做了一次
//============================================================================
// Name : POJ-1001.cpp
//========================================
#include <iostream>
#include <algorithm>
using namespace std;
std::string multiply(const std::string& a, const std::string& b)
{
int a_len = a.length();
int b_len = b.length();
/*最终结果*/
std::string result;
/*设置初始结果，"0000...000",与b的位数相同*/
result.assign(b_len,'0');
/*临时结果、临时进位*/
int consq = 0;
int carry = 0;
for(int i=a_len-1; i>=0; --i)
{
for(int j=b_len-1; j>=0; --j)
{
consq = (a.at(i)-'0') * ( b.at(j)-'0')
+ (result.at(a_len-i+b_len-j-2)-'0')
+ carry ;
carry = 0;
if( consq >9 )
{
int temp = consq/10;
carry = temp;
consq = consq - carry*10;
}
result.at(a_len-i+b_len-j-2) = (consq+'0');
}
result.push_back(carry+'0');
carry = 0;
}
/*处理最终结果*/
if( result.at(a_len+b_len-1) == '0')
{ result.erase(result.length()-1,1); }
/*翻转得到最终结果*/
for(int i=0; i<result.length()/2; ++i)
{
char tmp = result.at(i);
result.at(i) = result.at(result.length()-1-i);
result.at(result.length()-1-i) = tmp;
}
return result;
};
int main()
{
string R;
int n;
while(cin>>R>>n)
{
string result = "1";
int pos = R.find(".");
if( pos < 0)/*R是整数*/
{
while( --n >= 0 )
result = multiply(R,result);
}
else /*R是小数*/
{
R.erase(pos,1);
int dot_num = R.length()-pos;
int res_dot = dot_num * n;
while( --n >= 0 )
result = multiply(R,result);
int dot_pos = result.length()-res_dot;
while( dot_pos <= 0 )
{
result.insert(dot_pos,"0");
dot_pos++;
}
result.insert(dot_pos,".");
/*去掉后缀不必要的0*/
while( result.at(result.length()-1) =='0')
result.erase(result.length()-1,1);
}
/*去掉不必要的0*/
while( result.at(0) =='0')
result.erase(0,1);
cout<<result.c_str()<<endl;
}
return 0;
}
但不知道为什么总时wrong answer，我检查过和Accept的解法的输出，应该是一致的，但就是通不过，汗……做个POJ的同学指教一下吧，求高手！！！