一、问题与要求
问题:1、大整数运算C++中整型的表示范围受限,但在某些领域存在大整数(如位数>20)的计算。请使用线性表实现大整数的加法和乘法,并分析算法时间复杂度。
要求:顺序表类用C++的模板实现
算法用流程图和伪代码的形式分别描述,并分析算法时间复杂度
二、程序设计的基本思想,原理和算法描述:
(包括程序的结构,数据结构,输入/输出设计,符号名说明等)
自然语言:首先在头文件中定义顺序表类,在public中声明函数,private中创建固定数组和数据长度,在具体的加法函数实现中记录进位变量,用短的数据长度次进行循环相加进位,并用array数组接收,每经过一次循环,两个数据长度减一,较长的数据长度继续进行进位操作,若最后还有一位进位,存入array数组,由于存入数组的顺序是从右向左,为逆序,因此需要正序存入data数组中。
时间复杂度:O(N)
伪代码:
3.流程图:
三、源程序及注释
三个文件:
大数相加.h
大数相加函数.cpp
大数相加测试.cpp
四、运行输出结果:
五、源代码:
大数相加.h:
include
using namespace std;
class Seqlist
{
public:
Seqlist(){length = 0;}
Seqlist(int a[], int n);
~Seqlist(){}
void SeqlistAdd(Seqlist A,Seqlist B,int array[]);
void Print_sum();
int count();
private:
int num[100];
int length;
};
extern int sub;
extern int E[1000];
Seqlist::Seqlist(int a[],int n)//将数组的值传入顺序表中
{
for(int i=0;i<n;i++)
{
num[i]=a[i];
}
length=n;
}
void Seqlist::SeqlistAdd(Seqlist A,Seqlist B,int array[])
{
int a=A.length,b=B.length;
int sh=a<b?a:b;//选择短的数据长度
int m=a-1,n=b-1;//两个数组下标
sub=0;//和数组下标
int jw=0;//产生的进位
for(int i=0;i<sh;i++)
{
int add=A.num[m--]+B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(m>=0)
{
int add=A.num[m--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(n>=0)
{
int add=B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
if(jw)
{
array[sub++]=jw;
}
length=sub;
for(int i=0;i<length;i++)
{
num[i]=array[length-i-1];
}
}
void Seqlist::Print_sum()
{
for(int i = 0; i < length; i++){
cout << num[i];
}
}
int Seqlist::count()
{
return length;
}
大数相加函数.cpp:
include"大数相加.h"
int sub;
int E[1000];
Seqlist::Seqlist(int a[],int n)//将数组的值传入顺序表中
{
for(int i=0;i<n;i++)
{
num[i]=a[i];
}
length=n;
}
void Seqlist::SeqlistAdd(Seqlist A,Seqlist B,int array[])
{
int a=A.length,b=B.length;
int sh=a<b?a:b;//选择短的数据长度
int m=a-1,n=b-1;//两个数组下标
sub=0;//和数组下标
int jw=0;//产生的进位
for(int i=0;i<sh;i++)
{
int add=A.num[m--]+B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(m>=0)
{
int add=A.num[m--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(n>=0)
{
int add=B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
if(jw)
{
array[sub++]=jw;
}
length=sub;
for(int i=0;i<length;i++)
{
num[i]=array[length-i-1];
}
}
void Seqlist::Print_sum()
{
for(int i = 0; i < length; i++){
cout << num[i];
}
}
大数相加主程序.cpp:
include"大数相加.h"
int sub;
int E[1000]; //逆序数组变量
int main()
{
int m;
cout<<"请输入位数:";
cin>>m;
int arr1[m];
cout<<endl<<"请输入数字:";
for(int i=0;i<m;i++)
{
cin>>arr1[i];
}
cout<<endl;
int n;
cout<<"请输入位数:";
cin>>n;
int arr2[n];
cout<<endl<<"请输入数字:";
for(int i=0;i<n;i++)
{
cin>>arr2[i];
}
Seqlist A(arr1,m);
Seqlist B(arr2,n);
Seqlist sum;
sum.SeqlistAdd(A, B, E);
cout<<"位数为:"<<sum.count()<<endl;
cout << "大数相加:" << endl;
A.Print_sum();
cout << " + " << endl;
B.Print_sum();
cout << " = " << endl;
sum.Print_sum();
cout << endl << endl;
return 0;
}