一道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，它也是排序算法的極限。

我非常憤怒自己的低級表現，怎麼批評也不為過。但是實際上也是一次經驗累積，它非常類似應試，需要比較充分的準備以及比較深厚的理論功底。