大整数的乘法实习报告.doc

湖南涉外经济学院计算机科学与技术专业
《算法设计与分析》课程
大整数乘法问题
实验报告
班级:
学号:
姓名:
教师:
成绩:
2012年5月
【实验目的】
1 掌握设计有效算法的分治策略
2 利用软件的方法来实现大整数的算术运算
【系统环境】
Windows 7 平台
【实验工具】
VC++
【问题描述】
描述: 由于现在的许多方面需要在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的运算。其中一般都通过数组来实现。
例: 5464 *1231 其结果是:6524184
【实验原理】
1 、开始时的思路:
1>.弄2个string类型的变量来获取乘数a与被乘数b
2>.需要用到string类型的变量时再调用转换函数
3>.再定义个2维数组来装a*b的积、定义个d数组装最终结果
4>.写一个乘法和加法函数用来实现上述功能

、例子:
【源程序代码】
#include<iostream>
#include<string>
using namespace std;
void MUL_max(string a,int la,string b,int lb,int **c);//相乘函数
void ADD_max(int * d,int **c,int la,int lb);//相加函数
char * ZhuanH(string);
void main()
{
string a;
string b;
int **c=NULL;
int *d=NULL;
int la=0,lb=0;
int i=0,j=0,k=0;

cout<<" ************大整数乘法**************"<<endl;
cout<<"请输入乘数:";
cin>>a;
cout<<"请输入被乘数:";
cin>>b;

la=();
lb=();
//分配2维C数组,存储数组a和b的乘积
c=new int*[la];
for(k=0;k<la;k++)
c[k]=new int[lb+1];
//分配数组d用于存储最终结果
d=new int[la+lb+1];
for(i=0;i<la+lb+1;i++)//初始化,便于后面判断相加后的有效位数
d[i]=0;
//初始化数组C,便于后面判断相加后的有效位数
for(i=0;i<la;i++)
for(j=0;j<=lb;j++)
c[i][j]=0;
//调用函数
MUL_max(a,la,b,lb,c);
ADD_max(d,c,la,lb);

k=0;
cout<<a<<"和"<<b<<"相乘结果是:"<<endl;
for(i=0;i<=la+lb;i++)
{
if(d[i]==0)
k++;
else
break;
}
for(i=k;i<=la+lb;i++)
cout<<d[i];
cout<<endl;
//释放空间
for(int n=0;n<lb;n++)
{
delete c[n];
}
delete[la] c;
delete [] d;

}
void MUL_max(string a,int la,string b,int lb,int **c)
{
int mid=0,i=0,j=0;
int k=0;
int num_a=0,num_b=0;
char *char_a=NULL,*char_b=NULL;
char_a=ZhuanH(a);//将String转化为char
char_b=ZhuanH(b);
//开始循环相乘la*lb次
for(i=la-1;i>=0;i--)
for(j=lb-1;j>=0;j--)
{

num_a=a[i]-48;
num_b=b[j]-48;
if((k=num_a*num_b)>=10)//判断乘积是否有进位
{
if(mid!=0)//判断前一次相乘是否有进位
c[i][j+1]=k%10+mid;
else
c[i][j+1]=k%10;
mid=k/10;
}
else//没有进位
{
if(mid!=0)//判断前一次相乘是否有进位
c[i][j+1]=k+mid;
else
c[i][j+1]=k;
mid=0;
}
}