一道c的面试题，大数相乘（转）

一道c的面试题，大数相乘（转）

这是我亲身经历的一个面试题目，并且表现的是整个面试里面最为糟糕的环节，令我十分恼火。回来以后我在tc2.0上写它，发现依然花费了我相当多的时间用于改错和调试（从这一点来看，我面试里的表现也算正常了）。尽管这个问题看起来是如此的简单。当然，这里面有我对c 和c＋＋的生疏和不熟练也有很大关系，此外是对算法的学习和研究还没有完成，还处于一个准备阶段。

题干：输入两个较大的数，输出相乘的结果。

意思也就是两个数很大，超出了int的存储范围。

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define N 100

void GetDigits(int *a,char *s);

void multiply(int *a,int *b,int *c);

main()

{

    char s1[N],s2[N];

    int i,j,a[N],b[N],c[N*2];

    printf("/n input number a: ");

    scanf("%s",s1);

    printf("/n input number b: ");

    scanf("%s",s2);

    //把输入的字符串，按位存放到数组

    GetDigits(a,s1);

    GetDigits(b,s2);

    multiply(a,b,c);

    //找到最高位

    j=N*2-1;

    while(c[j]==0)

        j--;

   //打印计算结果

    printf("/n %s * %s=",s1,s2);

    for(i=j;i>=0;i--)

        printf("%d",c[i]);

}

void GetDigits(int *a, char *s)

{

   int i;

   char digit;

   int len=strlen(s);

   for(i=0;i<N;i++)

    *(a+i)=0;

   for(i=0;i<len;i++)

   {

        digit=*(s+i);

        *(a+len-1-i) = digit - '0';

   }

}

void multiply(int *a,int *b,int *c)

{

     int i,j;

      //先把结果数组设置为0

     for(i=0;i<N*2;i++)

          *(c+i)=0;

     for(i=0;i<N;i++)

           for(j=0;j<N;j++)

                  *(c+i+j)+=*(a+i) * *(b+j);

    // 处理进位

     for(i=0;i<N*2-1;i++)

     {

           *(c+i+1)+=*(c+i)/10;      //进位累加到高位

           *(c+i)=*(c+i)%10;          //该位的最后结果

     }

}

当我贴出这些代码时，它们基本通过简单的测试。

大致的过程是，输入两个相乘的数字的字符串（没有对输入数字的合法性进行检查），然后按位存入较大的数组，然后循环按位相乘并累加。最后从低位到高位依次完成进位操作。这里面的问题是，一个是int数组每一个元素只存储0～9，一个byte就可以容纳2个数据位了，而现在是一位占用了4个byte，在空间上有巨大浪费。所以其实可以压缩。另外一点是相乘函数，实际上可以将两个因子的位数作为参数传递，以避免为0的那些高位的不必要的累加。

此外，我还答错了一个题目，冒泡排序的时间复杂度，实际上是从1累加到n，那么应该是n的平方才对。。。而我的回答居然是快速排序的复杂度，实际快速排序的时间n log n，它也是排序算法的极限。

我非常愤怒自己的低级表现，怎么批评也不为过。但是实际上也是一次经验累积，它非常类似应试，需要比较充分的准备以及比较深厚的理论功底。