全国咨询/投诉热线:400-618-9090

首页技术文章正文

高精度计算之大整数乘法【黑马C++培训】

更新时间:2019年08月05日 10时18分45秒 来源:黑马程序员论坛

黑马中级程序员课程


【例1】两个大整数乘法。

      输入两个不超过200位的非负大整数a和b,求a×b的值。

      (1)编程思路。
      用 unsigned num1[200]和num2[200]分别存放两个乘数,用result[400]来存放积。计算的中间结果也都存在result 中。result 长度取400 是因为两个200 位的数相乘,积最多会有400 位。num1[0], num2[0], result[0]都表示个位。
       计算的过程基本上和小学生列竖式做乘法相同。为编程方便,并不急于处理进位,而将 进位问题留待最后统一处理。

       图1给出了753×68的计算过程。描述如下:
      1)先依次计算753的各位数字与8的乘积,并加到result数组的相应单元中。result数组的全部元素的初始值均为0。
      2)再依次计算753的各位数字与6的乘积,并加到result数组的相应单元中。
      3)乘法过程完毕。从 result[0]开始向高位逐位处理进位问题。result[0]留下4,
把2 加到result[1]上,result[1]变为60 后,应留下0,把6 加到result[2]上……最终使 得result 里的每个元素都是1 位数,结果就算出来了。
       在乘法过程中,num1的第i 位和num2的第j 位相乘所得的数,一定是要累加到 result的第i+j 位上。这里i, j 都是从右往左,从0 开始数。
      (2)源程序。
#include <stdio.h> #include <string.h> #define MAX_LEN 201 void bigNumMul(char a[],char b[],char c[]) {       int i,j,n1,n2;       int num1[MAX_LEN]={0},num2[MAX_LEN]={0},result[2*MAX_LEN]={0};       // 将a和b中存储的字符串形式的整数转换到num1和num2中去,       // num1[0]对应于个位、num1[1]对应于十位、……       n1 = strlen(a);       j = 0;      for (i = n1 - 1;i >= 0 ; i --)         num1[j++] = a - '0';      n2 = strlen(b);      j = 0;     for (i = n2 - 1;i >= 0 ; i --)         num2[j++] = b - '0';     for (i=0;i < n2; i++ )     {         for (j=0; j<n1; j++)             result[i+j] += num2*num1[j];   // 两数第i, j 位相乘,累加到结果的第i+j 位     }      //  统一处理进位问题     for( i = 0; i < MAX_LEN * 2; i ++ ) {          if (result >= 10)          {               result[i+1] += result / 10;               result %= 10;          }     }     bool isBeginZero = false;     j=0;     for (i=n1+n2-1; i>=0; i--)          if (isBeginZero)             c[j++]=result+'0';         else if (result!=0)         {              c[j++]=result+'0';               isBeginZero = true;          }     if (!isBeginZero) c[j++]='0';     c[j]='\0'; } int main() {      char a[MAX_LEN],b[MAX_LEN],c[2*MAX_LEN];      scanf("%s",a);      scanf("%s",b);      bigNumMul(a,b,c);      printf("%s\n",c);      return 0; }

(3)问题扩展。
下面我们来讨论如何完成一个大整数a和一个int型整型变量b的相乘。
图2给出了753×68的另一种计算过程。描述如下:
      
       1)先依次计算753的各位数字与68的乘积,并存入到result数组的相应单元中。
       2)乘法过程完毕。从 result[0]开始向高位逐位处理进位问题。result[0]留下4,
把20 加到result[1]上,result[1]变为360 后,应留下0,把36 加到result[2]上……最终使 得result 里的每个元素都是1 位数,结果就算出来了。
按这个思路可以实现一个大整数与int型整型变量相乘。源程序如下:
#include <stdio.h> #include <string.h> #define MAX_LEN 201 void bigNumMul(char a[],int b,char c[]) {       int i,j,n1,n2,t;       int num[MAX_LEN]={0},result[MAX_LEN+10]={0};       // 将a和b中存储的字符串形式的整数转换到num1和num2中去,       // num1[0]对应于个位、num1[1]对应于十位、……       n1 = strlen(a);       j = 0;       for (i = n1 - 1;i >= 0 ; i --)          num[j++] = a - '0';       n2 =0;       t=b;       do {            n2++;            t=t/10;        } while (t!=0);        for (i=0;i < n1; i++)             result = num*b;        //   统一处理进位问题        for (i = 0; i < n1+n2; i++)        {             if (result >= 10)            {                 result[i+1] += result / 10;                 result %= 10;             }        }       bool isBeginZero = false;       j=0;       for (i=n1+n2-1; i>=0; i--)           if (isBeginZero)              c[j++]=result+'0';          else if (result!=0)         {             c[j++]=result+'0';             isBeginZero = true;          }        if (!isBeginZero) c[j++]='0';        c[j]='\0'; } int main() {       char a[MAX_LEN],c[MAX_LEN+10];        int b;       scanf("%s",a);        scanf("%d",&b);        bigNumMul(a,b,c);        printf("%s\n",c);        return 0; }



推荐了解热门学科

java培训Python人工智能Web前端培训PHP培训
区块链培训影视制作培训C++培训产品经理培训
UI设计培训新媒体培训产品经理培训Linux运维
大数据培训智能机器人软件开发




传智播客是一家致力于培养高素质软件开发人才的科技公司“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来,教学研发团队一直致力于打造精品课程资源,不断在产、学、研3个层面创新自己的执教理念与教学方针,并集中“黑马程序员”的优势力量,针对性地出版了计算机系列教材50多册,制作教学视频数+套,发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到,“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员,具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示,“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验,从而多出了更多的项目经验。“为此,传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家,集中研发面向中高级程序员的课程,用以满足企业用人需求,尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程,是在当前主流的初级程序员课程的基础上,增加多领域多行业的含金量项目,从技术的广度和深度上进行拓展“我们希望用5年的时间,打造上百个高含金量的项目,覆盖主流的32个行业。”传智播客课程研发总监于洋表示。




黑马程序员热门视频教程

Python入门教程完整版(懂中文就能学会)零起点打开Java世界的大门
C++| 匠心之作 从0到1入门学编程PHP|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript软件测试入门到精通


在线咨询 我要报名