首页 > 代码库 > 大数相乘
大数相乘
1、算法思路
将大数当做字符串进行处理,也就是将大数用十进制字符数组进行表示,然后模拟人们手工进行“竖式计算”的过程得到乘法的结果。
乘积是逐位相乘,也就是a[i] * b[j],结果加入到积C的第i+j位,即
最后处理进位即可
例如:A =17 = 1*10 + 7 = (7,1)最后是十进制的幂表示法,幂次是从低位到高位,以下同。
B=25 = 2*10 + 5 = (5, 2);
C = A * B = (7 * 5, 1 * 5 + 2 * 7, 1 * 2) = (35, 19, 2) = (5, 22, 2) = (5, 2. 4)=425
2、源代码
#include<iostream>using namespace std;#define null 0#define MAXN 51 //大数相乘char *big_cheng(char line1[], char line2[]){ short s1[MAXN], s2[MAXN], s[MAXN];//s1,s2:两个乘数;s:乘积的结果 int i, j, k, c; int len1, len2, len; len1 = strlen(line1); len2 = strlen(line2); len = len1 + len2;//初步确定乘积的长度 for(i = len1 - 1; i >= 0; i--) { s1[i] = line1[len1 - i -1] - ‘0‘;//将字符串转化为整型,并反着存放 } for(i = len2 - 1; i >= 0; i--) { s2[i] = line2[len2 - i - 1] - ‘0‘; } memset(s, 0, sizeof(short) * (MAXN - 1));//s数组初始化 for(i = 0; i <= len1 -1; i++) { for(j = 0; j <= len2 -1; j++) { s[i + j] = s[i + j] + s1[i] * s2[j];//逐位相乘 } } for(i = 0, c = 0; i <= len - 1;i++)//处理进位 { k = s[i] + c; s[i] = k % 10; c = k / 10; } for(i = len - 1; i >= 0; i--) { if(s[i] != 0) { break;//处理多余的零 } } len = i + 1; char *line;//注意只有指针才可以返回去,不能定义成数组 line = new char[len + 1]; if(len == 0) { line[0] = 0 + ‘0‘; line[1] = ‘\0‘;//字符串的结束标志 } else { for(i = 0; i <= len - 1; i++) { line[i] = s[len - i - 1] + ‘0‘; } line[len] = ‘\0‘;//字符串的结束标志 } return line;} int main(){ char line1[MAXN], line2[MAXN]; while(cin >> line1 >>line2) { cout << big_cheng(line1, line2) << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。