|
|
| 题目描述： | 输出两个不超过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) * 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);
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 < '0' or num > '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) * 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) * Int(num2[j]);
}
}
接下来是处理进位的代码：
/* 这个循环用来处理进位的，所以要从result的最后一位一直处理到首位。
* 要注意result的总长度是resultLen+1,有一位是保存result的长度，而
* C语言下标是从0开始，所以result的最后一位的下标就是resultLen，而
* 第一位就是1。*/
for(i = resultLen; i > 1; i--)
{
result[i-1] += result/10;
result = result%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 != 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);
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 < '0' or num > '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) * 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/10;
123 result = result%10;
124 }
125 printf("num1Len:%d\nnum2Len:%d\n", num1Len, num2Len);
126 return result;
127 }
大整数相乘2完整代码 程序运行结果：
总结：
这是一道非常经典而且必须要掌握的题目，所以看到这篇文章的你最好能认真理解一下。
作者：陈栋权
时间：2016/09/17
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，
且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
如有特别用途，请与我联系邮箱：kingchen.gd@foxmail.com
最后有兴趣的同学可以关注我的微信公众号，可以随时及时方便看我的文章。*^_^*
扫码关注或者搜索微信号：King_diary
|
|
QQ群⑧：
窥视卡
雷达卡
发表于 2017-7-10 08:02:08
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