多项式相乘的问题
设多项式h(x) = f(x)*g(x),其中
f(x) = a(0)*pow(x,n) + a(1)*pow(x,n-1) + a(2)*pow(x,n-2) + ... + a(n-1)*x + a(n)
g(x) = b(0)*pow(x,n) + b(1)*pow(x,n-1) + b(3)*pow(x,n-2) + ... + b(m-1)*x + b(m)
h(x) = c(0)*pow(x,n) + c(1)*pow(x,n-1) + c(3)*pow(x,n-2) + ... + c(l-1)*x + c(l) (l= m+n)
如何用程序表示出上面的式子相乘，比如：
f(x) = 2*pow(x,2) + 3*x + 1
g(x) = 3*pow(x,3) + 4*x + 1
求h(x) = f(x) * g(x)
问题点数：100、回复次数：3Top
1 楼tpProgramer（tp编程者）回复于 2002-04-05 17:56:13 得分 100
项式可以用数组或链表表示。用数组表示多项式有压缩与非压缩两种形式，
例如,f(x) = 6*pow(x,7) - 3*pow(x,4) + 2*x +16
(1)非压缩存储方式（即有零系数）
幂指数 7 6 5 4 3 2 1 0
系 数 6 0 0 -3 0 0 2 16
(2)压缩存储形式（即没有零系数）
幂指数 7 4 1 0
系 数 6 -3 2 16
(3)多项式的链式表示：
{f} -> {7,6} -> {4,3} -> {1,2} -> {0,16} -> NULL
多项式相乘，按不同表示形式，有多种算法：
(1)数组的非压缩形式
f与g的逐项相乘，并合并到相应h的项上去。具体采用二重循环，对每个f项,逐个乘以g的项，
并合并到h的相应项上。
r=m+n;
for(i=0;i<r;i++)
{
h[0][i]=r-i;
h[1][i]=0;
}
for(i=0;i<=m;i++)
{
for(j=0;j<=m;j++)
{
h[1][i+j] = f[1][i]*g[1][j];
}//end for j
}//end for i
这种算法简单，但是效率差。
(2)数组的压缩形式
<1>以f、g为主导的算法：
由f的第i项与g的第j项形成一个新项。若此项h中已有，则应同类项合并，
合并后系数为0则压缩掉；若此项h中没有，则应插入。
为便于寻找h中同类项，在h中附加一个标志--maxint，以表示多项式的尾。
void mult1(ta f, ta g, int n, int m, ta h, int &r)
{
int i,j,k,kk,kp;
int p;
double c;
k=0;
h[0][0]=-MAXINT;
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
p=f[0][i]+g[0][j]; //两项相乘以后，x的幂
c=f[1][i]*g[1][j]; //两项相乘以后，x的系数
kk=0;
while(p<h[0][kk]) //在h[0][kk]中找到相乘以后项的位置
kk+=1;
if(p==h[0][kk]) //如果这一项在h中存在,则系数加上新项的系数
{
h[1][kk]+=c;
if(fabs(h[1][kk]))<1e-6) //如果合并后的项系数接近0,则从h中删除此项
{
for(kp=kk;kp<=k;kp++)
{
h[0][kp] = h[0][kp+1];
h[1][kp] = h[1][kp+1];
}//end for kp
}//end if fabs
}else{ //如果这一项在h中不存在，则插入此项
for(kp=k;kp>=kk;kp--)
{
h[0][kp+1] = h[0][kp];
h[1][kp+1] = h[1][kp];
}
h[0][kk] = p;
h[1][kk] = c;
k+=1;
}//end if p
}//end for j
}//end for i
r=m+n;
}
<2>以h为主导的算法。该算法以r为主线，h的第r项(r:m+n->0)是由若干对(i,j)相关的项合并而成。
它满足：f[0][i]+g[0][j]=r,并且系数不为零。若又这样的项，便放入h中。
为寻找所有(i,j)，其方法为：f的幂从大到小搜索，g的幂则由小到大地变化，以寻找(i,j)。为此，
i:0->n, j:m->0。
若 f[0][i] + g[0][j] >r ，则i增大，以减小 f[0][i];
若 f[0][i] + g[0][j] <r , 则j变小，以加大 g[0][j];
若 f[0][i] + g[0][j] =r , 则合并该项，并继续以上i,j的变化，直到f或者g中有一个遍历完毕
（即i、j到边界），停止合并。
合并后的项若系数为零，则不添入h,否则添入h。
void mult2(ta f ,ta g, int n, int m, ta h, int &k)
{
int i,j,r;
int p;
double c;
k=0;
for(r=n+m;r>=0;r--)
{
c=0;
i=0;
j=m;
do{
p=f[0][i] + g[0][j];
if(p>r)
i++;
else if(p<r)
j--;
else{
c+=f[1][i]*g[1][j];
i++;
j--;
}//end if p
}while((i>n) || (j<0))
if(fabs(c)>1e-6)
{
h[0][k] = r;
h[1][k] = c;
k++;
}//end if fabs
}//for r
}
(3)链表形式的算法
链表的算法与数组形式的算法是一致的。数组是逐个数组元素进行处理，而链表则是逐个节点进行处理。
但对于(2)<2>的算法，由于单向链表不能象数组那样访问，因此对幂由小到大变化，即应先将链表指向倒置。
设reverse为将链倒置的函数。
typedef struct node* ptr;
struct node
{
int p;
float c;
ptr next;
};
void mult3(ptr f, prt g,ptr h)
{
ptr fg,gp,hp,q;
int maxp,p;
int r;
double c;
maxp = f->p+g->p;
new(h);
hp=h;
reverse(g);
for(r=maxp;r>=0;r--)
{
c=0;
fp=f;
gp=g;
while((fp!=NULL) && (gp!=NULL))
{
p=fp->p + gp->p;
if(p>r)
fp= fp->next;
else if(p<r)
gp= gp->next;
else{
c+= fp->c*gp->c;
fp= fp->next;
gp= gp->next;
}
}//end while fp
if(fabs(c)>1e-6)
{
new(q);
q->p = r;
q->c = c;
q->next = NULL;
hp->next =q;
hp =q;
}
}//end for r
hp=h;
h=h->next;
delete(hp);
}
void reverse(ptr q)
{
ptr p1,p2;
if(q!=NULL)
{
p1=q->next;
q->next = NULL;
while(p1!=NULL)
{
p2=p1->next;
p1->next =q;
q=p1;
p1=p2;
}//end while p1
}//end if q
}Top
2 楼tpProgramer（tp编程者）回复于 2002-04-05 17:58:50 得分 0
//详细完整代码例子，采用压缩形式且以f、g为主导的算法：
/*
例子：
f(x) = 2*pow(x,2) + 3*x + 1
g(x) = 3*pow(x,3) + 4*x + 1
求h(x) = f(x) * g(x)
*/
#include <iostream>
#include <math.h>
using namespace std;
typedef int ** ta ;
const int MAXINT =65535;
const int m=3; //f(x)的项数
const int n=4; //g(x)的项数
const int f_m[] ={2,1,0}; //f(x)的幂
const int f_x[] ={2,3,1}; //f(x)的系数
const int g_m[] ={4,3,1,0}; //g(x)的幂
const int g_x[] ={3,6,4,1}; //g(x)的系数
void create_arr(ta f,ta g,int n, int m, ta h);
void mult1(ta f, ta g, int n, int m ,ta h, int &r);
void print_arr(ta h,int r);
void destroy_arr(ta f,ta g,ta h);
void create_arr(ta f,ta g, ta h)
{
f[0] = new int[m];
f[1] = new int[m];
for(long i=0;i<m;i++)
{
f[0][i] = f_m[i]; //幂
f[1][i] = f_x[i]; //系数
}
g[0]=new int[n];
g[1]=new int[n];
for(i=0;i<n;i++)
{
g[0][i] = g_m[i]; //幂
g[1][i] = g_x[i]; //系数
}
h[0] = new int[m*n];
h[1] = new int[m*n];
for(i=0;i<m*n;i++)
{
h[0][i]=0; //幂
h[1][i]=0; //系数
}
}
void mult1(ta f, ta g, int n, int m ,ta h, int &r)
{
int i,j,k,kk,kp;
int p;
double c;
k=0;
h[0][0]=-MAXINT;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
p=f[0][i] + g[0][j];
c=f[1][i] * g[1][j];
kk=0;
while(p<h[0][kk])
kk++;
if(p==h[0][kk]) //如果此幂在h中存在
{
h[1][kk]+=c;
if(fabs(h[1][kk])<1e-6)
{
for(kp=kk;kp<=k;kp++)
{
h[0][kp] = h[0][kp+1];
h[1][kp] = h[1][kp+1];
}//end for kp
}//end if fabs
}else{ //如果此幂在h中存在
for(kp=k;kp>=kk;kp--)
{
h[0][kp+1] = h[0][kp];
h[1][kp+1] = h[1][kp];
}
h[0][kk] = p;
h[1][kk] = c;
k++;
}//end if p
}//end for j
}//end for i
r= m+n;
}//end
void print_arr(ta h, int r)
{
int i;
cout<<" 幂:";
for(i=0;i<r;i++)
{
cout.width(3);
cout<<h[0][i];
}
cout<<endl<<"系数:";
for(i=0;i<r;i++)
{
cout.width(3);
cout<<h[1][i];
}
}
void destroy_arr(ta f,ta g,ta h)
{
delete f[0];
delete f[1];
delete f;
delete g[0];
delete g[1];
delete g;
delete h[0];
delete h[1];
delete h;
}
void main()
{
ta f,g,h;
f=new int*[2];
g=new int*[2];
h=new int*[2];
int r;
create_arr(f,g,h);
mult1(f,g,m,n,h,r);
print_arr(h,r);
destroy_arr(f,g,h);
cin.get();
}
/*
输出：
幂: 6 5 4 3 2 1 0
系数: 6 21 21 14 14 7 1
*/
Top
3 楼tpProgramer（tp编程者）回复于 2002-04-06 10:22:00 得分 0
//另一个详细的例子
/*－－－－－－－－－－－－－－－－－－－－－－－
以下采用数组的压缩形式 以h为主导的算法：
(采用了结构存储而不是二维数组,表现更为清晰)
－－－－－－－－－－－－－－－－－－－－－－－*/
/*
例子：
f(x) = 2*pow(x,2) + 3*x + 1
g(x) = 3*pow(x,4) + 6*pow(x,3) + 4*x + 1
求h(x) = f(x) * g(x)
*/
#include <iostream>
#include <math.h>
using namespace std;
struct node
{
int p; //幂
float c; //系数
};
const int MAXINT =65535;
const int n=3; //f(x)的项数
const int m=4; //g(x)的项数
const int f_m[] ={2,1,0}; //f(x)的幂
const int f_x[] ={2,3,1}; //f(x)的系数
const int g_m[] ={4,3,1,0}; //g(x)的幂
const int g_x[] ={3,6,4,1}; //g(x)的系数
void create_arr(node f[],node g[],node h[]);
void mult(node f[],node g[],int n,int m,node h[],int &k);
void print_arr(node h[],const int k);
/*
f[]: 要填充的 f(x)
g[]: 要填充的 g(x)
h[]: 要初始化为0的h(x)
*/
void create_arr(node f[], node g[], node h[])
{
long i;
for(i=0;i<n;i++)
{
f[i].p =f_m[i];
f[i].c =f_x[i];
}
for(i=0;i<m;i++)
{
g[i].p = g_m[i];
g[i].c = g_x[i];
}
for(i=0;i<m*n;i++)
{
h[i].p =0;
h[i].c =0;
}
}
/*
f[], n: f(x)以及其项数
g[], m: g(x)以及其项数
h[], k: 返回的h(x)以及其项数 ,h(x)=f(x)*g(x)
*/
void mult(node f[],node g[],int n,int m,node h[],int &k)
{
int i,j,r;
int p;
double c;
k=0;
for(r=m+n;r>=0;r--)
{
c=0;
i=0;
j=m-1;
do{
p=f[i].p + g[j].p;
if(p>r)
i++;
else if(p<r)
j--;
else{
c+= f[i].c*g[j].c;
i++;
j--;
}
}while((i<n) && (j>=0));
if(fabs(c)>1e-6)
{
h[k].p = r;
h[k].c = c;
k++;
}
}
}
/*
h[], k: 要打印的h(x)以及其项数
*/
void print_arr(node h[],const int k)
{
int i;
cout<<" 幂:";
for(i=0;i<k;i++)
{
cout.width(3);
cout<<h[i].p;
}
cout<<endl;
cout<<"系数:";
for(i=0;i<k;i++)
{
cout.width(3);
cout<<h[i].c;
}
cout<<endl;
}
void main(void)
{
node f[n], g[m], h[m*n];
int k;
create_arr(f,g,h);
mult(f,g,n,m,h,k);
print_arr(h,k);
cin.get();
}
/*
输出:
幂: 6 5 4 3 2 1 0
系数: 6 21 21 14 14 7 1
*/Top
