兩個大數相乘、精度很高的小數相乘（小數點後位數沒有限制，請寫一個高精度算法）

【轉】http://www.cppblog.com/dotaqop/articles/148190.html

算法提示：

          輸入 string a, string b； 計算string c=a*b; 傳回 c;

1，    紀錄小數點在a,b中的位置l1,l2， 則需要小數點後移動位置數為l=length(a)+length(b)-l1-l2-2;

2，    去掉a,b中的小數點，（a,b小數點後移，使a,b變為整數）

3，    計算c=a*b; （同整數的大數相乘算法）

4，    輸出c,（注意在輸出倒數第l個數時，輸出一個小數點。若是輸出的數少于l個，就補0）

du51(郁郁思揚)的答案：

下面是兩個大數的相乘的算法：

原理：

大數A：A1A2A3A4...An 轉換為n項多項式PolyA 大數B：B1B2B3B4...Bm 轉換為m項多項式PolyB 這樣将大數乘法轉換為多項式PolyA * PolyB ,然後将多項式計算結果轉換為大數表示。

# include<stdio.h>

# include<string.h>

# include<malloc.h>

void

multiply(

char

* a,

char

* b,

char

* c)

{

int

i,j,ca,cb,* s;

ca=

strlen

(a);

cb=

strlen

(b);

s=(

int

*)

malloc

(

sizeof

(

int

)*(ca+cb)); // strlen(a)的數a * strlen(b)的數b一定少于strlen(a)+strlen(b)的數

// 初始化數組

for

(i=0;i<ca+cb;i++)

{

s[i]=0;

} // 各個位上的數分别相乘，并存入相應位的數組成員中（原理類似于國小的兩個數相乘的方式）

for

(i=0;i<ca;i++)

for

(j=0;j<cb;j++)

s[i+j+1]+=(a[i]-

'0'

)*(b[j]-

'0'

); //這裡為什麼不是s[i+j]?而是s[i+j+1] ------為了統一操作,s[0]是用來存放最高位的進位,否則需要分開進行判斷

// 處理有進位的數位

for

(i=ca+cb-1;i>=0;i--)

{

if

(s[i]>=10)

{

s[i-1]+=s[i]/10;

s[i]%=10;

}

}

// 清除高位的0

i=0;

while

(s[i]==0)

i++;

for

(j=0;i<ca+cb;i++,j++)

c[j]=s[i]+

'0'

;

c[j]=

'\0'

;

free

(s);

}