回西安的第一天又被发短信催着去面试,介于无聊,所以准备去被鄙视下,两个月的实习会让面试那些东西又忘光了。。在其他人都是链表节点的删除、字符串循环左移一位的题目下。。。我幸运的被问了一句“写个大数乘法吧”,So,只好模拟手算过程,然后想边计算边搞进位,结果写的漏洞百出的被鄙视了,话说成天php的,写变量的时候都老容易写出来$。

任何一个数都可以表示成为  x = a(n) * 10^n + a(n-1)*10(n-1) + … + a(0)的形式,

则 x*y = (a(n) * b(n))*10^(2n) + (a(n)*b(n-1) + a(n-1)*b(n))*10^(2n-1) + … + a(0)*b(0)

程序中可以直接按上述公式乘,乘完的结果再做进位的调整

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

void reverse(char *str)
{
     int len = strlen(str);
     int i=0;
     for(i=0;i<len/2;i++)
     {
          char tmp = str[i];
          str[i] = str[len-i-1];
          str[len-i-1] = tmp;
     }
}

void mul(int *ret,char *a,char *b)
{
     int lena = strlen(a);
     int lenb = strlen(b);
     int i,j;
     for(i=0;i<lena;i++)
     {
         for(j=0;j<lenb;j++)
         {
             ret[i+j] = ret[i+j] + (a[i] - '0') * (b[j] - '0');
         }
     }
     for(i=1;i<lena + lenb + 2;i++)
     {
          ret[i] += ret[i-1]/10;
          ret[i-1] = ret[i-1]%10;
     }
}

int main(void)
{
    char a[256],b[256];
    scanf("%s%s",a,b);
    reverse(a);
    reverse(b);
    int lena = strlen(a);
    int lenb = strlen(b);
    int *ret = (int *)malloc(sizeof(int)*(lena + lenb + 2));
    int i=0;
    for(i=0 ; i<lena + lenb + 2;i++)
       ret[i] = 0;
    mul(ret,a,b);
    i = lena + lenb + 1;
    while(ret[i] == 0)
    {
       i--;
       if(i == -1)
         break;
    }
    if(i == -1)
         printf("0\n");
    else
    {
        while(i>=0)
        {
           printf("%d",ret[i]);
           i--;
        }
        printf("\n");
    }
    system("pause");
    return 0;
}
转载请注明来源:Leoncom-《通信公司面试之大数乘法》
Trackback

no comment untill now

Add your comment now