巧用數(shù)組實(shí)現(xiàn)長整數(shù)的精確計(jì)算

巧用數(shù)組實(shí)現(xiàn)長整數(shù)的精確計(jì)算

摘要：本文闡述了利用數(shù)組實(shí)現(xiàn)長整數(shù)的算法

關(guān)鍵詞：數(shù)組算法VB

Abstract：Usearraytorealizetheprecisecalculateoflongteger

Keywords：arrayarithmeticVB前言

我們都知道，計(jì)算機(jī)的一個(gè)最重要的功能就是進(jìn)行科學(xué)計(jì)算。利用一些標(biāo)準(zhǔn)的數(shù)學(xué)函數(shù)和運(yùn)算符號可以進(jìn)行任何復(fù)雜的數(shù)學(xué)運(yùn)算，數(shù)學(xué)運(yùn)算對計(jì)算機(jī)來說當(dāng)然也是十分輕松的事情。但由于計(jì)算機(jī)內(nèi)存空間的限制等原因，計(jì)算機(jī)在計(jì)算很大的數(shù)據(jù)時(shí)，往往是用科學(xué)記數(shù)法表示。比如在和其他的一些高級編程語言中，計(jì)算機(jī)所能處理的長整數(shù)的范圍是從-2,147,483,648到2,147,483,647。也就是說超出這個(gè)范圍的整數(shù)計(jì)算機(jī)就不能處理甚至不能識別了，那時(shí)計(jì)算機(jī)就會把數(shù)據(jù)轉(zhuǎn)換為科學(xué)記數(shù)法后再進(jìn)行處理，比如，它表示乘以10的19次方。

假如我們需要知道兩個(gè)很大的整數(shù)相乘的精確結(jié)果呢？看起來是很難實(shí)現(xiàn)，因?yàn)橛?jì)算機(jī)不支持很長的位數(shù)計(jì)算。然而，我們只要愿意去做，拿一張紙和一枝筆一步一步地進(jìn)行人工計(jì)算，最后總能得到精確結(jié)果.我們能不能把我們?nèi)斯び?jì)算的方法告訴計(jì)算機(jī)，讓計(jì)算機(jī)來完成這些計(jì)算工作呢？答案是肯定的。我們可以找出一個(gè)算法，讓計(jì)算機(jī)來模擬我們?nèi)斯び?jì)算的方式進(jìn)行計(jì)算，并且也不會超出計(jì)算機(jī)的整數(shù)計(jì)算范圍。本文就是通過對人工計(jì)算步驟的分析和模擬，最后找出一個(gè)算法，用高級語言實(shí)現(xiàn)長整數(shù)的精確計(jì)算。

2、人工計(jì)算步驟的分析和模擬

首先我們來分析一下人工進(jìn)行乘法計(jì)算的過程。例如：347×78=27066

a347

b×78

c12776

c22429

c27066

為了便于說明，我們用a表示被乘數(shù)，用b表示乘數(shù)，用c表示結(jié)果。并且把個(gè)位數(shù)定義成第一位，十位數(shù)定義成第二位，依次類推。

人工計(jì)算過程為：

1.用b的第一位依次去乘a的各位，中間結(jié)果放在c1中，最后的c1要累加進(jìn)結(jié)果c中，而且c1的第n位要累加到c的第n位。

2.用b的第二位依次去乘a的各位，中間結(jié)果放在c2中，最后的c2也要累加進(jìn)結(jié)果c中，而且c2的第n位要累加在c的第n+1位。

3.假如b的位數(shù)很長的話，按上面的方式，用b的第m位依次去乘a的各位，中間結(jié)果放在cm中，最后的cm要累加進(jìn)結(jié)果c中，而且cm的第n位要累加在c的第n+m-1中。

4.把c1、c2……cm都累加成結(jié)果c,最后c的值就是a乘b的積。

這里有一點(diǎn)要注意，當(dāng)用b的第m位去乘a中的第k位時(shí)，有可能產(chǎn)生進(jìn)位，這時(shí)的進(jìn)位要累加在cm的第k+1位，也就是最后結(jié)果c中的n+m+k中。

3、程序算法：

現(xiàn)在我們來總結(jié)人工計(jì)算的算法，告訴計(jì)算機(jī)怎么按這個(gè)算法去計(jì)算。

前文已經(jīng)提過，太長的整數(shù)計(jì)算機(jī)不能處理，所以我們首先要解決輸入和輸出的問題。我們知道，計(jì)算機(jī)不能處理很長的整數(shù)，但能處理很長的字符串。所以我們把輸入和輸出都轉(zhuǎn)換成數(shù)字型字符串來處理。同時(shí)字符串沒有數(shù)字計(jì)算的能力，所以我們還要把字符串分拆成一個(gè)一個(gè)的數(shù)字，這樣計(jì)算機(jī)就既能計(jì)算，又能處理很長的數(shù)據(jù)了。

我們定義三個(gè)可變數(shù)組a(),b()和c()，其中a()存放被乘數(shù)的每一位，最低位放在a(1)中，同樣地，b()存放乘數(shù)的每一位，c()存放結(jié)果。

