Compunerea polinoamelor

[•lucrue]

Salut,

Am un examen la sfarsitul lui august si pregatindu-ma am intalnit problema compunerii a 2 polinoame.

Apreciez, daca este cineva sa ma ajute. Am gasit cum se face inmultirea a 2 polinoame si cum se afla valoarea unui polinom intr-un punct, dar nu reusesc sa fac rezolvarea pentru compunerea polinoamelor.

As aprecia o idee de algoritm pentru compunerea polinoamelor.

[•pauldb]

Fie P1(x) si P2(x) polinoamele avand grad n si, respectiv, m. Sa presupunem ca vrei sa calculezi P1(P2(x)). Atunci algoritmul ar arata asa:

• calculezi c[ i ][ j ] combinari de i luate cate j pentru orice i <= n si orice j <= i. Poti face asta folosind recurenta de la triunghiul lui Pascal.
• pentru fiecare termen al lui P1, a_ixⁱ:
  
  • calculezi coeficientii lui P2(x)ⁱ folosind de m ori binomul lui Newton (si implicit combinarile calculate anterior)
  • inmultesti coeficientii cu a_i
  • aduni coeficientii la coeficientii polinomului rezultat

[•lucrue]

Mersi frumos de idee.
Insa m-am impotmolit in iteratii 

Recurenta de la triunghiul lui Pascal o fac asa:

Pt i:=1 la n-1 ex
 pt. j:=1 la i ex
  c[i+1,j]:=c[i,j-1]+c[i,j]

dar nu stiu cum sa folosesc de m ori binomul lui Newton...

De fapt cate repetitii trebuie sa folosesc?

[•pauldb]

Recurenta pentru combinari pare corecta, daca ai grija sa umpli si celulele din matrice pentru i = 0, 1 si j = 0.

Intr-adevar, cred ca nu e suficient sa folosesti binomul lui Newton doar de m ori. Ideea mea e ca atunci cand vrei sa calculezi P(x)ⁱ e sa consideri polinomul ca format din 2 termeni (primul si o suma formata din restul termenilor de la 2 la m) si sa aplici formula de la binom. Ce iese pare foarte urat, dar s-ar putea sa mearga implementat frumos ca o functie recursiva care primeste doi parametri x si y si are ca scop calculul polinomului format din termenii de la x la m din P ridicat la puterea y. S-ar putea sa existe si o formula mai simpla care sa nu necesite Binomul lui Newton, dar eu nu o gasesc.