华为OJ机试题目:两个大整数相乘(纯C语言实现两…
2018-06-18 04:15:30来源:未知 阅读 ()
题目描述: | 输出两个不超过100位的大整数的乘积。 |
输入: | 输入两个大整数,如1234567 123 |
输出: | 输出乘积,如:151851741 |
样例输入: | 1234567 123 |
样例输出: | 151851741 |
注意:在oj上不能直接套用我的代码,需要将无关的输出去除才行
方法一
思路:
解这道题目最简单的方法就是模拟我们笔算乘法的过程,如:1234×123
只要把这个过程实现,无论多大的数我们都能解决了,是不是很简单。
程序实现:
首先,我们用两个字符串来保存我们的大整数,num1[100], num2[100]
scanf("%s%s", num1, num2);
然后,求num2的每一位与num1的乘积,保存到tempRes中。
过程为:res保存每位相乘的结果,carry用来保存进位,每位相乘之后还要加上进位才是真的结果。将res的个位保存到tempRes中,其他位则为下一位相乘的进位。
for(j = num2Len - 1; j >= 0; j--) { /*计算num1与num2各位相乘的结果,保存到tempRes中 *每一位相乘后与之前的进位相加得出res,将res的个 *位(res%10)保存到tempRes里,然后将res的其余位数 *(res/10)则为进位carry*/ for(i = num1Len-1; i >= 0; i--) { res = Int(num1[i]) * Int(num2[j]) + carry; tempRes[tempResLen--] = Char(res % 10); carry = res / 10; } //tempRes第一位为进位,刚刚的循环是没有算的,最后把进位算上 tempRes[tempResLen] = Char(carry); tempResLen = num1Len; carry = 0; }
再然后,将tempRes与result求和,每求一次,向左偏移一位。res为每位之和再加上进位,这里很重要,然后保存到result里只是res的个位,res为下一位计算的进位。
//由result的末尾开始计算和,算完一次,向左偏移一位 for(k = resultLen-offset; k > (resultLen-offset-num1Len); k--) { res = Int(result[k]) + Int(tempRes[tempResLen--]) + carry; result[k] = Char(res%10); carry = res/10; } result[k] += Int(tempRes[tempResLen] + carry); offset++;
以上两步就是我程序最核心的部分。以下是程序的全部代码。
1 #include<stdio.h> 2 #include<string.h> 3 #include<malloc.h> 4 5 #define and && 6 #define or || 7 #define not ! 8 #define Int(X) (X - '0') 9 #define Char(X) (X + '0') 10 11 char *multiBigInteger(const char *, const char *); 12 int checkNum(const char *); 13 14 int main(void) 15 { 16 char num1[100] = {'\0'}, num2[100] = {'\0'}; 17 while(scanf("%s%s", num1, num2) != EOF) 18 { 19 char *result = "0"; 20 if(strlen(num1) > 100 or strlen(num2) > 100) 21 { 22 printf("ERROR\n"); 23 return 1; 24 } 25 if(checkNum(num1) or checkNum(num2)) 26 { 27 printf("ERROR: input must be an Integer\n"); 28 return 1; 29 } 30 printf("num1:\t%s\nnum2:\t%s\n", num1, num2); 31 result = multiBigInteger(num1, num2); 32 if(result[0] == '0') 33 { 34 int i; 35 printf("result:\t"); 36 for(i = 1; (size_t)i < strlen(result); i++) 37 { 38 printf("%c", result[i]); 39 } 40 printf("\n"); 41 } 42 else 43 { 44 printf("result:\t%s\n", result); 45 } 46 printf("\n"); 47 } 48 return 0; 49 } 50 51 int checkNum(const char *num) 52 { 53 int i; 54 for(i = 0; (size_t)i < strlen(num); i++) 55 { 56 if(num[i] < '0' or num[i] > '9') 57 { 58 return 1; 59 } 60 } 61 return 0; 62 } 63 64 char *multiBigInteger(const char *num1, const char *num2) 65 { 66 char *tempRes = NULL; //用来保存每次相乘的结果 67 char *result = NULL; //用来保存最终结果 68 int tempResLen; //每次相乘结果的最大长度 69 int num1Len = strlen(num1); //num1的长度 70 int num2Len = strlen(num2); //num2的长度 71 int resultLen; //结果的最大长度 72 int i, j, k; //循环计数器 73 int res; //每次一位相乘/相加的结果 74 int carry = 0; //进位 75 int offset = 0; //加法的偏移位 76 resultLen = num1Len + num2Len - 1; //结果长度最大为num1长度和num2长度之和,由于下标从0开始,所以要减一 77 tempResLen = num1Len; //每次num1乘以num2每一位的结果最大长度是num1Len+1,由于下标从0开始,所以减一后约去1,只剩num1Len 78 //初始化result为0 79 result = (char *)malloc((resultLen+2)*sizeof(char)); 80 memset(result, '0', (resultLen+1)*sizeof(char)); 81 result[resultLen+1] = 0; 82 83 tempRes = (char *)malloc((tempResLen+2)*sizeof(char)); 84 for(j = num2Len - 1; j >= 0; j--) 85 { 86 //初始化tempRes每位为0 87 memset(tempRes, '0', (tempResLen+1)*sizeof(char)); 88 /*计算num1与num2各位相乘的结果,保存到tempRes中 89 *每一位相乘后与之前的进位相加得出res,将res的个 90 *位(res%10)保存到tempRes里,然后将res的其余位数 91 *(res/10)则为进位carry*/ 92 for(i = num1Len-1; i >= 0; i--) 93 { 94 res = Int(num1[i]) * Int(num2[j]) + carry; 95 tempRes[tempResLen--] = Char(res % 10); 96 carry = res / 10; 97 } 98 //tempRes第一位为进位,刚刚的循环是没有算的,最后把进位算上 99 tempRes[tempResLen] = Char(carry); 100 tempResLen = num1Len; 101 carry = 0; 102 //由result的末尾开始计算和,算完一次,向左偏移一位 103 for(k = resultLen-offset; k > (resultLen-offset-num1Len); k--) 104 { 105 res = Int(result[k]) + Int(tempRes[tempResLen--]) + carry; 106 result[k] = Char(res%10); 107 carry = res/10; 108 } 109 result[k] += Int(tempRes[tempResLen] + carry); 110 carry = 0; 111 tempResLen = num1Len; 112 offset++; 113 114 } 115 printf("num1Len:%d\nnum2Len:%d\n", num1Len, num2Len); 116 return result; 117 }
以下是程序执行的结果:
看了以上的代码,感觉思路虽然很简单,但是实现起来却很麻烦,那么我们有没有别的方法来实现这个程序呢?答案是有的,接下来我来介绍第二种方法。
方法二:
思路:
简单来说,方法二就是先不算任何的进位,也就是说,将每一位相乘,相加的结果保存到同一个位置,到最后才计算进位。
例如:result[200]用来保存结果,计算98×21,步骤如下
由上面可以看出,result的数据为result[100] = {0, 18, 27, 9}
接下来就处理进位,注意看,巧妙的地方来了:
有result末尾到首位计算:
第一次:result[3] = 9; result[2] = 27;
A.先将result[3]除个位以外的数加给前一位,也就是result[2]:result[2] = result[2]+result[3]/10 = 27 + [9/10]=27; 注:数学里面的[]为取整符。如[0.9] = 0
B.然后把result[3]的个位保存到result[3]:
>> result[3] = result[3]%10 = 9;
第二次,向前一位,result[2] = 27, result[1] = 18;
重复第一次的A、B步骤,求得result[1] = result[1]+result[2] / 10=18+[27/10] = 20;
>> result[2] = result[2] % 10 = 7
第三次,再向前一位,result[1] = 20, result[0] = 0
重复之前的步骤,
>> result[0] = result[0]+result[1]/10=0+[20]/10=2
>> result[1] = result[1] % 10 = 0;
至此,已经算到首位,result此时的结果为:result[100] = {2, 0, 7, 9}可以知道这就是结果:99×21=2079;
核心代码:
先是不进位的各位之和:
for(j = 0; j < num2Len; j++) { for(i = 0; i < num1Len; i++) { /* result第一位是用来保存result长度的,而第二位是保存结果最后的进位的 * 没有进位,则result[1]为0,所以每位相乘之和是从第三位(即result[2]) * 开始。这里是本程序的比较巧妙的地方,需要仔细想想。 * */ result[i+j+2] += Int(num1[i]) * Int(num2[j]); } }
接下来是处理进位的代码:
/* 这个循环用来处理进位的,所以要从result的最后一位一直处理到首位。 * 要注意result的总长度是resultLen+1,有一位是保存result的长度,而 * C语言下标是从0开始,所以result的最后一位的下标就是resultLen,而 * 第一位就是1。*/ for(i = resultLen; i > 1; i--) { result[i-1] += result[i]/10; result[i] = result[i]%10; }
注意:这个方法有一个大坑,就是保存结果的result的数据类型必须至少是int,而不能是char,为什么呢?先想想再打开答案。
/* 因为char类型的数据每个只有1个字节 * 也就是8位,所以保存的最大数值为256 * 而我们这个程序,每位最大为100个9×9=81 * 之和,也就是每个数据必须最大要能保存的数 * 值为8100, 所以char数据类型就不够保存了。 * good luck :-)*/
接下来程序的完整代码:
1 #include<stdio.h> 2 #include<string.h> 3 #include<malloc.h> 4 5 #define and && /**************/ 6 #define or || /* python风格 */ 7 #define not ! /* */ 8 #define Int(X) (X - '0') /**************/ 9 10 int *multiBigInteger(const char *, const char *); 11 int checkNum(const char *); 12 13 int main(void) 14 { 15 char num1[100] = {'\0'}, num2[100] = {'\0'}; 16 printf("Please input two nunber(less than 100 digits):\n> "); 17 while(scanf("%s%s", num1, num2) != EOF) 18 { 19 int *result = NULL; 20 int i, change = 0; 21 //对输入的数据进行检验 22 if(strlen(num1) > 100 or strlen(num2) > 100) 23 { 24 printf("per number must less than 100 digits\n"); 25 return 1; 26 } 27 28 if(checkNum(num1) or checkNum(num2)) 29 { 30 printf("ERROR: input must be an Integer\n"); 31 return 1; 32 } 33 34 printf("num1:\t%s\nnum2:\t%s\n", num1, num2); 35 36 result = multiBigInteger(num1, num2); 37 38 /* 输出结果result,result[0]保存着result的长度, 39 * 所以下标要从1开始 */ 40 printf("result:\t"); 41 for(i = 1; i <= result[0]; i++) 42 { 43 if(result[i] != 0) //这一步用来去掉前导0,第一位为0跳过不输出 44 change = 1; 45 if(not change) 46 { 47 if(i > 1) //这一步用来判断结果是否为0, 48 { //如果结果第二位还是0,就判断为0 49 printf("0"); 50 break; 51 } 52 continue; 53 } 54 printf("%d", result[i]); 55 } 56 printf("\n"); 57 printf("\nPlease input two nunber(less than 100 digits):\n> "); 58 } 59 return 0; 60 } 61 62 //用于检测输入的是否是数字,如果是就返回0,不是就返回1 63 int checkNum(const char *num) 64 { 65 int i; 66 for(i = 0; (size_t)i < strlen(num); i++) 67 { 68 if(num[i] < '0' or num[i] > '9') 69 { 70 return 1; 71 } 72 } 73 return 0; 74 } 75 76 //返回结果result,为一片内存块,类似数组 77 int *multiBigInteger(const char *num1, const char *num2) 78 { 79 int *result = NULL; //用来保存最终结果 80 int num1Len = strlen(num1); //num1的长度 81 int num2Len = strlen(num2); //num2的长度 82 int resultLen; //结果的最大长度 83 int i, j; //循环计数器 84 resultLen = num1Len + num2Len; //结果长度最大为num1长度和num2长度之和 85 //初始化result为0 86 result = (int *)malloc((resultLen+1)*sizeof(int)); 87 memset(result, 0, (resultLen+1)*sizeof(int)); 88 89 result[0] = resultLen; //result的第一位是用来保存result的长度的。 90 /* num1乘以num2,由于这里采用先不进位的算法,所以算法是按从左到右 91 * 按顺序来乘,然后将每位的结果保存到result的每一位中,循环一次 92 * reult就从下一位开始求和。如下:(左边为正常算法,右边为本程序算法) 93 * 94 * 54321 | 54321 95 * × 123 | × 123 96 * ------- | -------- 97 * 162963 | 54321 98 * 108642 | 108642 99 * 54321 | 162963 100 * -------- | --------- 101 * 6681483 | 6681483 102 * 103 * */ 104 for(j = 0; j < num2Len; j++) 105 { 106 for(i = 0; i < num1Len; i++) 107 { 108 /* result第一位是用来保存result长度的,而第二位是保存结果最后的进位的 109 * 没有进位,则result[1]为0,所以每位相乘之和是从第三位(即result[2]) 110 * 开始。这里是本程序的比较巧妙的地方,需要仔细想想。 111 * */ 112 result[i+j+2] += Int(num1[i]) * Int(num2[j]); 113 } 114 } 115 116 /* 这个循环用来处理进位的,所以要从result的最后一位一直处理到首位。 117 * 要注意result的总长度是resultLen+1,有一位是保存result的长度,而 118 * C语言下标是从0开始,所以result的最后一位的下标就是resultLen,而 119 * 第一位就是1。*/ 120 for(i = resultLen; i > 1; i--) 121 { 122 result[i-1] += result[i]/10; 123 result[i] = result[i]%10; 124 } 125 printf("num1Len:%d\nnum2Len:%d\n", num1Len, num2Len); 126 return result; 127 }
程序运行结果:
总结:
这是一道非常经典而且必须要掌握的题目,所以看到这篇文章的你最好能认真理解一下。
作者:陈栋权
时间:2016/09/17
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,
且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
如有特别用途,请与我联系邮箱:kingchen.gd@foxmail.com
最后有兴趣的同学可以关注我的微信公众号,可以随时及时方便看我的文章。*^_^*
扫码关注或者搜索微信号:King_diary
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:5-22 龟兔赛跑 (20分)
下一篇:一些简单的C语言算法
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash