多项式的乘法:大数乘法 和 多项式乘法

看数据结构链表应用讲到他可以处理多项式乘法

实际上也可以拿相似思想做大数相乘只是把输入源从链表变为即可

基本原理:

1把两个数字a和b转换成放到里；或者把数字每位隔离开分别放到里作为位这样更方便乘法处理这样做根本好处是:相乘时候不会造成溢出

2结果长度最大应该是a长度+b长度+1所以定义个这样；

3过程很简单了:a中第i位乘以b中第j位保存在c中第i+j位；

4后期处理注意经过第 3步处理过c中结果每位都可能向高位进位；比如说c[8]=24这时候就要从低位开始把进位部分向高位加次循环即可:

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; //该位最后结果
}

这时候就计算完毕了

但是第3行和第8、9行实际上是可以放到起就是说只要任意次计算导致了c[k]值>10,那么立刻进行进位处理于是提高的后版本是:

for(i=0;i<MAX;i)
for(j=0;j<MAX;j)
{
c[i+j]a[i]*b[j];
c[i+j+1]c[i+j]/10;
c[i+j]%=10;
}

有关进位这个事情多项式就没有这个问题每项系数可以>10不过他也有他自己处理:如果系数为0话就把该项删除呵呵

延伸阅读