Diviser des polynômes en Java?

Question

J'essaie de trouver le GCD d'un polynôme en créant une classe de division pour les polynômes. Je comprends comment ajouter, réduire, multiplier et créer des polynômes, mais je ne sais pas comment les diviser (avec du code). Quelqu'un pourrait m'aider?

Voici mon code à ce jour:

public class Polynomial2 { 
private int[] coef; // coefficients 
private int deg;  // degree of polynomial (0 for the zero polynomial) 

// a * x^b 
public Polynomial2(int a, int b) { 
    coef = new int[b+1]; 
    coef[b] = a; 
    deg = degree(); 
} 

// return the degree of this polynomial (0 for the zero polynomial) 
public int degree() { 
    int d = 0; 
    for (int i = 0; i < coef.length; i++) 
     if (coef[i] != 0) d = i; 
    return d; 
} 

// return c = a + b 
public Polynomial2 plus(Polynomial2 b) { 
    Polynomial2 a = this; 
    Polynomial2 c = new Polynomial2(0, Math.max(a.deg, b.deg)); 
    for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i]; 
    for (int i = 0; i <= b.deg; i++) c.coef[i] += b.coef[i]; 
    c.deg = c.degree(); 
    return c; 
} 

// return (a - b) 
public Polynomial2 minus(Polynomial2 b) { 
    Polynomial2 a = this; 
    Polynomial2 c = new Polynomial2(0, Math.max(a.deg, b.deg)); 
    for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i]; 
    for (int i = 0; i <= b.deg; i++) c.coef[i] -= b.coef[i]; 
    c.deg = c.degree(); 
    return c; 
} 

// return (a * b) 
public Polynomial2 times(Polynomial2 b) { 
    Polynomial2 a = this; 
    Polynomial2 c = new Polynomial2(0, a.deg + b.deg); 
    for (int i = 0; i <= a.deg; i++) 
     for (int j = 0; j <= b.deg; j++) 
      c.coef[i+j] += (a.coef[i] * b.coef[j]); 
    c.deg = c.degree(); 
    return c; 
} 

// return a(b(x)) - compute using Horner's method 
public Polynomial2 compose(Polynomial2 b) { 
    Polynomial2 a = this; 
    Polynomial2 c = new Polynomial2(0, 0); 
    for (int i = a.deg; i >= 0; i--) { 
     Polynomial2 term = new Polynomial2(a.coef[i], 0); 
     c = term.plus(b.times(c)); 
    } 
    return c; 
} 


// do a and b represent the same polynomial? 
public boolean eq(Polynomial2 b) { 
    Polynomial2 a = this; 
    if (a.deg != b.deg) return false; 
    for (int i = a.deg; i >= 0; i--) 
     if (a.coef[i] != b.coef[i]) return false; 
    return true; 
} 


// use Horner's method to compute and return the polynomial evaluated at x 
public int evaluate(int x) { 
    int p = 0; 
    for (int i = deg; i >= 0; i--) 
     p = coef[i] + (x * p); 
    return p; 
} 

// differentiate this polynomial and return it 
public Polynomial2 differentiate() { 
    if (deg == 0) return new Polynomial2(0, 0); 
    Polynomial2 deriv = new Polynomial2(0, deg - 1); 
    deriv.deg = deg - 1; 
    for (int i = 0; i < deg; i++) 
     deriv.coef[i] = (i + 1) * coef[i + 1]; 
    return deriv; 
} 

// convert to string representation 
public String toString() { 
    if (deg == 0) return "" + coef[0]; 
    if (deg == 1) return coef[1] + "x + " + coef[0]; 
    String s = coef[deg] + "x^" + deg; 
    for (int i = deg-1; i >= 0; i--) { 
     if  (coef[i] == 0) continue; 
     else if (coef[i] > 0) s = s + " + " + (coef[i]); 
     else if (coef[i] < 0) s = s + " - " + (-coef[i]); 
     if  (i == 1) s = s + "x"; 
     else if (i > 1) s = s + "x^" + i; 
    } 
    return s; 
} 

//method for division 
public Polynomial2 divides(Polynomial2 b) { 

} 

