首页
会员中心
到顶部
到尾部
计算机

巧用数组实现长整数的精确计算

时间:2020/10/27 9:25:50  作者:  来源:  查看:42  评论:0
<
内容摘要:摘要:本文阐述了利用数组实现长整数的算法关键词:数组算法VBAbstract:UsearraytorealizetheprecisecalculateoflongtegerKeywords:arrayarithmeticVB1、前言我们都知道,计算机的一个最重要的功能就是进行科学...

摘要:本文阐述了利用数组实现长整数的算法

关键词:数组算法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
nbsp;'定义输入和输出数组
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) zz\10'进位处理
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中文版实用参考手册——语句、函数、对象与方法篇.晶辰工作室.电子工业出版社,1998VisualBasic6.0中文版控件大全.李玉东,李罡,李雷.电子工业出版社,2000数据结构.刘良观,黄水松.武汉大学出版社,2000

Tags:



相关评论
闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳婀遍埀顒傛嚀鐎氼參宕崇壕瀣ㄤ汗闁圭儤鍨归崐鐐烘偡濠婂嫮鐭婇棁澶愭煛瀹ュ骸骞楅柣鎾崇箰閳规垿鎮欓棃娑楀濠电偛鎳庡Λ婵嬪蓟濞戙垹围闁告侗鍙庢导鍐⒑閸濆嫯顫﹂柛濠冾殘閸掓帒鈻庨幋鐐茬/闂侀潧枪閸婃銇欓搹顐ょ瘈闁汇垽娼ф禒婊堟煙閾忣偄濮堥柟渚垮姂瀹曞綊顢曢妶鍌涙暤濠电姷鏁告慨鏉懨洪妶鍛函闂傚倷鑳舵灙闁哄牜鍓熼幆宀勵敊閻e瞼褰鹃梺鍝勬储閸ㄦ椽鍩涢幒鎳ㄥ綊鏁愭径妯活棖婵炴垶鎹佺亸娆戞閹烘鍙撴い鎾跺Х閻撴捇姊虹拠鈥虫灍闁挎碍銇勯锝囩畺婵炵厧绻橀崺锟犲礃椤忓懏顔旈梻鍌氬€烽懗鍓佸垝椤栨凹娼栧┑鐘宠壘閸屻劎鎲搁弮鍫濈畺闁绘劕鎼崹鍌涖亜閹邦喖小缂併劌顭峰娲偡閻楀牊鍎撳┑鈽嗗亝椤ㄥ棛绮嬪鍡愬亝闁告劏鏂侀幏鐑樼箾閺夋垵鎮戦柣鐔濆洤绀嗗ù鐓庣摠閻撴洟鏌曡箛銉х?闁告瑢鍋撻梻浣虹《閺呮繈宕戦妶澶屽祦閻庯綆鍠楅崑鎰亜閹板灚绶氬瑙勬礋濮婃椽骞愭惔锝囩暤婵°倗濮撮幉锛勭矉瀹ュ應鍫柛蹇曞Х閹虫捇銈导鏉戠妞ゅ繐鏌婇妸銉㈡斀妞ゆ梻銆嬫Λ姘箾閸滃啰鎮兼俊鍙夊姍楠炴帡骞婂畷鍥ф灈闁圭厧缍婇弻鍛槈濞嗘ɑ鏅i梻浣筋嚙妤犳悂宕㈠⿰鍫濈;闁瑰墽绮悡銉︾節闂堟稒顥為柛锝嗘そ閺屾稓鈧絻鍔岄崝姘舵煃鐟欏嫬鐏撮柛銊﹀劤閻g兘宕惰閸樹粙姊绘担绛嬪殐闁哥噥鍋婂畷鎯邦樄闁哥偛鐖煎娲濞戞氨鐤勯梺绯曟櫅鐎氭澘鐣烽娑欏劅闁靛⿵鑵归幏缁樼箾鏉堝墽鎮奸柛搴涘€濆畷鐢稿焵椤掆偓椤啴濡堕崱妯侯槱闂佸憡鐟ラ崯顐︽偩閻戣棄绠i柨鏃囨閳ь剛鍏橀弻娑樷攽閸℃浼€闂佷紮缍佺粻鏍ь潖濞差亜绀堥柟缁樺笂缁ㄦ挳姊虹粙鍨劉闁绘搫绻濋獮鍐灳閺傘儲鐎婚梺瑙勫劤椤曨參宕㈤柆宥嗏拺闁荤喐澹嗛幗鐘绘煟閻旀潙鍔﹂柛鈹惧亾濡炪倖甯婇懗鑸垫櫠闁秵鐓冪憸婊堝礈濮樿埖鍋勬い鎺戝缁狀垶鏌ㄩ悤鍌涘...
闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳婀遍埀顒傛嚀鐎氼參宕崇壕瀣ㄤ汗闁圭儤鍨归崐鐐烘偡濠婂嫮鐭婇棁澶愭煛瀹ュ骸骞楅柣鎾崇箰閳规垿鎮欓棃娑楀濠电偛鎳庡Λ婵嬪蓟濞戙垹围闁告侗鍙庢导鍐⒑閸濆嫯顫﹂柛濠冾殘閸掓帒鈻庨幋鐐茬/闂侀潧枪閸婃銇欓搹顐ょ瘈闁汇垽娼ф禒婊堟煙閾忣偄濮堥柟渚垮姂瀹曞綊顢曢妶鍌涙暤濠电姷鏁告慨鏉懨洪妶鍛函闂傚倷鑳舵灙闁哄牜鍓熼幆宀勵敊閻e瞼褰鹃梺鍝勬储閸ㄦ椽鍩涢幒鎳ㄥ綊鏁愭径妯活棖婵炴垶鎹佺亸娆戞閹烘鍙撴い鎾跺Х閻撴捇姊虹拠鈥虫灍闁挎碍銇勯锝囩畺婵炵厧绻橀崺锟犲礃椤忓懏顔旈梻鍌氬€烽懗鍓佸垝椤栨凹娼栧┑鐘宠壘閸屻劎鎲搁弮鍫濈畺闁绘劕鎼崹鍌涖亜閹邦喖小缂併劌顭峰娲偡閻楀牊鍎撳┑鈽嗗亝椤ㄥ棛绮嬪鍡愬亝闁告劏鏂侀幏鐑樼箾閺夋垵鎮戦柣鐔濆洤绀嗗ù鐓庣摠閻撴洟鏌曡箛銉х?闁告瑢鍋撻梻浣虹《閺呮繈宕戦妶澶屽祦閻庯綆鍠楅崑鎰亜閹板灚绶氬瑙勬礋濮婃椽骞愭惔锝囩暤婵°倗濮撮幉锛勭矉瀹ュ應鍫柛蹇曞Х閹虫捇銈导鏉戠妞ゅ繐鏌婇妸銉㈡斀妞ゆ梻銆嬫Λ姘箾閸滃啰鎮兼俊鍙夊姍楠炴帡骞婂畷鍥ф灈闁圭厧缍婇弻鍛槈濞嗘ɑ鏅i梻浣筋嚙妤犳悂宕㈠⿰鍫濈;闁瑰墽绮悡銉︾節闂堟稒顥為柛锝嗘そ閺屾稓鈧絻鍔岄崝姘舵煃鐟欏嫬鐏撮柛銊﹀劤閻g兘宕惰閸樹粙姊绘担绛嬪殐闁哥噥鍋婂畷鎯邦樄闁哥偛鐖煎娲濞戞氨鐤勯梺绯曟櫅鐎氭澘鐣烽娑欏劅闁靛⿵鑵归幏缁樼箾鏉堝墽鎮奸柛搴涘€濆畷鐢稿焵椤掆偓椤啴濡堕崱妯侯槱闂佸憡鐟ラ崯顐︽偩閻戣棄绠i柨鏃囨閳ь剛鍏橀弻娑樷攽閸℃浼€闂佷紮缍佺粻鏍ь潖濞差亜绀堥柟缁樺笂缁ㄦ挳姊虹粙鍨劉闁绘搫绻濋獮鍐灳閺傘儲鐎婚梺瑙勫劤椤曨參宕㈤柆宥嗏拺闁荤喐澹嗛幗鐘绘煟閻旀潙鍔﹂柛鈹惧亾濡炪倖甯婇懗鑸垫櫠闁秵鐓冪憸婊堝礈濮樿埖鍋勬い鎺戝缁狀垶鏌ㄩ悤鍌涘...
广告联系QQ:45157718 点击这里给我发消息 电话:13516821613 杭州余杭东港路118号雷恩国际科技创新园  网站技术支持:黄菊华互联网工作室 浙ICP备06056032号