华为笔试准备 --- 大数相乘

下午写了一会，借鉴了别人的思想，很给力的乘法算法，一目了然，虽然听说最快的大数相乘是傅立叶算法...（只记得是FFT...）

又在边界问题出错了，下次错的话要在纸上多画一下，算一下，就明晰了

/********************************************
要求基本与相加一样
void mul (const char *num1, const char *num2, char *result)
********************************************/

#include<stdio.h>
#include<string.h>
/************************************************
编程思路：
基本与大数相加一样，思路清晰以后，注意边界问题。
不妨说说区别，大数相加得到最大大数的位数最多是len_max+1，
大数相乘，得到最大的数位数不会超过2×len_max;

此题的精华在于乘法的算法(

    for(i = len_max - 1; i >= len_max - len1 ; i--)
        for(j = i; j >= len_max -len2 ; j--)
            p_r[len_r-1-(len_max-i-1)-(len_max-j-1)] += p_num1[i] * p_num2[j];

出错的地方：
在乘法算法的时候，边界问题，这里再出错，不妨在纸上画画。
    p_r[len_r-1-(len_max-i-1)-(len_max-j-1)]，是不是很复杂，想明白就不会忘了。

*************************************************/
void mul (const char *num1, const char *num2, char *result)
{
    int len1, len2, len_max, len_r, i, j, flag1, flag2;

    char *p_num1, *p_num2, *p_r;

    len1 = strlen(num1);
    len2 = strlen(num2);

    len_max = (len1 > len2) ? len1 : len2;
    len_r = 2 * len_max;

    p_num1 = (char *)malloc(sizeof(char) * len_max);
    p_num2 = (char *)malloc(sizeof(char) * len_max);
    p_r = (char *)malloc(sizeof(char) * len_r);

    memset(p_num1, 0 , sizeof(char) * len_max);
    memset(p_num2, 0 , sizeof(char) * len_max);
    memset(p_r, 0 , sizeof(char) * len_r);

    flag1 = (num1[0] == '-') ? 1 : 0;
    for(i = len1 - 1, j = 0; i >= 0 + flag1; i--,j++)
    {    p_num1[len_max-1-j] = num1[i] - '0';

    }

    flag2 = (num2[0] == '-') ? 1 : 0;
    for(i = len2 - 1, j = 0; i >= 0 + flag2; i--,j++)
        p_num2[len_max-1-j] = num2[i] - '0';
    //申请空间，字符转变为整型

    for(i = len_max - 1; i >= len_max - len1 ; i--)
        for(j = i; j >= len_max -len2 ; j--)
            p_r[len_r-1-(len_max-i-1)-(len_max-j-1)] += p_num1[i] * p_num2[j];

    //运算结果低位到高位依次存在p_r向前的数组下标中

    for(i = len_r - 1; i > 0 ; i--)
    {
        if(p_r[i] >= 10)
        {
            p_r[i-1] += p_r[i]/10;
            p_r[i] = p_r[i] % 10;
        }
    }
    //进位操作

    i = j = 0;
     while(p_r[i] == 0)
      i++;
    if(flag1 == flag2)//符号相同
    {
        while(i < len_r)
            result[j++] = p_r[i++] + '0';
        result[j] = '\0';
    }
    else //符号不同
    {
        result[0] = '-';
        while(i < len_r)
        {    printf("i = %d, p_r[i] = %d, \n", i,p_r[i]);
            result[1+(j++)] = p_r[i++] + '0';

        }
        result[j+1] = '\0';
    }


    return result;
}

int main(int argc, char **argv)
{
    char result[100] = {0};

    char *p1 = "35";
    char *p2 = "-120";

    mul(p1, p2, result);
    printf("result = %s", result);
    while(1);

}