大數(shù)乘方　趣味編程

[摘要]針對(duì)計(jì)算機(jī)精度位數(shù)的限制，編程制作乘方計(jì)算器工具，可以精確計(jì)算底數(shù)在10100以?xún)?nèi)，指數(shù)在108以?xún)?nèi)，結(jié)果在101000以?xún)?nèi)非負(fù)整數(shù)的乘方。

[關(guān)鍵詞]大數(shù)乘方 編程

中圖分類(lèi)號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597（2009）0220068－01

在歷屆的數(shù)學(xué)競(jìng)賽里，總會(huì)出現(xiàn)一些較大數(shù)字的乘方運(yùn)算，比如22005-22004。雖然這些題目都有巧妙的方法可以很快的得到答案，但無(wú)法把這些乘方運(yùn)算化為準(zhǔn)確的數(shù)字。競(jìng)賽后想用家用電腦驗(yàn)證，卻因?yàn)閿?shù)字太大超出計(jì)算范圍而無(wú)法計(jì)算。

算法：用初值1逐次乘輸入的底數(shù)，一共乘指數(shù)次，就是得數(shù)。

因?yàn)殡娔X算多位數(shù)之間的乘法是很慢的，而且如果得數(shù)很大還會(huì)受位數(shù)限制，所以我就把底數(shù)按位分成很多一位數(shù)，把每次做乘法后的結(jié)果也按位分成很多一位數(shù)，然后將這些一位數(shù)兩兩相乘，加到結(jié)果中相應(yīng)的各位上，然后如果某一位超過(guò)9，就留下它的個(gè)位并把十位及以后的數(shù)字加到后一位去（進(jìn)位）。

比如16*16，6*6=36，1*6=6，6*1=6，1*1=1，結(jié)果為1，（6+6=）12，36。個(gè)位進(jìn)3，結(jié)果變?yōu)?，15，6。十位進(jìn)1，得到2，5，6。

256*16，6*6=36，5*6=30，6*1=6，5*1=5，2*6=12，2*1=2，結(jié)果為2，（12+5=）17，（30+6=）36，36，個(gè)位進(jìn)3，結(jié)果變成2，17，39，6。十位進(jìn)3，變成2，20，9，6，百位進(jìn)2，變成4，0，9，6。

比如算22008，輸入2-2008，回車(chē)后不到1秒鐘就會(huì)打印出結(jié)果：

29，392，145，799，020，915，820，360，529，950，148，658，790，971，333，173，470，597，132，227，654，062，739，616，291，644，680，034，730，482，849，702，560，509，912，216，694，758，079，047，000，246，245，398，094，216，484，503，842，717，866，321，546，017，277，221，199，943，680，176，327，461，949，451，487，085，805，309，456，252，478，664，093，558，693，475，421，170，513，158，666，359，386，616，551，679，118，889，574，095，089，825，179，039，567，782，281，258，040，824，405，166，424，107，240，700，021，377，434，209，148，110，825，999，078，639，302，784，109，824，695，476，896，212，613，634，081，852，488，010，690，884，578，129，204，889，342，821，483，040，517，575，643，751，434，792，922，414，912，394，467，695，078，935，531，662，069，192，598，956，042，024，980，981，047，457，429，185，377，388，949，433，859，975，257，289，323，374，605，954，282，310，600，673，952，044，911，495，373，010，647，749，329，399，156，163，119，321，894，151，520，256。

另外的一些數(shù)字也經(jīng)過(guò)驗(yàn)證得到了正確答案，比如

甚至可以算出23000，時(shí)間都在一兩秒之內(nèi)。

這樣，以后考試時(shí)能夠用簡(jiǎn)便的計(jì)算來(lái)求解，考試后也能用家用電腦進(jìn)行窮舉驗(yàn)證，算出答數(shù)了。

附程序（已在VC環(huán)境下調(diào)試驗(yàn)證通過(guò)）：

#include＜stdio.h＞

#include＜string.h＞

int main(){

/**********定義，計(jì)算結(jié)果在1000位以下**********/

long int a[1000]，b[100]，c，a1[1000]，i，j，k，s，m；

char ch；

FILE *in；

in=fopen("POW.txt"，"w")；

/**********輸入底數(shù)，不超過(guò)100位**********/

for(s=0；；s++){

ch=getchar()；

b[s]=ch-48；

if(!(b[s]＞-1&&b[s]＜10)){

b[s]=0；

break；

}

}

/**********輸入指數(shù)，不超過(guò)8位**********/

scanf("%ld"，&c)；

/**********將結(jié)果初始化為1**********/

a[0]=1；

for(i=1；i＜1000；i++)a[i]=0；

/**********共乘指數(shù)次**********/

for(i=0；i＜c；i++){

/**********預(yù)備**********/

for(j=0；j＜1000；j++){

a1[j]=a[j]；

}

for(j=0；j＜1000；j++){

a[j]=0；

}

/**********將分解開(kāi)來(lái)的一位數(shù)兩兩相乘，加到結(jié)果的各位上**********/

for(j=0；j＜1000；j++){

for(k=s-1；k＞-1；k--){

a[j+s-1-k]=a[j+s-1-k]+a1[j]*b[k]；

}

}

/**********進(jìn)位**********/

m=0；

for(j=0；j＜1000；j++){

a[j]+=m；

m=(a[j]-a[j]%10)/10；

a[j]-=m*10；

}

}

/**********因?yàn)閟接下來(lái)要充當(dāng)分隔符，重置**********/

s=1；

/**********打印在屏幕上**********/

k=0；

for(i=999；i＞0；i--){

J=a[i]；

if(a[i]!=0&&k==0){k=1；s=2-(i%3)；}

if(k==1){printf("%d"，(int)j)；s++；}

if(s%3==0)printf("，")；

}

Printf("%d"，a[0])； printf(" ")；

/*如果想將結(jié)果打印在文件里，可以把這段改為：for(i=999；i＞0；i--){

j=a[i]；

If(a[i]!=0&&k==0){k=1；s=2-(i%3)；}

if(k==1){fprintf(in，"%d"，(int)j)；s++；}

if(s%3==0)fprintf(in，"，")；

}fprintf(in，"%d"，a[0])；

Fprintf(in，" ")； */

fclose(in)；

return(0)；

}

參考文獻(xiàn)：

[1]《聰明在于勤奮 天才在于積累》，華羅庚著，中國(guó)少年兒童出版社，P118-119.

[2]《C程序設(shè)計(jì)》，譚浩強(qiáng)著，清華大學(xué)出版社.

作者簡(jiǎn)介：

郭天魁，男，漢，浙江杭州，杭州建蘭中學(xué)，主要研究方向：程序綜合設(shè)計(jì)與數(shù)學(xué)證明。