大數乘法 和 多項式乘法

 看資料結構，連結清單的應用，講到他可以處理多項式的乘法。

實際上也可以拿相似的思想做大數相乘，隻是把輸入源從連結清單變為數組即可。

基本原理：

1，把兩個數字a和b轉換成字元，放到字元數組裡；或者把數字的每一位隔離開分别放到數組裡作為一位，這樣更友善乘法處理。這樣做的根本好處是：相乘的時候不會造成溢出。

2，結果數組的長度，最大應該是a的長度+b的長度+1，是以定義一個這樣的數組；

3，過程很簡單了：a中的第i位乘以b中的第j位，儲存在c中的第i+j位；

4，後期處理。注意，經過第三步處理過的c中的結果，每一位都可能向高位進位；比如說，c[8]=24。這時候就要從低位開始把進位部分向高位加，一次循環即可：

1.      for(i=0;i<N;i++)
2.            for(j=0;j<N;j++)
3.                   *(c+i+j)+=*(a+i) * *(b+j);
4.     // 處理進位
5.      for(i=0;i<N*2-1;i++)
6.      {
7.            *(c+i+1)+=*(c+i)/10;      //進位累加到高位
8.            *(c+i)=*(c+i)%10;          //該位的最後結果
9.      }

這時候就計算完畢了。

但是，第3行和第8、9行實際上是可以放到一起的。就是說，隻要任意一次計算導緻了c[k]的值>10,那麼立刻進行進位處理。于是提高之後的版本是：

1. for(i=0;i<MAX;i++)   
2. for(j=0;j<MAX;j++)   
3. {   
4.     c[i+j]+=a[i]*b[j];   
5.     c[i+j+1]+=c[i+j]/10;   
6.     c[i+j]%=10;   
7. }   

 關于進位這個事情，多項式就沒有這個問題，因為每一項的系數可以>10。不過他也有他自己的處理：如果系數為0的話，就把該項删除，呵呵。

參考文獻：

http://www.cnblogs.com/hoodlum1980/archive/2007/08/15/857067.html

殷人昆，資料結構