算法大整数的四则运算.docx

姓名： 胡双兴 学号：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=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_op10;i=i-6) /数组的每个元素存放6个字符串if(i5) /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;j0;j=j-6) /num2存放字符串m_operate2if(j5) 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;i100;i+) /初始化num1i=num2i=heni=0; ChangeToInt(); /将字符型大整数转化为整数数组存储for(j=0;j=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(henl10)bb.Format(%d,henl);bb=00000+bb;else if(henl100)bb.Format(%d,henl);bb=0000+bb;else if(henl1000)bb.Format(%d,henl);bb=000+bb;else if(henl10000)bb.Format(%d,henl);bb=00+bb;else if(henl100000)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为低位是否向此位借位。若 chai0则修正为chai+=1000000;且jie=1。3：算法策略的选择：采用蛮力法。4：程序流程图开始 以字符形式输入两个大整数m_operate1,m_operate2将m_operate1和m_operate2转化为整形数组的形式存储每位6位。Num1,num2,m1,m2为两个数组的长度。int j=0声明变量并初始化判断im1？ Nchai=num1i-num2i-jie; Y 从高位到低位找到cha中第一位不为0的下标记位beginchai0&(i!=m1-1) N输出结果 将hen中的元素由高位到低位转化为字符串输出jie=0;(不需要借位)jie=1;（需要借位）chai+=1000000; Y结束i+ 5：算法时间复杂度与空间复杂度（推导过程）6：程序实现（注释）void CBigCountDlg:OnButtonCut() /实现两个大整数的减法for(int q=0;qlen_op1)comp=1;ChangeToInt();int jie=0;for(int i=0;im1;i+)chai=num1i-num2i-jie;if(chai=0;p-)if(chap!=0)begin=p;break;CString aa,bb;aa.Format(%d,chabegin);for(int l=begin-1;l=0;l-)if(chal10)bb.Format(%d,chal);bb=00000+bb;else if(chal100)bb.Format(%d,chal);bb=0000+bb;else if(chal1000)bb.Format(%d,chal);bb=000+bb;else if(chal10000)bb.Format(%d,chal);bb=00+bb;else if(chal100000)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结束判断t1m2？ N Ybuffert1=(at1*b+jin)%10000; jin=(at1*b+jin)/10000;判断t1m1？t1+; N Y判断jin!=0？处理最高位进位jic+i=jin;t1+; buffert1=jin; yt1-;Len=t1;为buffer数组的长度C为当前处理的num2数组元素的下标，i=0判断i9999？ 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_op10;i=i-4)if(i3) 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;j0;j=j-4)if(j3) 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;i100;i+) /初始化num1i=num2i=jii=bufferi=0;ChangeToInt4(); /将字符串表示的大整数存入长整形数组for(int t1=0;t1=0;j-)if(jij!=0)begin=j;break;aa=bb=;aa.Format(%d,jibegin);for(int l=begin-1;l=0;l-)if(jil10)bb.Format(%d,jil); bb=000+bb;else if(jil100)bb.Format(%d,jil);bb=00+bb;else if(jil=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;ilen_da2;i+)bufferdi+i=data1di+i-data2i-jie;if(bufferdi+i0&lon=len_da2) /此时从被除数中取到的与除数相同长度的一段比除数小 return -1; /返回-1将除数较于被除数后撤一位在相减 else /此时将buffer新负的值传给被除数 bufferdi+i=data1di+i-jie; for(int j=l-lon+1;j=0;k-) if(data1k=0) xiao+; else break; len_da1-=xiao; return 1;void CBigCountDlg:OnButtonDive() for(int k=0;k100;k+) /初始化num1k=num2k=countk=0; UpdateData();len_da1=m_operate1.GetLength();len_da2=m_operate2.GetLength();for(int i=0;ilen_da1;i+) /每位存储一位data1len_da1-i-1=atoi(m_operate1.Mid(i,1);for(int j=0;j=len_da2-1;)cha=len_da1-len_da2;xing=Jian(hu,len_da2);if(xing=-1) Jian(hu,len_da2+1); cha-;countcha+;hu=l