Lecture/자료구조/2011/알고리즘 3.1

Polynomial.java

abstract public class Polynomial {
 
    public abstract Polynomial zeroP();
    public abstract boolean isZeroP();
    public abstract int maxExp();
    public abstract int coef(int e);
    public abstract Polynomial addTerm(int c, int e);
    public abstract Polynomial delTerm(int e);
    public abstract void print();
 
    /**
     * p3 = p1 + p2
     * p3 = p1.polyAdd(p2);
     */
    public Polynomial polyAdd(Polynomial p2) {
        Polynomial p3 = zeroP();
        while(!this.isZeroP() && !p2.isZeroP()) {
            if (this.maxExp() < p2.maxExp()) {
                p3.addTerm(p2.coef(p2.maxExp()), p2.maxExp());
                p2.delTerm(p2.maxExp());
            } else if (this.maxExp() == p2.maxExp()) {
                int sum = this.coef(this.maxExp()) + p2.coef(p2.maxExp());
                if (sum != 0)
                    p3.addTerm(sum, this.maxExp());
            } else {
                p3.addTerm(this.coef(this.maxExp()), this.maxExp());
                this.delTerm(this.maxExp());
            }
        }
 
        if (!this.isZeroP()) {
            while(!this.isZeroP()) {
                p3.addTerm(this.coef(this.maxExp()), this.maxExp());
                this.delTerm(this.maxExp());
            }
        } else if (!p2.isZeroP()) {
            while(!p2.isZeroP()) {
                p3.addTerm(p2.coef(p2.maxExp()), p2.maxExp());
                p2.delTerm(p2.maxExp());
            }
        }
 
        return p3;
    }
 
    /**
     * p3 = p1 + p2
     * p3 = Polynomial.polyAdd(p1, p2);
     */ 
    public static Polynomial polyAdd(Polynomial p1, Polynomial p2) {
        Polynomial p3 = p1.zeroP();
        while(!p1.isZeroP() && !p2.isZeroP()) {
            if (p1.maxExp() < p2.maxExp()) {
                p3.addTerm(p2.coef(p2.maxExp()), p2.maxExp());
                p2.delTerm(p2.maxExp());
            } else if (p1.maxExp() == p2.maxExp()) {
                int sum = p1.coef(p1.maxExp()) + p2.coef(p2.maxExp());
                if (sum != 0)
                    p3.addTerm(sum, p1.maxExp());
            } else {
                p3.addTerm(p1.coef(p1.maxExp()), p1.maxExp());
                 p1.delTerm(p1.maxExp());
            }
        }
 
        if (!p1.isZeroP()) {
            while(!p1.isZeroP()) {
                p3.addTerm(p1.coef(p1.maxExp()), p1.maxExp());
                p1.delTerm(p1.maxExp());
            }
        } else if (!p2.isZeroP()) {
            while(!p2.isZeroP()) {
                p3.addTerm(p2.coef(p2.maxExp()), p2.maxExp());
                p2.delTerm(p2.maxExp());
            }
        }
 
        return p3;
    }
}

MyPolynomial.java

public class MyPolynomial extends Polynomial {
    private static final int MAX_SIZE = 100;
    private int[] mExps = new int[MAX_SIZE];
    private int[] mCoeffs = new int[MAX_SIZE];
    private int size = 0;
 
    @Override
    public Polynomial zeroP() {
        return new MyPolynomial();
    }
 
    @Override
    public boolean isZeroP() {
        return size == 0;
    }
 
    /**
     * 처음 제시한 코드에 지수와 계수를 바꾸어 표시했습니다.
     * 이를 정정합니다.
     * @param c 계수
     * @param e 지수
     */
    @Override
    public Polynomial addTerm(int c, int e) {
        mExps[size] = e;
        mCoeffs[size] = c;
        size++;
        return this;
    }
 
    @Override
    public Polynomial delTerm(int e) {
        // TODO Auto-generated method stub
        return null;		
    }
 
    @Override
    public int coef(int e) {
        // TODO Auto-generated method stub
        return 0;
    }
 
    @Override
    public int maxExp() {
        // TODO Auto-generated method stub
        return 0;
    }
 
    @Override
    public void print() {
        for(int i = 0; i < size; i++) {
            if (i != 0)
                System.out.print(" + ");
            System.out.print(mCoeffs[i] + "x^" + mExps[i]);
        }
        System.out.println();
    }
 
}

PolyTest.java

public class PolyTest {
    public static void main(String[] args) {
        Polynomial p1 = new MyPolynomial();
        Polynomial p2 = new MyPolynomial();
 
        // p1 = 2x^4 + 10x^3 + x^2 + 6
        p1.addTerm(2, 4).addTerm(10, 3).addTerm(1, 2).addTerm(6, 0);
 
        // p2 = 4x^7 + 2x^6 + 3x^5 + 10x^4 + x^2
        p2.addTerm(4, 7).addTerm(2, 6).addTerm(3, 5);
        p2.addTerm(10, 4).addTerm(1, 2);
 
        Polynomial p3 = p1.polyAdd(p2);
        // Polynomial p3 = Polynomial.polyAdd(p1, p2);
 
        p3.print();
    }
}