线性表表示一元多项式
试题类型:编程题    难度:困难

用线性表表示一元多项式及相加运算。


提示:

在数学上,一个一元n次多项式可以按照升幂写成

Pn(x)= p0 + p1x + p2x2 + …… + pnxn

它由n+1个系数唯一确定。因此,一个一元n次多项式可以用一个线性表P来表示:

P = (p0,p1,p2,……,pn)

多项式每一项的指数隐含在线性表的序号里。假设Q是另外一个一元m次多项式,同样也可以用线性表Q来表示

Q = (q0,q1,q2,q2,……,qm)

如果m<n,则P+Q= Pn(x)+ Qm(x)

因此,多项式P和Q相加的结果可以用线性表R表示

R =(p0+ q0,p1+ q1,p2+ q2,……,pm+ qm,pm+1,……,pn)

由此可以看出,一元n次多项式在计算机中可以用线性表来表示,其加法运算也可以在线性表的基础上进行。但在实际应用中,多项式的次数可能很高并且变化很大时,使得线性表最大长度很难确定,特别是在处理类似如下多项式时

T(x)= 12x2 + 2x12000+3x30000

虽然多项式只有3项非零元素,但仍然需要一个长度为30000的线性表来表示,造成对内存空间的浪费。在程序设计中,这种浪费是应当避免的。可以考虑用线性表存储多项式每项系数的同时,也存储相应的指数,这样就可以不用存储多项式的非零项了。

一般情况下,一元n次多项式也可以写成

Pn(x)= p1xe1+ p2xe2 + …… + pmxem

其中,pi是指数为ei项的非零系数,并且满足

0<=e1< e2<……<em=n

因此,若用一个长度为m,且每个元素有两个数据项(系数项和指数项)的线性表,便可唯一确定多项式P(x)

P = ((p1,e1),(p1,e2),……,(pm,em))

上面的式子在每项都不为零的情况下,仅只比存储每项系数的方案多存储一倍的数据。但是对于T(x)类的多项式,这种表示将极大节省存储空间。

用线性表存储多项式可以采用两种存储结构,一种是顺序存储结构,一种是链式存储结构。在实际应用中,具体采用什么存储结构,则要视作什么运算而定。一般来说如果仅是求多项式值的运算,宜采用顺序存储结构,当需要修改多项式的系数和值时宜采用链式存储结构。

例如,多项式

P(x)= 12 + 2x3+8x5+11x6

线性表的表示为

P = ((12,0),(2,3),(8,5),(11,6))

28.png

29.png

全部题解
线性表表示一元多项式
编程训练营官方题解

一元多项式相加的运算规则非常简单,两个多项式中指数相同的项对应系数相加,若相加的和不为零,则构成相加结果多项式中的一项,所有指数不相同的项均复制到相加结果多项式中。

下面用Java语言给出一元多项式表示及加法运算案例。前面讨论过,用线性表存储多项式时,宜采用系数项和指数项同时存储的结构。因此在案例中定义了PolyData类,用于存储多项式的项数据。

package com.milihua.algorithm.lineartable;
public class PolyData {
 /**
     * 多项式系数项
     */
public int coef;
 /**
     * 多项式指数项
     */
public int expn;
 /**
     * 多项式项构造函数
     */
PolyData(int coef,int expn){
    this.coef = coef;
    this.expn = expn;
}
public int getCoef() {
    return coef;
}
public void setCoef(int coef) {
    this.coef = coef;
}
public int getExpn() {
    return expn;
}
public void setExpn(int expn) {
    this.expn = expn;
}
}

多项式存储采用LinkedList类,LinkedList是一个双向链表,当数据量很大或者操作很频繁的情况下,添加和删除元素时具有比ArrayList更好的性能。

