大数相乘算法

1、计算两个大数相乘的结果。
2、算法流程:
(1)大数可能超出任何一种整数类型,会引发溢出问题,所以用字符串的格式存储数a,b;
(2)计算字符串a的的长度aLen即位数,计算字符串b的长度bLen.
(3)两个数相乘最大为aLen+bLen,整形sumLen=aLen+bLen;
(4)声明字符数组maxArr用于保存a,b中的更大者,声明整形maxLen保存a,b长度的更大者。声明字符数组minArr用于保存a,b中的更小者,声明整形minLen保存a,b长度的更小者。如下所示:


image.png

(5)创建整形数组sumArr用于保存相乘后的结果,创建整形数组tmpArr保存数a的某一位与数b各位相乘的结果,如下所示:


image.png

(6)更小的数minArr的各位(个位,十位,百位,千位等)依次和更大数minArr的各位相乘并存储在临时数组tmpArr中
image.png

3、具体代码:

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
 char* a="9999999";
 char* b="9999999";
 int aLen=strlen(a);
 int bLen=strlen(b);
 int sumLen=aLen+bLen;
 cout << "aLen="<<aLen<<" bLen="<<bLen<<<< "sumLen="<<sumLen<<endl;
 int minLen=0,maxLen=0;
 char* maxArr,minArr;

 if(aLen>bLen){
    maxArr=a;
    minArr=b;
    maxLen=aLen;
    minLen=bLen;
 }else{
     maxArr=b;
     minArr=a;
     maxLen=bLen;
     minLen=aLen;
 }

 int* sumArr=new int[sumLen];
 int* tmpArr=new int[sumLen];

 for(int i=0;i<sumLen;i++){
    sumArr[i]=0;
    tmpArr[i]=0;
 }

 int mulJin=0,addJin=0;

 for(int i=minLen-1;i>=0;i--){
    int k=--sumLen; 
    for(int j=maxLen-1;j>=0;j--){
        tmpArr[k]=((maxArr[j]-'0')*(minArr[i]-'0')+mulJin)%10;
        mulJin=((maxArr[j]-'0')*(minArr[i]-'0')+mulJin)/10;
        k--;
    }
    if(mulJin>0){
        tmpArr[k]=mulJin;
    }
    mulJin=0;
    for(int i=aLen+bLen-1;i>=0;i--){
    int tmp=(sumArr[i]+tmpArr[i]+addJin);
    sumArr[i]=tmp%10;
    addJin=tmp/10;
    }
    addJin=0;

    for(int i=0;i<aLen+bLen;i++){
      tmpArr[i]=0;
    }

}

 int t=0;
 while(true){
    if(sumArr[t]==0){
        t++;
    }else{
       break;
    }
 }
 for(;t<aLen+bLen;t++){
   cout << sumArr[t];
 }

return 0;}

推荐阅读更多精彩内容

  • 一、Java 简介 Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计...
    子非鱼_t_阅读 3,828评论 1 44
  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 3,551评论 0 13
  • 这几年因为工作的关系,经常需要认识各行各业的人,所谓的社交量大大增强。于我而言常常痛苦不堪,因为与对方见面之后常常...
    卿云小有阅读 821评论 0 0
  • 忙完村里白天的各项事务,晚饭吃罢,已近19点。饭后休憩间,听闻村副书记与村主任通电话商讨晚上群众会事宜,引...
    周昱燃阅读 396评论 0 0
  • 今天收到的主题是“朋友”,看到题目时会心一笑,心中有千言万语,临下笔却不知道写什么,像个空有一肚货的闷茶壶,那就想...
    四日阅读 81评论 3 3
  • 我有一个朋友,家在海南,她特别爱挑战自己。 有一次,她做出这样一个打算:从海南一路骑行到北极村——中国的最北端,纵...
    南柯梦语阅读 177评论 0 0