高级算法与数据结构的解题报告.doc

高级算法与数据结构

PKU1001Exponentiation
解题报告

老师：
学院：
专业：
姓名：
学号：

Exponentiation
TimeLimit:500MSMemoryLimit:10000K

Description
Problemsinvolvingthecomputationofexactvaluesofverylargemagnitudeandprecisionarecommon.Forexample,thecomputationofthenationaldebtisataxingexperienceformanycomputersystems.
ThisproblemrequiresthatyouwriteaprogramtocomputetheexactvalueofRnwhereRisarealnumber(0.0<R<99.999)andnisanintegersuchthat0<n<=25.

Input
TheinputwillconsistofasetofpairsofvaluesforRandn.TheRvaluewilloccupycolumns1through6,andthenvaluewillbeincolumns8and9.

Output
TheoutputwillconsistofonelineforeachlineofinputgivingtheexactvalueofR^n.Leadingzerosshouldbesuppressedintheoutput.Insignificanttrailingzerosmustnotbeprinted.Don'tprintthedecimalpointiftheresultisaninteger.

SampleInput
548815620517731830194541.899025343415715973535967221869852721.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

SampleOutput
95.12312
0.432120
5.123415
6.75929
98.99910
1.010012

Hint
Ifyoudon'tknowhowtodeterminewheatherencountedtheendofinput:
sisastringandnisaninteger

Source
EastCentralNorthAmerica1988

语言:c++

#include<iostream>
#include<stdlib.h>
usingnamespacestd;
voidmult(chara[],charb[],chars[])
{
inti,j,k=0,alen,blen,sum=0,res[201][201]={0},flag=0;
charresult[201];
alen=strlen(a);blen=strlen(b);

for(i=0;i<alen;i++)
for(j=0;j<blen;j++)res[i][j]=(a[i]-'0')*(b[j]-'0');

for(i=alen-1;i>=0;i--)
{
for(j=blen-1;j>=0;j--)sum=sum+res[i+blen-j-1][j];
result[k]=sum%10;
k=k+1;
sum=sum/10;
}

for(i=blen-2;i>=0;i--)
{
for(j=0;j<=i;j++)sum=sum+res[i-j][j];
result[k]=sum%10;
k=k+1;
sum=sum/10;
}
if(sum!=0){result[k]=sum;k=k+1;}

for(i=0;i<k;i++)result[i]+='0';
for(i=k-1;i>=0;i--)s[i]=result[k-1-i];
s[k]='\0';

while(1)
{
if(strlen(s)!=strlen(a)&&s[0]=='0')