算法大整数的四则运算.docx
《算法大整数的四则运算.docx》由会员分享，可在线阅读，更多相关《算法大整数的四则运算.docx（27页珍藏版）》请在冰点文库上搜索。
算法大整数的四则运算
姓名：
胡双兴学号：
090610213班级：
090413
一：
实验题目：
大整数加法
1问题分析：
处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。
2：
数学模型
输入时以字符串的形式表示大整数。
采用数组存放大整数，每位数组存放6位。
Num1[],num2[]存放两个加数。
Hen[]存放和，jin表示进位。
则hen[i]=num1[i]+num2[i]+jin,此时的jin表示的是来自低位的进位。
若hen[i]超过1000000，则hen[i]修正为hen[i]-1000000,且jin=1。
.
3：
算法策略的选择
采用蛮力算法
4：
程序流程图
N
Y
N
YY
5：
算法时间复杂度与空间复杂度（推导过程）
6：
程序实现（注释）
voidCBigCountDlg:
:
ChangeToInt（）
{//将字符串存储的大整数转化为整形数组存储每位数组存储6位
UpdateData（）;
intlen_op1,len_op2;//存放两个字符串长度且len_op1存放较长字符串的长度
len_op1=m_operate1.GetLength（）;
len_op2=m_operate2.GetLength（）;
if（len_op1{
CStringtemp;
temp=m_operate1;
m_operate1=m_operate2;
m_operate2=temp;
inthu;
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++;
intt1=0;
for（inti=len_op1-1;i>0;i=i-6）
{//数组的每个元素存放6个字符串
if（i>5）//num1中存放较长的字符串m_operate1
{
num1[t1]=atoi（m_operate1.Mid（i-5,6））;
t1++;
}
else
break;
}
if（t1!
=m1）
num1[t1]=atoi（m_operate1.Mid（0,i+1））;
intt2=0;
for（intj=len_op2-1;j>0;j=j-6）
{//num2存放字符串m_operate2
if（j>5）
{
num2[t2]=atoi（m_operate2.Mid（j-5,6））;
t2++;
}
else
break;
}
if（t2!
=m2）
num2[t2]=atoi（m_operate2.Mid（0,j+1））;
}
voidCBigCountDlg:
:
OnButtonAdd（）
{
intjin,i,j;//jin存储进位
CStringaa,bb;//存放输出的值
aa=bb="";
jin=0;
for（i=0;i<100;i++）
{//初始化
num1[i]=num2[i]=hen[i]=0;
}
ChangeToInt（）;//将字符型大整数转化为整数数组存储
for（j=0;j{//从低位开始相加每位都当成有进位处理
hen[j]=num1[j]+num2[j]+jin-1000000;
if（hen[j]>=0）//有进位
jin=1;
else//没有进位修正hen[j]的值
{
hen[j]=num1[j]+num2[j]+jin;
jin=0;
}
}
if（jin==1）//处理最高位的进位
hen[j]=1;
else
j--;
//输出结果
aa.Format（"%d",hen[j]）;
for（intl=j-1;l>=0;l--）
{
if（hen[l]<10）
{
bb.Format（"%d",hen[l]）;
bb="00000"+bb;
}
elseif（hen[l]<100）
{
bb.Format（"%d",hen[l]）;
bb="0000"+bb;
}
elseif（hen[l]<1000）
{
bb.Format（"%d",hen[l]）;
bb="000"+bb;
}
elseif（hen[l]<10000）
{
bb.Format（"%d",hen[l]）;
bb="00"+bb;
}
elseif（hen[l]<100000）
{
bb.Format（"%d",hen[l]）;
bb="0"+bb;
}
else
{bb.Format（"%d",hen[l]）;}
aa+=bb;
}
MessageBox（aa）;
}
7：
使用方法，如如何启动程序，关闭程序，对输入输出要求
可输入两个非负的大整数进行运算。
8：
测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
错误数据：
说明：
没有在输入大整数时判断正负。
9：
总结（如调试过程中遇到的问题算法策略；算法的方法）
输出时按照，存放和的数组hen[],由高位到低位输出，数组中除最高位的一位并没有达到6位时如123应该输出000123而不是123.。
解决方法判断大小在数前加0。
二：
实验题目
大整数减法
1：
问题分析
处理多位整数的减法，这些整数无法在计算机硬件允许的范围内表示和处理。
2：
数学模型
输入时以字符串的形式表示大整数。
采用数组存放大整数，每位数组存放6位。
将输入的两个大整数处理为位数较多的一个减去位数较少的一个，若被减数比减数位数少结果前面加“-”。
Num1[],num2[]存放被减数和减数。
cha[]存放差，jie表示借位。
则cha[i]=num1[i]-num2[i]-jie;jie为低位是否向此位借位。
若cha[i]<0则修正为cha[i]+=1000000;且jie=1。
3：
算法策略的选择：
采用蛮力法。
4：
程序流程图
N
Y
N
Y
5：
算法时间复杂度与空间复杂度（推导过程）
6：
程序实现（注释）
voidCBigCountDlg:
:
OnButtonCut（）
{//实现两个大整数的减法
for（intq=0;q<100;q++）
num1[q]=num2[q]=cha[q]=0;
UpdateData（）;
boolcomp=0;//若comp为0则m_operate1大于或等于m_oprate2若为1则相反
intlen_op1,len_op2;
len_op1=m_operate1.GetLength（）;
len_op2=m_operate2.GetLength（）;
if（len_op2>len_op1）
comp=1;
ChangeToInt（）;
intjie=0;
for（inti=0;i{
cha[i]=num1[i]-num2[i]-jie;
if（cha[i]<0&&（i!
=m1-1））
{
jie=1;
cha[i]+=1000000;
}
else
jie=0;
}
intbegin=0;//从高位到低位找到cha[]中第一位部位0的下标几位begin
for（intp=99;p>=0;p--）
{
if（cha[p]!
=0）
{
begin=p;
break;
}
}
CStringaa,bb;
aa.Format（"%d",cha[begin]）;
for（intl=begin-1;l>=0;l--）
{
if（cha[l]<10）
{
bb.Format（"%d",cha[l]）;
bb="00000"+bb;
}
elseif（cha[l]<100）
{
bb.Format（"%d",cha[l]）;
bb="0000"+bb;
}
elseif（cha[l]<1000）
{
bb.Format（"%d",cha[l]）;
bb="000"+bb;
}
elseif（cha[l]<10000）
{
bb.Format（"%d",cha[l]）;
bb="00"+bb;
}
elseif（cha[l]<100000）
{
bb.Format（"%d",cha[l]）;
bb="0"+bb;
}
else
{
bb.Format（"%d",cha[l]）;
}
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：
程序流程图
N
Y
N
Y
y
Y
N
Y
5：
算法时间复杂度与空间复杂度（推导过程）
6：
程序实现（注释）
voidCBigCountDlg:
:
ChangeToInt4（）
{//将字符串表示的长整数转化为长整形数组表示，每位数组存放4位。
UpdateData（）;
intlen_op1,len_op2;//
len_op1=m_operate1.GetLength（）;
len_op2=m_operate2.GetLength（）;
if（len_op1{
CStringtemp;
temp=m_operate1;
m_operate1=m_operate2;
m_operate2=temp;
inthu;
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++;
intt1=0;
for（inti=len_op1-1;i>0;i=i-4）
{
if（i>3）
{
num1[t1]=atoi（m_operate1.Mid（i-3,4））;
t1++;}
elsebreak;
}
if（t1!
=m1）
num1[t1]=atoi（m_operate1.Mid（0,i+1））;
intt2=0;
for（intj=len_op2-1;j>0;j=j-4）
{
if（j>3）
{num2[t2]=atoi（m_operate2.Mid（j-3,4））;
t2++;}
elsebreak;
}
if（t2!
=m2）
num2[t2]=atoi（m_operate2.Mid（0,j+1））;
}
voidCBigCountDlg:
:
OnButtonMulti（）
{
for（inti=0;i<100;i++）//初始化
num1[i]=num2[i]=ji[i]=buffer[i]=0;
ChangeToInt4（）;//将字符串表示的大整数存入长整形数组
for（intt1=0;t1SingleMul（num1,num2[t1],t1）;
intbegin;
CStringaa,bb;
for（intj=99;j>=0;j--）
{
if（ji[j]!
=0）
{begin=j;break;}
}
aa=bb="";
aa.Format（"%d",ji[begin]）;
for（intl=begin-1;l>=0;l--）
{
if（ji[l]<10）
{bb.Format（"%d",ji[l]）;bb="000"+bb;}
elseif（ji[l]<100）
{bb.Format（"%d",ji[l]）;bb="00"+bb;}
elseif（ji[l]<1000）
{bb.Format（"%d",ji[l]）;bb="0"+bb;}
else{bb.Format（"%d",ji[l]）;aa+=bb;}
}
MessageBox（aa）;
}
7：
使用方法，如如何启动程序，关闭程序，对输入输出要求
输入两个非负的的大整数的乘法
8：
测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
错误数据：
说明：
未考虑负数参与乘法运算的情况。
9：
总结（如调试过程中遇到的问题算法策略；算法的方法）
将两个大数相乘的情况，分解为非大整数与大整数相乘，最终分解为两个非大整数相乘，再将所的的结果用加法整合在一起，要注意相应的权值体现在数组的下表上。
四：
实验题目
大整数除法
1：
问题分析
处理多位整数的除法，这些整数无法在计算机硬件允许的范围内表示和处理。
2：
数学模型
一个较大的大整数除以一个整数，先把除数乘以相应的权值（在后面加0）使它成为小于被除数的最大的数。
则用被除数减去除数，直到被除数小于除数，记录减去的次数，则这个次数就为商，剩余的被除数就为余数。
3：
算法策略的选择
采用蛮力法
4：
程序流程图
N
Y
5：
算法时间复杂度与空间复杂度（推导过程）
6：
程序实现（注释）
intCBigCountDlg:
:
Jian（intl,intlon）//从被除数中减去除数
{intbuffer[100]={0};
intjie=0;intdi=l-lon+1;//di记录被除数与除数开始相减的位数
for（inti=0;i{buffer[di+i]=data1[di+i]-data2[i]-jie;
if（buffer[di+i]<0）
{buffer[di+i]+=10;
jie=1;}
elsejie=0;
}
if（jie>0&&lon==len_da2）//此时从被除数中取到的与除数相同长度的一段比除数小
return-1;//返回-1将除数较于被除数后撤一位在相减
else//此时将buffer新负的值传给被除数
{
buffer[di+i]=data1[di+i]-jie;
for（intj=l-lon+1;j<=l-lon+1+len_da2;j++）
data1[j]=buffer[j];
intxiao=0;//记录被除数的长度减少多少
for（intk=len_da1-1;l>=0;k--）
{if（data1[k]==0）
xiao++;
elsebreak;}
len_da1-=xiao;
}
return1;
}
voidCBigCountDlg:
:
OnButtonDive（）
{for（intk=0;k<100;k++）
{//初始化
num1[k]=num2[k]=count[k]=0;
}
UpdateData（）;
len_da1=m_operate1.GetLength（）;
len_da2=m_operate2.GetLength（）;
for（inti=0;i{//每位存储一位
data1[len_da1-i-1]=atoi（m_operate1.Mid（i,1））;
}
for（intj=0;j{
data2[len_da2-j-1]=atoi（m_operate2.Mid（j,1））;
}
intcha,sh,xing;
sh=1;
intl=len_da1-len_da2;
for（inthu=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--;
}
count[cha]++;
hu=len_da1-1;
boolbre=0;
if（len_da1break;
if（len_da1==len_da2）
{
for（intt4=len_da2-1;t4>=0;t4--）
{
if（data1[t4]{
bre=1;
break;
}//被除数比除数小了，此时被除数的值就为余数
}
}
if（bre==1）
break;
}
CStringresult,yu,bu;
result=yu=bu="";
if（count[l]==0）
l--;
for（intt6=l;t6>=0;t6--）
{
bu.Format（"%d",count[t6]）;
result+=bu;
}
for（intt5=len_da1-1;t5>=0;t5--）
{
bu.Format（"%d",data1[t5]）;
yu+=bu;
}
MessageBox（"商为"+result+"余数为"+yu）;}
7：
使用方法，如如何启动程序，关闭程序，对输入输出要求
实现两个非负大整数的除法运算，得到商和余数。
8：
测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
9：
总结（如调试过程中遇到的问题算法策略；算法的方法）
升级会员 