副标题#e#
我们回忆一下,在我们小时候刚接触多位数的乘法,我们的数学老师会教给我们一个方法,那就是“乘法的竖式计算”。在这里我们就采用该思想解决大数乘法的问题。
以下是我们经常进行乘法的竖式运算:
根据以上的竖式运算,我们实现过程总结如下:
-
先使用两个字符数组保存两个大数据;
-
用第一个数据的个位与第二个数据的所有位相乘,并将每一位的运算结果保存在暂存字符数组temp中,并进行进位调整,即如果该位的数值大于9,就将该数值的十位加到前一位,并将该位的个位保存在原位。
-
将temp与结果数组rst中的数值逆序相加,也就是从两个数组的倒数第一位开始相加。
-
以相同的方法,计算出第一个数据的十位与第二个数据相乘的结果,并保存至temp中。
-
将temp与rst倒数第二位的结果开始逆序相加。
-
第一个数据有几位就将以上过程进行几次。
【注】:对于确定每次与rst的倒数第几位相加时,可以采用一个bit变量存下正在进行第一个数据的第几位数据的运算,在最终相加时,在rst数组的末尾减去bit就是,应该与temp最后一位相加的位数。
#p#副标题#e##p#分页标题#e#
OK! 我们可以带着对这个乘法竖式的重新理解来解决我们的大数乘法问题,以下是C语言实现的代码:
#include <stdio.h>?
#include <stdlib.h>?
#include <string.h>?
#define MAXLEN (100)?
#define RSTMAX (1000000)?
int main(int ac,char **av)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
{?
? ? char Mp1[MAXLEN] = {0},Mp2[MAXLEN] = {0};??
? ? char temp[MAXLEN + 3] = {0},rst[RSTMAX] = {0};?
? ? int? i = 0,j = 0,t = 0,s = 0;?
? ? int? len1 = 0,len2 = 0;?
? ? int? bit = 0;?
??
? ? printf(“============= Welcome to Mutip Calculate ============\n”);?
? ? printf(“Please enter two number you want to calculate : \n”);?
? ? scanf(“%s%s”,Mp1,Mp2);?
? ? len1 = strlen(Mp1);?
? ? len2 = strlen(Mp2);?
? ? for(j = len2 – 1; j >=0; –j){?
? ? ? for(i = len1 – 1,t = len1; i >= 0; –i,–t){?
? ? ? ? ? // let two number not two character to multiply?
? ? ? ? ? temp[t] = (Mp1[i] – 0x30) * (Mp2[j] – 0x30);??
? ? ? ? ? // 0x30 == 48 == ‘0’?
? ? ? }? ? ? ??? ? ? ? ?
? ? ? // adjust temp’s each bit number which more than 9 to between 0 to 9?
? ? ? for(t = len1; t >0; –t){?
? ? ? ? ? if(temp[t] > 9){?
? ? ? ? ? ? ? temp[t-1] += temp[t]/10;?
? ? ? ? ? ? ? temp[t] %= 10;?
? ? ? ? ? }?
? ? ? }?
??
? ? ? // sum the new result to the original result;? ? ? ??
? ? ? for(s = len1 + len2 – bit,t = len1; t >= 0; –s,–t){?
? ? ? ? ? rst[s] += temp[t];?
? ? ? }?
??
? ? ? // ajust the new result which more than 9? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? for(s = len1 + len2; s > 0; –s){?
? ? ? ? ? ? if(rst[s] > 9){?
? ? ? ? ? ? ? ? rst[s-1] += rst[s]/10;?
? ? ? ? ? ? ? ? rst[s] %= 10;?
? ? ? ? ? ? }?
? ? ? ? }?
??
? ? ? ? // bzero the temp array?
? ? ? ? for(t = len1; t >= 0; –t){?
? ? ? ? ? ? temp[t] = 0;?
? ? ? ? }?
? ? ? ? bit++;?
? ? }?
? ? ??
? ? // in order to narmal output the result as a string not a interge?
? ? rst[len1 + len2 + 1] = ‘\0’;?
? ? ??
? ? // switch rst’s each bit to character save into the result array.?
? ? for(s = 0; s <= len1 + len2; ++s){?
? ? ? ? rst[s] += 0x30;?
? ? }?
??
? ? // delete the first zero before output the result.? ??
? ? for(s = 0; s < len1 + len2; ++s){?
? ? ? ? if(0x30 == rst[0]){?
? ? ? ? ? ? for(t = 0; t <= len1 + len2 – s; ++t){?
? ? ? ? ? ? ? ? rst[t] = rst[t+1];?
? ? ? ? ? ? }? ??
? ? ? ? }else{?
? ? ? ? ? ? break;?
? ? ? ? }?
? ? }?
??
? ? // output the result;?
? ? printf(“%s * %s = %s\n”,Mp2,rst);?
? ? printf(“========== Bye Bye ==========\n”);?
? ? return 0;?
}
运行结果如下:
[root@anna-laptop C]# ./Multip??
============= Welcome to Mutip Calculate ============?
Please enter two number you want to calculate :??
123456789?
987654321?
123456789 * 987654321 = 121932631112635269?
========== Bye Bye ==========
回复6:一图道尽程序员的职业发展路线
回复7:年薪10万、30万、50万到底差在哪里?
回复8:25岁时 马云、雷军、周鸿祎等10位科技大佬都在干啥?
回复9:嵌入式系统c语言编程该怎么学?
回复10:看完文章,你会认为linux才是最伟大的系统!
回复11:自学Linux,你该读哪些书?
点住二维码3秒
与10万程序高手做朋友
每天干货喂饱你
(记得识别二维码哟)
?
或微信搜索华清远见,即可关注我们
免费讲座 | 干货分享 | 程序员生活 | 就业招聘
高端IT就业培训专家
m.embedu.org