由于c1、c2、一直到最后一個(gè)中間結(jié)果最終都要累加進(jìn)結(jié)果c中，所以我們在程序中可以直接把中間結(jié)果cm直接累加到結(jié)果c()中，實(shí)際上c()中的每一單元都是一個(gè)累加器，當(dāng)一個(gè)單元c(n)中的結(jié)果大于9時(shí)，我們把c(n)對10的余數(shù)放在c(n)中，把c(n)整除10的結(jié)果累加進(jìn)c(n+1)中，這樣就實(shí)現(xiàn)了進(jìn)位處理。

用乘數(shù)b的每一位去乘被乘數(shù)a的各位時(shí)，我們設(shè)計(jì)一個(gè)循環(huán)，依次取出b的每一位。循環(huán)變量設(shè)為I，I從1遞增到b1(最高位)，步長為1。

用b的任何一位數(shù)m去乘a的各位數(shù)，我們也設(shè)計(jì)一個(gè)循環(huán)，依次取出a的各位。循環(huán)變量設(shè)為J，J從1遞增到a1(最高位)，步長為1。這樣利用這個(gè)雙重循環(huán)就可以計(jì)算到a和b的每一位。把結(jié)果都累加進(jìn)c()中的相應(yīng)位中，最后從高位到低位逐位輸出數(shù)組c就得到我們所要的長整數(shù)乘積。

源程序

Dima(),b(),c()AsByte‘定義輸入和輸出數(shù)組

SubMain()

ts="整數(shù)乘法"

xx=InputBox("請輸入被乘數(shù)：",ts)

Ifxx=""ThenEnd

yy=InputBox("請輸入乘數(shù)",ts)

Ifyy=""ThenEnd

a1=Len(xx)‘取xx的位數(shù)

b1=Len(yy)‘取yy的位數(shù)

c1=a1+b1‘確定結(jié)果的最大位數(shù)

ReDima(a1),b(b1),c(c1)‘重定義數(shù)組

Fori=1Toa

a(i)=Mid(xx,a1-i+1,1)‘給數(shù)組a的每一位賦值

IfNotIsNumeric(a(i))Then‘檢查輸入的合法性

MsgBox"被乘數(shù)輸入錯(cuò)誤",,ts

End

EndIf

Nexti

Fori=1Tob1

b(i)=Mid(yy,b1-i+1,1)‘給數(shù)組b的每一位賦值

IfNotIsNumeric(b(i))Then‘檢查輸入的合法性

MsgBox"乘數(shù)輸入錯(cuò)誤",,ts

End

EndIf

Nexti

Fori=1Toc1‘結(jié)果數(shù)組c初始化

c(i)=0

Nexti

Fori=1Tob1‘取b中的每一位

Forj=1Toa1‘取a中的每一位

c(j+i-1)=c(j+i-1)+b(i)*a(j)‘相乘結(jié)果累加到c中的相應(yīng)位

zz=c(j+i-1)

k=0

DoWhilezz=10‘c中的每一位進(jìn)位檢查

c(j+i+k-1)=zzMod10‘本位處理

c(j+i+k)=c(j+i+k)+zz“10‘進(jìn)位處理

zz=c(j+i+k)

k=k+1

Loop

Nextj

Nexti

zz=""

Fork=c1To1Step-1

Ifc(k)0ThenExitFor‘去掉結(jié)果中的前導(dǎo)0

Nextk

k=IIf(k1,1,k)

Fori=kTo1Step-1

zz=zz+Trim(Str(c(i)))

Nexti

zz=xx+"X"+yy+"="+zz

ts="計(jì)算結(jié)果："+Str(a1)+"位X"+Str(b1)+"位結(jié)果為"+Str(k)+"位"

MsgBoxzz,,ts‘算式和結(jié)果輸出

End

EndSub

以上程序在上編譯通過，并且能正確計(jì)算254位乘254位的長整數(shù)，輸出結(jié)果為508位長整數(shù)，精確到每一位。

5、結(jié)束語

理論上這個(gè)算法可以計(jì)算任意位數(shù)的整數(shù)乘法，本程序?yàn)榱苏f明算法，只設(shè)計(jì)了一個(gè)模塊，沒有使用到窗體。使用的是vb中的標(biāo)準(zhǔn)輸入輸出函數(shù)。所以它能處理的結(jié)果位數(shù)位508位，因?yàn)槌^254位的數(shù)據(jù)不能輸入了。要增加處理位數(shù)，只需要增加一個(gè)窗體，把輸入和輸出放在窗體上就可以了，實(shí)際上還可以用多個(gè)字符串連接，這樣能計(jì)算的位數(shù)就沒有限制了，而且當(dāng)所處理的位數(shù)超過數(shù)組的最大定義范圍時(shí)還可以用多維數(shù)組。總之，只要采用一定的方法，可以計(jì)算任意長度的數(shù)字。

把本程序稍做修改，可以做成一個(gè)自定義函數(shù)，把兩個(gè)輸入?yún)?shù)作為函數(shù)的參數(shù)，在其他地方調(diào)用本函數(shù)就可以計(jì)算任何整數(shù)的階乘，也可以計(jì)算任何整數(shù)的整數(shù)次方(n^m)。

本文給出的算法能給我們一種編程思路，也給我們一種啟示，即只要我們充分利用計(jì)算機(jī)的功能和特性，有些看來是