// test client 
public static void main(String[] args) { 

    /*first polynomial*/ 
    Polynomial2 p1 = new Polynomial2(1, 13); 
    Polynomial2 p2 = new Polynomial2(-12, 12); 
    Polynomial2 p3 = new Polynomial2(55, 11); 
    Polynomial2 p4 = new Polynomial2(-148, 10); 
    Polynomial2 p5 = new Polynomial2(337, 9); 
    Polynomial2 p6 = new Polynomial2(-460, 8); 
    Polynomial2 p7 = new Polynomial2(55, 7); 
    Polynomial2 p8 = new Polynomial2(-148, 6); 
    Polynomial2 p9 = new Polynomial2(336, 5); 
    Polynomial2 p10 = new Polynomial2(-448, 4); 

    Polynomial2 p = p1.plus(p2).plus(p3).plus(p4).plus(p5).plus(p6).plus(p7). 
      plus(p8).plus(p9).plus(p10); 
    //x^13 - 12x^12 - 55x^11 - 148x^10 + 337x^9 + 460x^8 + 55x^7 - 148x^5 + 336x^5 - 448x^4 

    /*second polynomial*/ 
    Polynomial2 q1 = new Polynomial2(1, 20); 
    Polynomial2 q2 = new Polynomial2(-12, 19); 
    Polynomial2 q3 = new Polynomial2(55, 18); 
    Polynomial2 q4 = new Polynomial2(-148, 17); 
    Polynomial2 q5 = new Polynomial2(335, 16); 
    Polynomial2 q6 = new Polynomial2(-436, 15); 
    Polynomial2 q7 = new Polynomial2(-55, 14); 
    Polynomial2 q8 = new Polynomial2(148, 13); 
    Polynomial2 q9 = new Polynomial2(-336, 12); 
    Polynomial2 q10 = new Polynomial2(448, 11); 
    Polynomial2 q11 = new Polynomial2(1, 7); 
    Polynomial2 q12 = new Polynomial2(-12, 6); 
    Polynomial2 q13 = new Polynomial2(55, 5); 
    Polynomial2 q14 = new Polynomial2(-148, 4); 
    Polynomial2 q15 = new Polynomial2(336, 3); 
    Polynomial2 q16 = new Polynomial2(-448, 2); 
    Polynomial2 q = q1.plus(q2).plus(q3).plus(q4).plus(q5).plus(q6).plus(q7). 
      plus(q8).plus(q9).plus(q10).plus(q11).plus(q12).plus(q13). 
      plus(q14).plus(q15).plus(q16); 
    //x^20 - 12x^19 + 55x^18 - 148x^17 + 335x^16 - 436x^15 - 55x^14 + 148x^13 - 336x^12 
    //448x^11 + x^7 - 12x^6 + 55x^5 - 148x^4 + 336x^3 - 448x^2; 

    System.out.println("p(x) =  " + p); 
    System.out.println("q(x) =  " + q); 
    } 

} 

Answer 1

Vous devez diviser le coefficient correspondant à degré dans les deux polynômes comme:

public Polynomial2 divides(Polynomial2 b) { 
    Polynomial2 a = this; 
    if ((b.deg == 0) && (b.coef[0] == 0)) 
     throw new RuntimeException("Divide by zero polynomial"); //Zero polynomial is the one having coeff and degree both zero. 

    if (a.deg < b.deg) return new Polynomial2(0,0); 

    int coefficient = a.coef[a.deg]/(b.coef[b.deg]); 
    int exponent = a.deg - b.deg; 
    Polynomial2 c = new Polynomial2(coefficient, exponent); 
    return c.plus((a.minus(b.times(c)).divides(b))); 
} 

Ce code doit faire ce que vous voulez. Vous devrez peut-être faire de petites améliorations en fonction de vos besoins. Le code ci-dessus est la version légèrement modifiée de this.

Answer 2

Voici quelques pseudo-code pour elle, basée sur la Princeton archives

// return (a/b) 
    public Polynomial2 divides(Polynomial2 b) { 
     Polynomial2 a = this; 
     if ((b.deg == 0) && (b.coef[0] == 0)) 
      throw new RuntimeException("Divide by zero polynomial"); 

     if (a.deg < b.deg) return ZERO; 

     int coefficient = a.coef[a.deg].divides(b.coef[b.deg]); 
     int exponent = a.deg - b.deg; 
     Polynomial2 c = new Polynomial2(coefficient, exponent); 
     return c.plus((a.minus(b.times(c)).divides(b))); 
    }