算法大整数的四则运算

1、姓名： 胡双兴 学号：090610213 班级：090413一：实验题目大整数加法1问题分析：处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。2:数学模型输入时以字符串的形式表示大整数。采用数组存放大整数，每位数组存放6位。Num1,num2存放两个加数。Hen存放和，jin 表示进位。则 heni二num1i+num2i+jin, 此时的jin表示的是来自低位的进位。若heni超过 1000000,则 heni修正为 heni-1000000, 且 jin=1。.3：算法策略的选择采用蛮力算法4:程序流程图5：算法时间复杂度与空间复杂度（推导过程）6:程序实现(注释)vo

2、id CBigCou ntDlg:Cha ngeTol nt() / 将字符串存储的大整数转化为整形数组存储每位数组存储6位UpdateData();in t Ien_op1,len_op2;存放两个字符串长度且Ien_op1存放较长字符串的长度len _op1=m_operate1.GetLe ngth();len _op2=m_operate2.GetLe ngth();if(len_op1<len_op2)若 m_operate1 长度小于 m_operate2 长度交换两字符串CStri ng temp;temp=m_operate1;m_operate1=m_operate2;

3、m_operate2=temp;int hu;hu=le n_op1;len _op1=le n_op2;len _op2=hu;m1=len_op1/6; /ml 是 m_operate1 所用数组的长度if(len_op1%6!=0)m1+;m2=len_op2/6; /m2 是 m_operate2 所用数组的长度if(len_op2%6!=0)m2+;int t1=0;for(int i=len_op1-1;i>0;i=i-6)/数组的每个元素存放6个字符串if(i>5) /numl中存放较长的字符串 m_operate1nu m1t1=atoi(m_operate1.Mi

4、d(i-5,6);t1+;elsebreak;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(i nt j=len_op2-1;j>0;j=j-6)num2存放字符串 m_operate2if(j>5)nu m2t2=atoi(m_operate2.Mid(j-5,6);t2+;elsebreak;if(t2!=m2)nu m2t2=atoi(m_operate2.Mid(0,j+1);void CBigCou ntDlg:O nButto nAdd()int jin ,i,j; /jin存储进位CStri ng a

5、a,bb; /存放输出的值aa=bb=""jin=0;for( i=0;i<100;i+)/初始化nu m1i=nu m2i=he ni=0;Cha ngeTol nt(); /将字符型大整数转化为整数数组存储for(j=0;j<m1;j+)/从低位开始相加每位都当成有进位处理he nj=n um1j+nu m2j+ji n-1000000;if(he nj>=0) / 有进位jin=1;else /没有进位修正henj的值henj=nu m1j+nu m2j+j in;jin=0;if(ji n=1) /处理最高位的进位hen j=1;elsej-;/输

6、出结果aa.Format("%d",he nj);for(int l=j-1;l>=0;l-)if(he n l<10)bb.Format("%d",he nl); bb="00000"+bb;else if(he n l<100) bb.Format("%d",he n I); bb="0000"+bb;else if(he n l<1000)bb.Format("%d",he n I); bb="000"+bb;else if(

7、he n l<10000)bb.Format("%d",he n I); bb="00"+bb;else if(he n l<100000)bb.Format("%d",he n I);bb="0"+bb;elsebb.Format("%d",he nl);aa+=bb;MessageBox(aa);.学习帮手.7:使用方法，如如何启动程序，关闭程序，对输入输出要求可输入两个非负的大整数进行运算。8测试数据数据及结果说明（正确数据以及非正确数据）正确数据:1234E6T999S7S5

8、4321123456739错误数据:HiSiseT说明：没有在输入大整数时判断正负。9:总结（如调试过程中遇到的问题算法策略；算法的方法）6位时如输出时按照，存放和的数组hen,由高位到低位输出，数组中除最高位的一位并没有达到 123应该输出000123而不是123.。解决方法判断大小在数前加 0。二：实验题目大整数减法1:问题分析处理多位整数的减法，这些整数无法在计算机硬件允许的范围内表示和处理。2:数学模型输入时以字符串的形式表示大整数。采用数组存放大整数，每位数组存放6位。将输入的两个大整数处理为位数较多的一个减去位数较少的一个，若被减数比减数位 数少结果前面加“-”。Num1,num2

9、存放被减数和减数。cha存放差，jie表示借位。则chai=num1i-num2i-jie;jie为低位是否向此位借位。若 chai<0 则修正为chai+=1000000;且 jie=1。3：算法策略的选择：采用蛮力法。4：程序流程图5：算法时间复杂度与空间复杂度（推导过程）6:程序实现(注释)void CBigCou ntDlg:O nButt on Cut()/实现两个大整数的减法for(i nt q=O;q<1OO;q+)nu m1q =nu m2q=chaq=0;UpdateData();bool comp=0; / 若 comp为 0 贝U m_operate1 大于或

10、等于 m_oprate2 若为 1 则相 反int len _op1,le n_ op2;len_ op1=m_operate1.GetLe ngth();len _op2=m_operate2.GetLe ngth();if(len_op2>len_op1)comp=1;Cha ngeTol nt();in t jie=0;for(int i=0;i<m1;i+)chai二nu m1i-nu m2i-jie;if(chai<0&&(i!=m1-1)jie=1;chai+=1000000;elsejie=0;int begin=0; /从高位到低位找到cha中

11、第一位部位0的下标几位beginfor(i nt p=99;p>=0;p-)if(chap!=0)begi n二p;break;CStri ng aa,bb;aa.Format("%d",chabeg in );for(int 匸begin-1;l>=0;l-)if(chal<10)bb.Format("%d",chal);bb="00000"+bb;else if(chal<100)bb.Format("%d",chal); bb二"OOOO"+bb;else if(c

12、hal<1000)bb.Format("%d",chal); bb="000"+bb;else if(chal<10000)bb.Format("%d",chal); bb="00"+bb;else if(chal<100000)bb.Format("%d",chal); bb="0"+bb;elsebb.Format("%d",chal);aa+=bb;if(comp)aa二"-"+aa; MessageBox(aa

13、);7:使用方法，如如何启动程序，关闭程序，对输入输出要求输入两个非负数的大整数的减法。&测试数据数据及结果说明(正确数据以及非正确数据)正确数据：错误数据:-1234:567BigCount凶-2123 4E&11111111说明：未考虑负数大整数相减的情况。9:总结(如调试过程中遇到的问题算法策略；算法的方法)相减的结果课能为 0,但结果是存在数组中的，判断是否为 0应从最高为一次检验数组中的每一位。.学习帮手.三：实验题目大数乘法1问题分析处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。 考虑，大整数与正常较小的数相乘，和两个大整数相乘。2:数学模型输

14、入时以字符串的形式表示大整数。采用长整形数组存放大整数，每位数组存放4位。Num1,num2存放两个加数。ji存放积。Num2数组中的元素依次从低位 至雋位（相应大整数的低位到高位）当成正常整数与数组num1的每一位相乘。jin 表示进位。结果存放在buffer数组中。将buffer中的元素乘以相应的权值赋值 给ji数组。3：算法策略的选择采用蛮力法4:程序流程图5：算法时间复杂度与空间复杂度(推导过程)6:程序实现(注释)void CBigCou ntDlg:Cha ngeTol nt4()/将字符串表示的长整数转化为长整形数组表示，每位数组存放UpdateData();in t le n_

15、op1,le n_op2;len _op仁m_operate1.GetLe ngth();len _op2=m_operate2.GetLe ngth();if(len_op1<len_op2)CStri ng temp;temp=m_operate1;m_operate1=m_operate2;m_operate2=temp;int hu;hu=le n_op1;len _op1=le n_op2;len _op2=hu;m1=le n_op1/4;if(len_op1%4!=0)m1+;m2=len_op2/4;if(len_op2%4!=0)m2+;int t1=0;for(int

16、 i=len_op1-1;i>0;i=i-4)if(i>3)nu m1t1=atoi(m_operate1.Mid(i-3,4);t1+;else break;if(t1!=m1)nu m1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(i nt j=len_op2-1;j>0;j=j-4)if(j>3)nu m2t2=atoi(m_operate2.Mid(j-3,4);t2+;else break;if(t2!=m2)nu m2t2=atoi(m_operate2.Mid(0,j+1);void CBigCou ntDlg:O

17、nButto nMulti()for(i nt i=0;i<100;i+)/初始化nu m1i=nu m2i=jii=bufferi=0;num1表示的长整数相Cha ngeTol nt4(); /将字符串表示的大整数存入长整形数组for(i nt t1=0;t1<m2;t1+)num2t1作为一个非大整数与数组乘Sin gleMul( num1, num2t1,t1);int beg in;CStri ng aa,bb;for(i nt j=99;j>=0;j-)if(jij!=0)beg in=j;break; aa=bb=""aa.Format(&q

18、uot;%d",jibegi n);for(int l=begin-1;l>=0;l-)if(jil<10) bb.Format("%d",jil);bb="000"+bb;else if(jil<100)bb.Format("%d",jil);bb="00"+bb;else if(jil<1000)bb.Format("%d",jil);bb="O"+bb; else bb.Format("%d",jil);aa+=bb

19、;MessageBox(aa);7:使用方法，如如何启动程序，关闭程序，对输入输出要求输入两个非负的的大整数的乘法&测试数据数据及结果说明（正确数据以及非正确数据）正确数据：错误数据:-ioaBlgCoun-t X|-1000-2300122说明：未考虑负数参与乘法运算的情况9:总结（如调试过程中遇到的问题算法策略；算法的方法）将两个大数相乘的情况，分解为非大整数与大整数相乘，最终分解为两个非大整数相乘，再将所的的结果用加法 整合在一起，要注意相应的权值体现在数组的下表上。四：实验题目大整数除法1:问题分析处理多位整数的除法，这些整数无法在计算机硬件允许的范围内表示和处理。2:数学模型

20、一个较大的大整数除以一个整数，先把除数乘以相应的权值（在后面加0）使它成为 小于被除数的最大的数。则用被除数减去除数，直到被除数小于除数，记录减去的次 数，则这个次数就为商，剩余的被除数就为余数。3：算法策略的选择采用蛮力法4：程序流程图5：算法时间复杂度与空间复杂度（推导过程）6:程序实现(注释)int CBigCou ntDlg:Jia n(i nt l,i nt Io n) /从被除数中减去除数 int buffer1OO=O;int jie=0; int di=l-lo n+1; /di记录被除数与除数开始相减的位数for(int i=0;i<len_da2;i+) buffer

21、di+i=data1di+i-data2i-jie;if(bufferdi+i<0) bufferdi+i+=10;jie=1; elsejie=0;if(jie>0&&lon=len_da2) /此时从被除数中取到的与除数相同长度的一段比除数小return -1; / 返回-1将除数较于被除数后撤一位在相减else / 此时将buffer新负的值传给被除数bufferdi+i=data1di+i-jie;for(i nt j=l-l on+1;j<=l-l on+1+le n_da2;j+) data1j=bufferj;int xiao=0; /记录被除数

22、的长度减少多少for(int k=len_da1-1;l>=0;k-)if(data1k=0)xiao+;elsebreak; len _da1-=xiao;return 1;void CBigCou ntDlg:O nButto nDive()for(i nt k=0;k<100;k+)/初始化nu m1k=num2k=co un tk=0;UpdateData();len _da仁m_operate1.GetLe ngth();len _da2=m_operate2.GetLe ngth();for(int i=0;i<len_da1;i+)/每位存储一位data1len_da1-i-1=atoi(m_operate1.Mid(i,1);for(i nt j=O;j<le n_da2;j+)data2len_da2-j-1=atoi(m_operate