hola de nuevo,
La técnica utilizada es:
Tenemos 2 polinomios de grado n-1
P(x) = P0 + P1x + P2x(elevado a 2) +……+Pn-1x(elevado a n-1)
Q(x) = Q0 + Q1x + Q2x(elevado a 2) +……+Qn-1x(elevado a n-1)
Hay que dividir cada polinomio en 2 polinomios de grado n/2.
Consideramos Pi la parte izquierda del polinomio P, Pd la parte derecha del polinomio P.
Pi(x) = P0 + P1x + P2x(elevado a 2) +…….+P(n/2)-1x(elevado a (n/2) -1)
Pd(x) = Pn/2 + P((n/2)+1)x + P2x(elevado a 2) +…….+P(n/2)-1x(elevado a (n/2) -1)
Ejemplo: 1 + 2x +3x(al cuadrado) + 4x(al cubo)
La parte izquierda sería 1+2x y la derecha el resto.
Como hemos hecho esa división antes el polinomio P quedaría de la siguiente manera:
P(x) = Pi(x) + Pd(x) x(elevado a n/2)
Nota: Como ves solo a la parte derecha hay que multiplicarla por x elevado a n/2.
Con el polinomio Q hay que hacer lo mismo que con el polinomio P:
Q(x) = Qi(x) + Qd(x) x(elevado a n/2)
P(x) Q(x) = Pi Qi + (Pi Qd + PdQi) x (elevado a n/2) + Pd Qd x(elevado a n) (n sale como resultado de sumar n/2 + n/2).
Hay que buscar una aproximación para reducir el número de multiplicaciones porque sino la complejidad será de n al cuadrado.
Ri(x) = Pi(x) Qi(x)
Rd(x) = Pd(x) Qd(x)
Rh(x) = (Pi(x) + Pd(x)) (Qi(x) + Qd(x))
P(x) Q(x) = Ri(x) + (Rh(x) – Ri(x) – Rd(x)) x (elevado a n/2) + Rdx (elevado a n)
Aunque es más grande, el número de operaciones se ha reducido a 3.
Si Pi = 5x +3 y Pd = 6x + 2
(5x + 3) + (6x + 2) = 11x + 5
Ejemplo:
P(x) = -1 + 2x + x (elevado a 2) + 3x (elevado a 3) n=4 por lo que el grado es n-1=3
Q(x) = 2 + x – x (elevado a 2) + 2x (elevado a 3)
Dividir los polinomios:
P(x) = (-1 + 2x) + (1 + 3x) x (elevado a 2)
Pi Pd
Q(x) = (2 + x) + (-1 + 2x) x (elevado a 2)
Pi Pd
Ri(x) = (-1 + 2x) (2 + x) = -2 + 3x + 2x (elevado a 2)
Rd(x) = (1 + 3x) (-1 + 2x) = -1 –x + 6x (elevado a 2)
Rh(x) = (-1 + 2x + 1 + 3x) (-1 + 2x + 2 + x) = 5x + 15x (elevado a 2)
Combinar soluciones parciales siguiendo la fórmula:
P(x) Q(x) = -2 + 3x + 2x (elevado a 2) + (5x + 5x (elevado a 2) + 2 – 3x – 2x (elevado a 2) + 1 + x – 6x (elevado a 2)) x(elevado a 2) + (1 – x + 6x(elevado a 2)) x (elevado a 4)
Lo primero que hago es comprobar que el grado del polinomio es múltiplo de 2.
Después lleno los vectores correspondientes para almacenar los polinomios.
En el método Multiplicar es el que utiliza la técnica de divide y Vencerás, en el cual se van dividiendo los problemas hasta llegar al caso base, que es cuando el grado del polinomio es 1, que entonces es como multiplicar dos escalares.
El método Combinar, es es que combina las soluciones obtenidas en el método multiplicar, para devolver una solución al problema.
Es que llevo tanto tiempo mirando el código que ya no encuentro ningún error. Por eso, estoy pidiendo ayuda.
Gracias, por preocuparte.
