多项式相乘的问题

Question

项式可以用数组或链表表示。用数组表示多项式有压缩与非压缩两种形式，
例如,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
}

Answer 1

//详细完整代码例子，采用压缩形式且以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;
}//endvoid 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*/

Answer 2

//另一个详细的例子
/*－－－－－－－－－－－－－－－－－－－－－－－
以下采用数组的压缩形式 以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*/