算法大整数的四则运算
含蓄是什么意思-节日祝词
姓名： 胡双兴 学号：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：程序流程图
声明变量并初始化
开始
以字符形式输入两个大整
数m_operate1,m_operate2
将m_operate1和m_operate2转化
为整形数组的形式存储每位6位。
Num1[],num2[],m1,m2为两个数
组的长度。int j=0
判断
j
Y
hen[j]=num1[j]+num2[j]+jin-1000000;
从低位开始相加每位都当成有进位处理
N
判断hen[j]>=0)？
（有无进位）
判断jin==1?处
理最高位进位
Y Y
jin=1;
有进位
hen[j]=num1[j]+num2[j]+jin;
jin=0;无进位
hen[j]=1;
j--;
j++;
输出结果
将hen[]中
的元素由高位到低位
转化为字符串输出
结束
5：算法时间复杂度与空间复杂度（推导过程）
6：程序实现（注释）
void CBigCountDlg::ChangeToInt()
{
将字符串存储的大整数转化为整形数组存储每位数组存储6位
UpdateData();
int
len_op1,len_op2;存放两个字符串长度且len_op1存放较长字符串的长度
len_op1=m_gth();
len_op2=m_gth();
if(l
en_op1
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_op16;
m1是m_operate1所用数组的长度
if(len_op1%6!=0)
m1++;
m2=len_op26; m2是m_operate2所用数组的长度
if(len_op2%6!=0)
int
t1=0;
for(int i=len_op1-1;i>0;i=i-6)
{
数组的每个元素存放6个字符串
}
if(t1!=m1)
if(i>5)
num1中存放较长的字符串m_operate1
{
num1[t1]=atoi(m_(i-5,6));
t1++;
}
else
break;
m2++;
}
num1[t1]=atoi(m_(0,i+1));
int t2=0;
for(int j=len_op2-1;j>0;j=j-6)
{
num2存放字符串m_operate2
}
if(t2!=m2)
num2[t2]=atoi(m_(0,j+1));
if(j>5)
{
num2[t2]=atoi(m_(j-5,6));
t2++;
}
else
break;
void
CBigCountDlg::OnButtonAdd()
{
int jin,i,j;
jin存储进位
CString aa,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--;
输出结果
(
for(int l=j-1;l>=0;l--)
{
if(hen[l]<10)
{
}
(
bb=
}
else if(hen[l]<100)
{
}
else if(hen[l]<1000)
{
}
else if(hen[l]<10000)
{
}
else if(hen[l]<100000)
{
}
else
{ (
(
bb=
(
bb=
(
bb=
(
bb=
aa+=bb;
MessageBox(aa);
}
7：使用方法，如如何启动程序，关闭程序，对输入输出要求
可输入两个非负的大整数进行运算。
8：测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
错误数据：
说明：没有在输入大整数时判断正负。
9：总结（如调试过程中遇到的问题算法策略；算法的方法）
输出时按照，存放和的数组h
en[],由高位到低位输出，数组中除最高位的一位并没有达到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：程序流程图
i
判断
N
将m_operate1和m_operate2转化
为整形数组的形式存储每位6位。
Num1[],num2[],m1,m2为两个数
组的长度。int j=0
声明变量并初始化
开始
以字符形式输入两个大整
数m_operate1,m_operate2
Y
cha[i]=num1[i]-num2[i]-jie;
从高位到低位找到cha[]中第一位不
为0的下标记位begin
N
cha[i]<0&
&(i!=m1-1)
Y
jie=1;（需要借位）
cha[i]+=1000000;
jie=0;(不需要借
位)
输出结果
将hen[]中
的元素由高位到低位
转化为字符串输出
i++
结束
5：算法时间复杂度与空间复杂度（推导过程）
6：程序实现（注释）
void
CBigCountDlg::OnButtonCut()
{
实现两个大整数的减法
for(int q=0;q<100;q++)
num1[q]=num2[q]=cha[q]=0;
UpdateData();
bool comp=0;
若comp为0则m_operate1大于或等于m_oprate2若为1则相反
int
len_op1,len_op2;
len_op1=m_gth();
len_op2=m_gth();
if(len_op2>len_op1)
comp=1;
ChangeToInt();
int jie=0;
for(int i=0;i
cha[i]=num1[i]-num2[i]-jie;
if(cha[i]<0&&(i!=m1-1))
{
}
}
jie=1;
cha[i]+=1000000;
else
jie=0;
int
begin=0; 从高位到低位找到cha[]中第一位部位0的下标几位begin
for(int p=99;p>=0;p--)
{
}
CString aa,bb;
(
for(int l=begin-1;l>=0;l--)
{
if(cha[l]<10)
{
}
else if(cha[l]<100)
(
bb=
if(cha[p]!=0)
{
begin=p;
break;
}
}
{
}
else if(cha[l]<1000)
{
}
else if(cha[l]<10000)
{
}
else if(cha[l]<100000)
{
}
else
{
(
(
bb=
(
bb=
(
bb=
(
bb=
}
aa+=bb;
}
if(comp)
{
}
MessageBox(aa);
aa=
7：使用方法，如如何启动程序，关闭程序，对输入输出要求
输入两个非负数的大整数的减法。
8：测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
错误数据：
说明：未考虑负数大整数相减的情况。
9：总结（如调试过程中遇到的问题算法策略；算法的方法）
相减的结果课能为0，但结果是存在数组中的，判断是否为0应从最高为一次检验数组中的每一位。
三：实验题目
大数乘法
1：问题分析
处理多位整数的加法，这些整数无法在计算机硬件允许的范围内表示和处理。
考虑，大整数与正常较小的数相乘，和两个大整数相乘。
2：数学模型
输
入时以字符串的形式表示大整数。采用长整形数组存放大整数，每位数组存放
4位。Num1[],nu
m2[]存放两个加数。ji[]存放积。Num2[]数组中的元素依次从低位到高
位（相应大整数的
低位到高位）当成正常整数与数组num1[]的每一位相乘。jin表示
进位。结果存放在buffe
r[]数组中。将buffer[]中的元素乘以相应的权值赋值给ji[]数组。
3：算法策略的选择
采用蛮力法
4：程序流程图
N
Y
开始
以字符形式输入两个大整
数m_operate1,m_operate2
从高位到低位找到cha[]中第一位不
为0的下标记位begin
声明变量并初始化
将m_operate1和m_operate2转化
为整形数组的形式存储每位6位。
Num1[],num2[],m1,m2为两个数
组的长度。int t1=t2=0
输出结果 将hen[]中
的元素由高位到低位
转化为字符串输出
结束
判断t1
判断
t1
？
N
Y
buffer[t1]=(a[t1]*b+jin)%10000;
jin=(a[t1]*b+jin)10000;
t1++;
判断jin!=0？
处理最高位进位
ji[c+i]=jin;
t1++;
y
判断i<=len？
buffer[t1]=jin;
t1--;
Len=t1;为buffer[]数组的长度
C为当前处理的num2[]数组
元素的下标，i=0
Y
ji[c+i]+=buffer[i]+jin;
jin=0;
N
Y
判断ji[c+i]>9999？
j++;
ji[c+i]=ji[c+i]-10000;
jin=1;
5：算法时间复杂度与空间复杂度（推导过程）
6：程序实现（注释）
void
CBigCountDlg::ChangeToInt4()
{
将字符串表示的长整数转化为长整形数组表示，每位数组存放4位。
UpdateData();
int
len_op1,len_op2;
len_op1=m_gth();
len_op2=m_gth();
if(len_op1
}
m1=len_op14;
CString temp;
temp=m_operate1;
m_operate1=m_operate2;
m_operate2=temp;
int hu;
hu=len_op1;
len_op1=len_op2;
len_op2=hu;
if(len_op1%4!=0)
m1++;
m2=len_op24;
}
if(len_op2%4!=0)
m2++;
int
t1=0;
for(int i=len_op1-1;i>0;i=i-4)
{
}
if(t1!=m1)
num1[t1]=atoi(m_(0,i+1));
int t2=0;
for(int j=len_op2-1;j>0;j=j-4)
{
}
if(t2!=m2)
num2[t2]=atoi(m_(0,j+1));
if(j>3)
{
num2[t2]=atoi(m_(j-3,4));
}
if(i>3)
{
num1[t1]=atoi(m_(i-3,4));
t1++; }
else break;
t2++;
else break;
void
CBigCountDlg::OnButtonMulti()
{
for(int i=0;i<100;i++) 初始化
num1[i]=num2[i]=ji[i]=buffer[i]=0;
ChangeToInt4(); 将字符串表示的大整数存入长整形数组
for(int
t1=0;t1
int begin;
CString aa,bb;
for(int j=99;j>=0;j--)
{
}
aa=bb=
(
for(int
l=begin-1;l>=0;l--)
{
if(ji[l]<10)
{ (
bb=
if(ji[j]!=0)
{ begin=j; break; }
else if(ji[l]<100)
{ (bb=}
else
if(ji[l]<1000)
{ (
(
bb=}
aa+=bb;}
else {
}
}
MessageBox(aa);
7：使用方法，如如何启动程序，关闭程序，对输入输出要求
输入两个非负的的大整数的乘法
8：测试数据数据及结果说明（正确数据以及非正确数据）
正确数据：
错误数据：
说明：未考虑负数参与乘法运算的情况。
9：总结（如调试过程中遇到的问题算法策略；算法的方法）
将两个大数相乘的情况，分
解为非大整数与大整数相乘，最终分解为两个非大整数相乘，再将所的的结果用加法
整合在一起，要注意
相应的权值体现在数组的下表上。
四：实验题目
大整数除法
1：问题分析
处理多位整数的除法，这些整数无法在计算机硬件允许的范围内表示和处理。
2：数学模型
一个较大的大整数除以一个整数，先把除数乘以相应的权值（在后面加0）
使它成为
小于被除数的最大的数。则用被除数减去除数，直到被除数小于除数，记录减去的次
数
，则这个次数就为商，剩余的被除数就为余数。
3：算法策略的选择
采用蛮力法
4：程序流程图
hu>=len_da2-1?
N
Y
开始
以字符形式输入两个大整
数m_operate1,m_operate2
声明变量并初始化
将m_operate1和m_operate2转化
为整形数组
的形式存储每位1位。
data1[],data2[],len_da1,len_da2为
两个数组的长度。hu=len_da1-1
cha=len_da1-len_da2;记录
两数相差的位数。
从高位到低位找到count
[]中第一位
若data1[]中较高位出现0，则
修正len_da1的大小
不为0的下标记位begin
输出结果
将count[]中
的元素由高位到低位
转化为字符串输出
若data1[]比data2[]从高位
开始算起大。则减去data[]2
若小data2[]与data1[]从其
第二高位开始相减。
hu=len_da1-1;
结束
5：算法时间复杂度与空间复杂度（推导过程）
6：程序实现（注释）
int
CBigCountDlg::Jian(int l,int lon) 从被除数中减去除数
{
int buffer[100]={0};
int jie=0; int di=l-lon+1;
di记录被除数与除数开始相减的位数
for(int i=0;i
}
buffer[di+i]=data1[di+i]-data2[i]-jie;
if(buffer[di+i]<0)
{
buffer[di+i]+=10;
jie=1; }
jie=0;
else
if(jie>0&&lon==len_da2)
此时从被除数中取到的与除数相同长度的一段比除数小
return -1;
返回-1将除数较于被除数后撤一位在相减
else
此时将buffer新负的值传给被除数
{
buffer[di+i]=data1[di+i]-jie;
for(int
j=l-lon+1;j<=l-lon+1+len_da2;j++)
data1[j]=buffer[j];
int xiao=0;
记录被除数的长度减少多少
for(int k=len_da1-1;l>=0;k--)
{
if(data1[k]==0)
xiao++;
} else break;
len_da1-=xiao;
}
return 1;
}
void CBigCountDlg::OnButtonDive()
{
UpdateData();
for(int
k=0;k<100;k++)
{ 初始化
}
num1[k]=num2[k]=count[k]=0;
len_da1=m_gth();
len_da2=m_gth();
for(int i=0;i
data1[len_da1-i-1]=atoi(m_(i,1));
}
for(int j=0;j
}
int cha,sh,xing;
data2[len_da2-j-1]=atoi(m_(j,1));
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--;
}
count[cha]++;
hu=len_da1-1;
bool bre=0;
if(len_da1
if(len_da1==len_da2)
{
for(int t4=len_da2-1;t4>=0;t4--)
{
if(data1[t4]
bre=1;
break;
} 被除数比除数小了
}
}
if(bre==1)
break;
}
CString result,yu,bu;
result=yu=bu=
if(count[l]==0)
l--;
for(int t6=l;t6>=0;t6--)
{
(
result+=bu;
}
for(int
t5=len_da1-1;t5>=0;t5--)
，此时被除数的值就为余数驻足痴望-短长