算法大整数的四则运算(15页).doc
-算法大整数的四则运算-第 18 页姓名： 胡双兴 学号：090610213 班级：090413一：实验题目： 大整数加法1问题分析： 处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。2：数学模型输入时以字符串的形式表示大整数。采用数组存放大整数，每位数组存放6位。Num1,num2存放两个加数。Hen存放和，jin表示进位。则heni=num1i+num2i+jin,此时的jin表示的是来自低位的进位。若heni超过1000000，则heni修正为heni-1000000,且jin=1。.3：算法策略的选择采用蛮力算法开始4：程序流程图以字符形式输入两个大整数m_operate1,m_operate2声明变量并初始化将m_operate1和m_operate2转化为整形数组的形式存储每位6位。Num1,num2,m1,m2为两个数组的长度。int j=0判断j<m1? Nhenj=num1j+num2j+jin-1000000;从低位开始相加每位都当成有进位处理 Y判断jin=1?处理最高位进位判断henj>=0)？（有无进位） Nhenj=1;henj=num1j+num2j+jin;jin=0;无进位 Y Yj-;jin=1;有进位 j+;输出结果 将hen中的元素由高位到低位转化为字符串输出结束5：算法时间复杂度与空间复杂度（推导过程）6：程序实现（注释）void CBigCountDlg:ChangeToInt() /将字符串存储的大整数转化为整形数组存储每位数组存储6位UpdateData();int len_op1,len_op2;/存放两个字符串长度且len_op1存放较长字符串的长度len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op1<len_op2)/若m_operate1长度小于m_operate2长度交换两字符串CString temp;temp=m_operate1;m_operate1=m_operate2;m_operate2=temp;int hu;hu=len_op1;len_op1=len_op2;len_op2=hu;m1=len_op1/6; /m1是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) /num1中存放较长的字符串m_operate1 num1t1=atoi(m_operate1.Mid(i-5,6); t1+;else break;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j>0;j=j-6) /num2存放字符串m_operate2if(j>5) num2t2=atoi(m_operate2.Mid(j-5,6); t2+;elsebreak;if(t2!=m2)num2t2=atoi(m_operate2.Mid(0,j+1);void CBigCountDlg:OnButtonAdd() int jin,i,j; /jin存储进位 CString aa,bb; /存放输出的值aa=bb=""jin=0;for( i=0;i<100;i+) /初始化num1i=num2i=heni=0; ChangeToInt(); /将字符型大整数转化为整数数组存储for(j=0;j<m1;j+) /从低位开始相加每位都当成有进位处理 henj=num1j+num2j+jin-1000000;if(henj>=0) /有进位jin=1;else /没有进位修正henj的值henj=num1j+num2j+jin;jin=0; if(jin=1) /处理最高位的进位 henj=1; else j-; /输出结果aa.Format("%d",henj);for(int l=j-1;l>=0;l-)if(henl<10)bb.Format("%d",henl);bb="00000"+bb;else if(henl<100)bb.Format("%d",henl);bb="0000"+bb;else if(henl<1000)bb.Format("%d",henl);bb="000"+bb;else if(henl<10000)bb.Format("%d",henl);bb="00"+bb;else if(henl<100000)bb.Format("%d",henl);bb="0"+bb;elsebb.Format("%d",henl);aa+=bb; MessageBox(aa);7：使用方法，如如何启动程序，关闭程序，对输入输出要求可输入两个非负的大整数进行运算。8：测试数据数据及结果说明（正确数据以及非正确数据）正确数据：错误数据：说明：没有在输入大整数时判断正负。9：总结（如调试过程中遇到的问题算法策略；算法的方法） 输出时按照，存放和的数组hen,由高位到低位输出，数组中除最高位的一位并没有达到6位时如123应该输出000123而不是123.。解决方法判断大小在数前加0。二：实验题目大整数减法1：问题分析处理多位整数的减法，这些整数无法在计算机硬件允许的范围内表示和处理。2：数学模型输入时以字符串的形式表示大整数。采用数组存放大整数，每位数组存放6位。将输入的两个大整数处理为位数较多的一个减去位数较少的一个，若被减数比减数位数少结果前面加“-”。Num1,num2存放被减数和减数。cha存放差，jie表示借位。则chai=num1i-num2i-jie;jie为低位是否向此位借位。若 chai<0则修正为chai+=1000000;且jie=1。3：算法策略的选择：采用蛮力法。4：程序流程图开始 以字符形式输入两个大整数m_operate1,m_operate2将m_operate1和m_operate2转化为整形数组的形式存储每位6位。Num1,num2,m1,m2为两个数组的长度。int j=0声明变量并初始化判断i<m1？ Nchai=num1i-num2i-jie; Y 从高位到低位找到cha中第一位不为0的下标记位beginchai<0&&(i!=m1-1) N输出结果 将hen中的元素由高位到低位转化为字符串输出jie=0;(不需要借位)jie=1;（需要借位）chai+=1000000; Y结束i+ 5：算法时间复杂度与空间复杂度（推导过程）6：程序实现（注释）void CBigCountDlg:OnButtonCut() /实现两个大整数的减法for(int q=0;q<100;q+)num1q=num2q=chaq=0;UpdateData();bool comp=0; /若comp为0则m_operate1大于或等于m_oprate2若为1则相反int len_op1,len_op2;len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op2>len_op1)comp=1;ChangeToInt();int jie=0;for(int i=0;i<m1;i+)chai=num1i-num2i-jie;if(chai<0&&(i!=m1-1)jie=1;chai+=1000000;elsejie=0;int begin=0; /从高位到低位找到cha中第一位部位0的下标几位beginfor(int p=99;p>=0;p-)if(chap!=0)begin=p;break;CString aa,bb;aa.Format("%d",chabegin);for(int l=begin-1;l>=0;l-)if(chal<10)bb.Format("%d",chal);bb="00000"+bb;else if(chal<100)bb.Format("%d",chal);bb="0000"+bb;else if(chal<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);7：使用方法，如如何启动程序，关闭程序，对输入输出要求输入两个非负数的大整数的减法。8：测试数据数据及结果说明（正确数据以及非正确数据）正确数据：错误数据：说明：未考虑负数大整数相减的情况。9：总结（如调试过程中遇到的问题算法策略；算法的方法）相减的结果课能为0，但结果是存在数组中的，判断是否为0应从最高为一次检验数组中的每一位。三：实验题目大数乘法1：问题分析处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。考虑，大整数与正常较小的数相乘，和两个大整数相乘。2：数学模型输入时以字符串的形式表示大整数。采用长整形数组存放大整数，每位数组存放4位。Num1,num2存放两个加数。ji存放积。Num2数组中的元素依次从低位到高位（相应大整数的低位到高位）当成正常整数与数组num1的每一位相乘。jin表示进位。结果存放在buffer数组中。将buffer中的元素乘以相应的权值赋值给ji数组。3：算法策略的选择 采用蛮力法4：程序流程图开始 以字符形式输入两个大整数m_operate1,m_operate2声明变量并初始化 从高位到低位找到cha中第一位不为0的下标记位begin输出结果 将hen中的元素由高位到低位转化为字符串输出将m_operate1和m_operate2转化为整形数组的形式存储每位6位。Num1,num2,m1,m2为两个数组的长度。int t1=t2=0结束判断t1<m2？ N Ybuffert1=(at1*b+jin)%10000; jin=(at1*b+jin)/10000;判断t1<m1？t1+; N Y判断jin!=0？处理最高位进位jic+i=jin;t1+;buffert1=jin; yt1-;Len=t1;为buffer数组的长度C为当前处理的num2数组元素的下标，i=0判断i<=len？ Yjic+i+=bufferi+jin;jin=0;判断jic+i>9999？ N Yj+;jic+i=jic+i-10000; jin=1;5：算法时间复杂度与空间复杂度（推导过程）6：程序实现（注释）void CBigCountDlg:ChangeToInt4() /将字符串表示的长整数转化为长整形数组表示，每位数组存放4位。 UpdateData();int len_op1,len_op2;/len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op1<len_op2)CString temp;temp=m_operate1;m_operate1=m_operate2;m_operate2=temp;int hu;hu=len_op1;len_op1=len_op2;len_op2=hu;m1=len_op1/4; if(len_op1%4!=0)m1+;m2=len_op2/4;if(len_op2%4!=0)m2+;int t1=0;for(int i=len_op1-1;i>0;i=i-4)if(i>3) num1t1=atoi(m_operate1.Mid(i-3,4); t1+;else break;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j>0;j=j-4)if(j>3) num2t2=atoi(m_operate2.Mid(j-3,4); t2+;else break;if(t2!=m2)num2t2=atoi(m_operate2.Mid(0,j+1);void CBigCountDlg:OnButtonMulti() for(int i=0;i<100;i+) /初始化num1i=num2i=jii=bufferi=0;ChangeToInt4(); /将字符串表示的大整数存入长整形数组for(int t1=0;t1<m2;t1+) /num2t1作为一个非大整数与数组num1表示的长整数相乘SingleMul(num1,num2t1,t1);int begin;CString aa,bb;for(int j=99;j>=0;j-)if(jij!=0)begin=j;break;aa=bb=""aa.Format("%d",jibegin);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="0"+bb;elsebb.Format("%d",jil);aa+=bb;MessageBox(aa);7：使用方法，如如何启动程序，关闭程序，对输入输出要求 输入两个非负的的大整数的乘法8：测试数据数据及结果说明（正确数据以及非正确数据）正确数据：错误数据：说明：未考虑负数参与乘法运算的情况。9：总结（如调试过程中遇到的问题算法策略；算法的方法） 将两个大数相乘的情况，分解为非大整数与大整数相乘，最终分解为两个非大整数相乘，再将所的的结果用加法整合在一起，要注意相应的权值体现在数组的下表上。四：实验题目大整数除法1：问题分析处理多位整数的除法，这些整数无法在计算机硬件允许的范围内表示和处理。2：数学模型 一个较大的大整数除以一个整数，先把除数乘以相应的权值（在后面加0）使它成为小于被除数的最大的数。则用被除数减去除数，直到被除数小于除数，记录减去的次数，则这个次数就为商，剩余的被除数就为余数。3：算法策略的选择采用蛮力法4：程序流程图开始 以字符形式输入两个大整数m_operate1,m_operate2声明变量并初始化将m_operate1和m_operate2转化为整形数组的形式存储每位1位。data1,data2,len_da1,len_da2为两个数组的长度。hu=len_da1-1hu>=len_da2-1? N Ycha=len_da1-len_da2;记录两数相差的位数。若data1比data2从高位开始算起大。则减去data2若小data2与data1从其第二高位开始相减。从高位到低位找到count 中第一位不为0的下标记位begin 若data1中较高位出现0，则修正len_da1的大小输出结果 将count中的元素由高位到低位转化为字符串输出hu=len_da1-1;结束5：算法时间复杂度与空间复杂度（推导过程）6：程序实现（注释） int CBigCountDlg:Jian(int l,int lon) /从被除数中减去除数 int buffer100=0;int jie=0; int di=l-lon+1; /di记录被除数与除数开始相减的位数for(int i=0;i<len_da2;i+)bufferdi+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(int j=l-lon+1;j<=l-lon+1+len_da2;j+) data1j=bufferj; int xiao=0; /记录被除数的长度减少多少 for(int k=len_da1-1;l>=0;k-) if(data1k=0) xiao+; else break; len_da1-=xiao; return 1;void CBigCountDlg:OnButtonDive() for(int k=0;k<100;k+) /初始化num1k=num2k=countk=0; UpdateData();len_da1=m_operate1.GetLength();len_da2=m_operate2.GetLength();for(int i=0;i<len_da1;i+) /每位存储一位data1len_da1-i-1=atoi(m_operate1.Mid(i,1);for(int j=0;j<len_da2;j+)data2len_da2-j-1=atoi(m_operate2.Mid(j,1);int cha,sh,xing;sh=1;int l=len_da1-len_da2;for(int hu=len_da1-1;hu>=len_da2-1;)cha=len_da1-len_da2;xing=Jian(hu,len_da2);if(xing=-1) Jian(hu,len_da2+1); cha-;countcha+;hu=len_da1-1;bool bre=0;if(len_da1<len_da2)break;if(len_da1=len_da2)for(int t4=len_da2-1;t4>=0;t4-)if(data1t4<data2t4)bre=1; break; /被除数比除数小了 ，此时被除数的值就为余数if(bre=1)break;CString result,yu,bu;result=yu=bu=""if(countl=0) l-;for(int t6=l;t6>=0;t6-)bu.Format("%d",countt6);result+=bu;for(int t5=len_da1-1;t5>=0;t5-) bu.Format("%d",data1t5);yu+=bu;MessageBox("商为"+result+"余数为"+yu);7：使用方法，如如何启动程序，关闭程序，对输入输出要求实现两个非负大整数的除法运算，得到商和余数。8：测试数据数据及结果说明（正确数据以及非正确数据）正确数据：9：总结（如调试过程中遇到的问题算法策略；算法的方法）
