[筆記]一道C語言面試題：大整數乘法，整數乘法

[筆記]一道C語言面試題：大整數乘法，整數乘法

題目：輸入兩個數字字符串，如“1234567890”和“987654321”，返回二者相乘的結果字符串，如本例返回為“1219326311126352690”。

來源：某500強企業面試題目

思路：從尾部到頭部，對兩個字串的每個數字分別相乘，並放入結果字符串相應的位置。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *BigNumMultiply(const char *n1, const char *n2)
{
    // quit if n1 or n2 is invalid
    if (!n1 || !n2) {
        return NULL;
    }

    // get length
    int Len1 = strlen(n1);
    int Len2 = strlen(n2);
    int Len = Len1 + Len2;

    // allocate result buffer
    char *ret = (char *)malloc(Len + 1);
    if (!ret) {
        return NULL;
    }
    memset(ret, 0, Len + 1);

    // multiply
    for (int i = Len1 - 1; i >= 0; --i) {
        for (int j = Len2 - 1; j >= 0; --j) {
            int k = i + j + 1;
            // multiply digit by digit
            ret[k] += (n1[i] - '0') * (n2[j] - '0');
            
            // add to upper position
            if (ret[k] >= 10){
                ret[k - 1] += ret[k] / 10;
                ret[k] = ret[k] % 10;
            }
        }
    }

    // handle first 0
    int d = ret[0] == 0 ? 1 : 0;
    for (int i = 0; i < Len - d; ++i) {
        ret[i] = ret[i + d] + '0';
    }
    ret[Len - d] = '\0';

    return ret;
}

int main(int argc, char* argv[])
{
    char n1[] = "1234567890";
    char n2[] = "987654321";
    char *ret = BigNumMultiply(n1, n2);
    printf("%s * %s = %s\n", n1, n2, ret);
    free(ret);
    ret = NULL;

    getchar();
    return 0;
}

從工程化角度考慮，有幾點需要注意：

1、輸入的字符串是否有效？
    上面的代碼只判斷了是否為空，實際上還有可能輸入的字符串並非有效的數字字符串，如“12gh34”，這種也需要返回NULL。

2、前導0的處理
    a位數與b位數相乘，結果長度可能為a+b，如9*99=891；也可能a+b-1是如 10*100=1000。
    在代碼的最後部分，對a+b-1的類型進行了移位處理，壓縮掉了前導的0。

從編程角度考慮，有幾點需要注意：

1、字符串下標從小到大，是從高位到低位。如n=“123”，最高位n[0]=1，最低位n[2]=3。

2、字符ASCII碼與字符的轉換，如n[3]=5這是純數字，而+'0'後有n[3]='5'這就是字符了。

3、數字交叉相乘的進位處理，通過 >=10來判斷進位，此處注意不要寫成>10；另外注意多次疊加，所以使用 +=

4、malloc()的返回值是(void *)，為了讓編譯器happy，需要強制轉為(char *)，而且最後需要free來釋放它申請的內存。

5、字符'0'和字符串“0”的區別

C語言編程，用分治法實現大整數乘法

很大的數，只能用字符串，要不然溢出
這個問題有兩個方式解決，一個就是乘法的定義，是乘數的累加
那麼做法就是乘數多次累加，而被乘數每次減去1，直到被乘數為零跳出循環
那麼這裡就需要兩個子函數，一個是大數的加法，一個是大數的減去1的算法

另一個方式，還記得當年小學學過的乘法的豎式嗎？
如
12 -----(1)

X 12 ------(2)

----------
24 ----(3)

12 ------(4)

---------
144 --------(5)

這樣就轉行為計算（3）（4）等要是多位數，那麼（3）（4）會很多，計算這些的和就是了
最終的到的（5）就是結果
那麼這個問題也是兩個子函數，一個是大數的加法，就是計算（3）（4）等的和
一個是（1）和（2）的每位數的乘法
 

c語言大整數乘法問題

你的第一個for循環裡面應該用j而不是i吧？

#include<stdio.h>
#include<string.h>

#define max 10

int main(void)
{
int i, j, an[max];
memset(an, 0, sizeof(an));
an[0] = 16;
an[5] = 57;

for (j = 0; j < max; j++) {
if (an[j] >= 10) {
an[j+1] = an[j+1] + an[j]/10;
an[j] %= 10;
}
}
for (i = 0; i < max; i++)
printf("%d", an[i]);
return 0;
}