華為OJ機試題目：兩個大整數相乘(純C語言實現兩個大整數相乘，兩種方法實現大數相乘)，華為oj
![]()
題目描述：
輸出兩個不超過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 }
大整數相乘2完整代碼
程序運行結果：
總結：
這是一道非常經典而且必須要掌握的題目，所以看到這篇文章的你最好能認真理解一下。
作者：陳棟權
時間：2016/09/17
本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，
且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。
如有特別用途，請與我聯系郵箱：[email protected]
最後有興趣的同學可以關注我的微信公眾號，可以隨時及時方便看我的文章。*^_^*
掃碼關注或者搜索微信號：King_diary