package com.milihua.algorithm.lineartable;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
public class Polynomial {
 
/**
 * 存储第一个多项式的链表
 */
LinkedList<PolyData> polyListOne = new LinkedList<PolyData>();
 
/**
 * 存储第二个多项式的链表
 */
LinkedList<PolyData> polyListTwo = new LinkedList<PolyData>();
 
/**
 * 存储运算结果的多项式链表
 */
LinkedList<PolyData> polyListResult = new LinkedList<PolyData>();
 
/**
 * 添加数据到链表尾部
 *
 * @param inPolyData
 * @return
 */
 
public void addLastPol(LinkedList<PolyData> list, PolyData inPolyData) {
 
    list.addLast(inPolyData);
}
 
/**
 * 添加数据到链表
 *
 * @param inPolyData
 * @return
 */
 
public void addPol(LinkedList<PolyData> list, PolyData inPolyData) {
 
    list.add(inPolyData);
}
 
/**
 * 比较每项的指数大小
 *
 * @param aExpen
 * @param bExpn
 * @return 0两个指数相等,1第一个链表的指数大,-1第二个链表的指数大
 */
 
public int compExpn(int aExpen, int bExpn) {
 
    if (aExpen == bExpn) {
 
        return 0;
 
    } else if (aExpen > bExpn) {
 
        return 1;
 
    } else {
 
        return -1;
 
    }
 
}
 
/**
 * 两个多项式链表相加
 *
 * @return
 */
 
public void addPol() {
 
    for (Iterator<PolyData> iter = polyListOne.iterator(); iter.hasNext();) {
        PolyData poly = iter.next();
        for (Iterator<PolyData> iterTwo = polyListTwo.iterator(); iterTwo.hasNext();) {
            PolyData polyTwo = iterTwo.next();
            switch (compExpn(poly.expn, polyTwo.expn)) {
            case 0:
                PolyData newPolyData = new PolyData(poly.coef + polyTwo.coef, poly.expn);
                polyListResult.add(newPolyData);
                polyListTwo.remove(polyTwo);
                break;
            case 1:
                polyListResult.add(polyTwo);
                polyListResult.add(poly);
                polyListTwo.remove(polyTwo);
                break;
            case -1:
                polyListResult.add(poly);
                polyListResult.add(polyTwo);
                polyListTwo.remove(polyTwo);
                break;
            }  
            break;
        }
   
    }
 
}
 
/**
 * 遍历链表并显示出来
 *
 * @param list
 */
 
public void display(LinkedList<PolyData> list) {
 
    for (Iterator<PolyData> iter = list.iterator(); iter.hasNext();) {
        PolyData poly = iter.next();
        System.out.print(poly.getCoef() + "x^" + poly.getExpn() + "+");
    }
    System.out.println();
 
}
 
public LinkedList<PolyData> getPolyListOne() {
    return polyListOne;
}
 
public void setPolyListOne(LinkedList<PolyData> polyListOne) {
    this.polyListOne = polyListOne;
}
 
public LinkedList<PolyData> getPolyListTwo() {
    return polyListTwo;
}
 
public void setPolyListTwo(LinkedList<PolyData> polyListTwo) {
    this.polyListTwo = polyListTwo;
}
 
public LinkedList<PolyData> getPolyListResult() {
    return polyListResult;
}
 
public void setPolyListResult(LinkedList<PolyData> polyListResult) {
    this.polyListResult = polyListResult;
}
}

Polynomial类是案例文件的主要处理类,在类中声明了三个LinkedList类,分别存储第一个多项式、第二个多项式以及两个多项式相加运算的结果。

Polynomial类的addPol()方法用于执行两个多项式的相加运算,具体算法过程是:

1、遍历第一个多项式;

2、在遍历过程中,处理每一个单项;

(1)遍历第二个多项式;

(2)比较两个单项式的指数;

(3)若指数相同,则两个单项式的系数相加,并形成新的单项式添加到运算结果列表中;若指数不相同,则两个单项式都添加到运算结果列表中。

addPol算法的执行频率为n*m,n为第一个多项式的单项式个数,m为第二个多项式的单项式个数,其算法复杂度为O(n^2)。

PolynomialTest类为测试类,代码如下。

package unittest;
import java.util.Scanner;
import com.milihua.algorithm.lineartable.PolyData;
import com.milihua.algorithm.lineartable.Polynomial;
 
public class PolynomialTest {
public static void main(String[] args) {
   
    Polynomial  poly = new Polynomial();
     //声明Scanner变量,并用new运算符实例化Scanner
    Scanner sc = new Scanner(System.in);
    System.out.println("----请输入第一个多项式\r\n输入方式为“系数,"
            + "指数”\r\n结束请输入0----");
    while(true)
    {
        String  str = sc.next();
        if( str.equals("0") )
        {
            System.out.println("----第一个多项式输入结束----");
            break;
        }
        String[] strArray = str.split(",");
        if( strArray.length < 2 )
        {
            System.out.println("----输入的数据格式错误----");
            break;
        }
        int coef = Integer.parseInt(strArray[0]);
        int expn = Integer.parseInt(strArray[1]);
        PolyData polyData = new PolyData(coef,expn);
        poly.addPol(poly.getPolyListOne(),polyData);
       
    }
    poly.display(poly.getPolyListOne());
    System.out.println("----请输入第二个多项式\r\n输入方式为“系数,"
            + "指数”\r\n结束请输入0----");
    while(true)
    {
        String  str = sc.next();
        if( str.equals("0") )
        {
            System.out.println("----第二个多项式输入结束----");
            break;
        }
        String[] strArray = str.split(",");
        if( strArray.length < 2 )
        {
            System.out.println("----输入的数据格式错误----");
            break;
        }
        int coef = Integer.parseInt(strArray[0]);
        int expn = Integer.parseInt(strArray[1]);
        PolyData polyData = new PolyData(coef,expn);
        poly.addPol(poly.getPolyListTwo(),polyData);
   
    }
    poly.display(poly.getPolyListTwo());
    poly.addPol();
    poly.display(poly.getPolyListResult());
   
   
}
}


  • 备案号:鲁ICP备15001146号
  • @1997-2018 潍坊米粒花网络技术有限公司版权所有