实验报告
一、实验题目:两个 10 位以上大整数相乘
二、算法设计思想:
1.用字符数组接收输入的大整型相乘数;
2.对字符数组中的数据提取出来倒序的存入整型数组中;
3.对数组中的数值依次相乘,数组下标相加的值相等的说明乘积的幂次也相等,所以乘积
就累加并存入另一组数组对应的位中。
4.对存储乘积累加和得数组进行十进制个位化,即数组每位存的数值不超过 9,即利用对
10 取模取余的方法,余数留在本位,模就当是进位就往上一位累加。
5 对规范化的数值倒序输出就是得到大整型数乘积的结果。
三、算法描述:
用两个字符数组 ca[50]和 cb[50]存储输入的 10 位以上的大整数,以字符串的形式来存储,
再分别用 ASCII 码差值提取出各位上的数值分别存储到 a[50]和 b[50]两个整型数组中,整
型数组每一个存储空间存储各位上的值,比如 a[0]存储的是个位上的数值,a[1]存储的是十
位上的数值。再用一个整型数组存储 c[i+j]存储对应的 a[i]和 b[j]的乘积的总和,比如 c[3]的
值是等于 a[0]*b[3]+ a[1]*b[2]+ a[2]*b[1]+ a[3]*b[0]的总和,这里也是相当于幂次相同的数
值相加,最后把数组 c[i]个位话,就是把 c[i]里的整型都对 10 取余和取模,余数留在本位
c[i],模就往下一位 c[i+1]相加,循环此操作,最后 c[i]的每个空间存储的数就是输入的两个
长整型数相乘所得结果的对应个位上的数值,其中 c[0]对应结果的个位,c[1]对应结果的十
位,问题求解成功!
四、算法分析:
该算法的基本核心操作是累加赋值操作,即
for(i=0;i<len1;i++)
for(j=0;j<len2;j++)
{
c[i+j]+=a[i]*b[j];
//printf("%d",c[i+j]);
}
所以时间复杂度为 len1*len2,即 T(n)=O(len1*len2)
五、代码清单
#include<stdio.h>
#include<string.h>
void main()
{
int a[50]={0},b[50]={0},c[100]={0};
char ca[50]={0},cb[50]={0};
int len1,len2;
int i,j;