两个10位以上大整数相乘 算法 设计
4星 · 超过85%的资源 需积分: 21 44 浏览量
2009-12-20
14:55:16
上传
评论 1
收藏 43KB DOC 举报 
实验报告
一、实验题目:两个 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;
资源评论
yixiaoyan_2012-03-30不错，比较清晰，也能实现！- tujianxin2013-06-17很好的，对于喜欢算法的人可以好好研究一下
