長整數計算中的數組運用思考
前言：本站為你精心整理了長整數計算中的數組運用思考范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。
摘要：本文闡述了利用數組實現長整數的算法
關鍵詞：數組算法VB
Abstract：Usearraytorealizetheprecisecalculateoflongteger
Keywords：arrayarithmeticVB
1、前言
我們都知道，計算機的一個最重要的功能就是進行科學計算。利用一些標準的數學函數和運算符號可以進行任何復雜的數學運算，數學運算對計算機來說當然也是十分輕松的事情。但由于計算機內存空間的限制等原因，計算機在計算很大的數據時，往往是用科學記數法表示。比如在VB6.0和其他的一些高級編程語言中，計算機所能處理的長整數的范圍是從-2,147,483,648到2,147,483,647。也就是說超出這個范圍的整數計算機就不能處理甚至不能識別了，那時計算機就會把數據轉換為科學記數法后再進行處理，比如1.398865E19，它表示1.398865乘以10的19次方。
假如我們需要知道兩個很大的整數相乘的精確結果呢？看起來是很難實現，因為計算機不支持很長的位數計算。然而，我們只要愿意去做，拿一張紙和一枝筆一步一步地進行人工計算，最后總能得到精確結果.我們能不能把我們人工計算的方法告訴計算機，讓計算機來完成這些計算工作呢？答案是肯定的。我們可以找出一個算法，讓計算機來模擬我們人工計算的方式進行計算，并且也不會超出計算機的整數計算范圍。本文就是通過對人工計算步驟的分析和模擬，最后找出一個算法，用高級語言實現長整數的精確計算。
2、人工計算步驟的分析和模擬
首先我們來分析一下人工進行乘法計算的過程。例如：347×78=27066
a347
b×78
c12776
c22429
c27066
為了便于說明，我們用a表示被乘數，用b表示乘數，用c表示結果。并且把個位數定義成第一位，十位數定義成第二位，依次類推。
人工計算過程為：
1.用b的第一位依次去乘a的各位，中間結果放在c1中，最后的c1要累加進結果c中，而且c1的第n位要累加到c的第n位。
2.用b的第二位依次去乘a的各位，中間結果放在c2中，最后的c2也要累加進結果c中，而且c2的第n位要累加在c的第n+1位。
3.假如b的位數很長的話，按上面的方式，用b的第m位依次去乘a的各位，中間結果放在cm中，最后的cm要累加進結果c中，而且cm的第n位要累加在c的第n+m-1中。
4.把c1、c2……cm都累加成結果c,最后c的值就是a乘b的積。
這里有一點要注意，當用b的第m位去乘a中的第k位時，有可能產生進位，這時的進位要累加在cm的第k+1位，也就是最后結果c中的n+m+k中。
3、程序算法：
現在我們來總結人工計算的算法，告訴計算機怎么按這個算法去計算。
前文已經提過，太長的整數計算機不能處理，所以我們首先要解決輸入和輸出的問題。我們知道，計算機不能處理很長的整數，但能處理很長的字符串。所以我們把輸入和輸出都轉換成數字型字符串來處理。同時字符串沒有數字計算的能力，所以我們還要把字符串分拆成一個一個的數字，這樣計算機就既能計算，又能處理很長的數據了。
我們定義三個可變數組a(),b()和c()，其中a()存放被乘數的每一位，最低位（個位數）放在a(1)中，同樣地，b()存放乘數的每一位，c()存放結果。
由于c1、c2、一直到最后一個中間結果最終都要累加進結果c中，所以我們在程序中可以直接把中間結果cm直接累加到結果c()中，實際上c()中的每一單元都是一個累加器，當一個單元c(n)中的結果大于9時，我們把c(n)對10的余數放在c(n)中，把c(n)整除10的結果累加進c(n+1)中，這樣就實現了進位處理。
用乘數b的每一位去乘被乘數a的各位時，我們設計一個循環，依次取出b的每一位。循環變量設為I，I從1遞增到b1(最高位)，步長為1。
用b的任何一位數m去乘a的各位數，我們也設計一個循環，依次取出a的各位。循環變量設為J，J從1遞增到a1(最高位)，步長為1。這樣利用這個雙重循環就可以計算到a和b的每一位。把結果都累加進c()中的相應位中，最后從高位到低位逐位輸出數組c就得到我們所要的長整數乘積。
源程序如下：
Dima(),b(),c()AsByte''''定義輸入和輸出數組
SubMain()
ts="整數乘法"
xx=InputBox("請輸入被乘數：",ts)
Ifxx=""ThenEnd
yy=InputBox("請輸入乘數",ts)
Ifyy=""ThenEnd
a1=Len(xx)''''取xx的位數
b1=Len(yy)''''取yy的位數
c1=a1+b1''''確定結果的最大位數
ReDima(a1),b(b1),c(c1)''''重定義數組
Fori=1Toa
a(i)=Mid(xx,a1-i+1,1)''''給數組a的每一位賦值
IfNotIsNumeric(a(i))Then''''檢查輸入的合法性
MsgBox"被乘數輸入錯誤",,ts
End
EndIf
Nexti
Fori=1Tob1
b(i)=Mid(yy,b1-i+1,1)''''給數組b的每一位賦值
IfNotIsNumeric(b(i))Then''''檢查輸入的合法性
MsgBox"乘數輸入錯誤",,ts
End
EndIf
Nexti
Fori=1Toc1''''結果數組c初始化
c(i)=0
Nexti
Fori=1Tob1''''取b中的每一位
Forj=1Toa1''''取a中的每一位
c(j+i-1)=c(j+i-1)+b(i)*a(j)''''相乘結果累加到c中的相應位
zz=c(j+i-1)
k=0
DoWhilezz>=10''''c中的每一位進位檢查
c(j+i+k-1)=zzMod10''''本位處理
c(j+i+k)=c(j+i+k)+zz10''''進位處理
zz=c(j+i+k)
k=k+1
Loop
Nextj
Nexti
zz=""
Fork=c1To1Step-1
Ifc(k)<>0ThenExitFor''''去掉結果中的前導0
Nextk
k=IIf(k<1,1,k)
Fori=kTo1Step-1
zz=zz+Trim(Str(c(i)))
Nexti
zz=xx+"X"+yy+"="+zz
ts="計算結果："+Str(a1)+"位X"+Str(b1)+"位結果為"+Str(k)+"位"
MsgBoxzz,,ts''''算式和結果輸出
End
EndSub
以上程序在vb6.0上編譯通過，并且能正確計算254位乘254位的長整數，輸出結果為508位長整數，精確到每一位。
5、結束語
理論上這個算法可以計算任意位數的整數乘法，本程序為了說明算法，只設計了一個模塊，沒有使用到窗體。使用的是vb中的標準輸入輸出函數。所以它能處理的結果位數位508位，因為超過254位的數據不能輸入了。要增加處理位數，只需要增加一個窗體，把輸入和輸出放在窗體上就可以了，實際上還可以用多個字符串連接，這樣能計算的位數就沒有限制了，而且當所處理的位數超過數組的最大定義范圍時還可以用多維數組。總之，只要采用一定的方法，可以計算任意長度的數字。
把本程序稍做修改，可以做成一個自定義函數，把兩個輸入參數作為函數的參數，在其他地方調用本函數就可以計算任何整數的階乘（n!），也可以計算任何整數的整數次方(n^m)。
本文給出的算法能給我們一種編程思路，也給我們一種啟示，即只要我們充分利用計算機的功能和特性，有些看來是不可能實現的計算處理，通過一定的轉換，我們總能找到解決的方法。
參考文獻：
VisualBasic6.0中文版實用參考手冊——語句、函數、對象與方法篇.晶辰工作室.電子工業出版社,1998
VisualBasic6.0中文版控件大全.李玉東，李罡，李雷.電子工業出版社,2000
數據結構.劉良觀，黃水松.武漢大學出版社,2000
