Faktorisering av polynomer

Det er god trening å prate matematikk. Her er det fritt fram for alle. Obs: Ikke spør om hjelp til oppgaver i dette underforumet.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gjest

Hei, dette er muligens matematikk over videregående-nivå, men satser på at det er matte-entusiaster her som kan dette...

Jeg lurer på hvilken fremgangsmåte man bruker når man skal faktorisere et polynom. Jeg prøver å løse følgende programmeringsoppgave:

http://online-judge.uva.es/p/v4/463.html

Ta f.eks følgende polynom og dets faktorisering:

493x^4 + 172x^3 - 860x^2 - 151x + 58 = (17x^2 + 3x - 29)*(29x^2 + 5x - 2)

Hvilken metode er best for å bruke for å finne faktorer av andre grad og høyere? Det er greit nok å finne de av første grad, jeg sliter litt med andre grad...
dischler
Guru
Guru
Innlegg: 242
Registrert: 01/03-2004 10:11

Å faktorisere polynomer er ekvivalent med å finne nullpunktene, altså p(x) = 0 (dette lærte i hvertfall vi på videregående). Når polynomene har grad 5 eller større har ikke dette problemet en generell løsning. Men for grad større eller mindre enn 4 finnes formler du kan bruke, f.eks er formelen for andregradsligninger velkjent.

I ditt problem behøver du imidlertid ikke tenke på disse formlene. Det er gitt i oppgaveteksten at polynomene som programmet får som input skal faktoriseres i heltallige polynomer. Dette forenkler mye.

Det finnes sikkert mange måter å skrive dette programmet på, men jeg vil bare skissere en ide som er det første jeg tenkte på (som innebærer at det sikkert finnes bedre måter!):

- faktoriser først i to andregradspolynomer. Dette gjøres ved å bruke at:

(tx[sup]2[/sup]+ux+v)(qx[sup]2[/sup]+rx+s)=ax[sup]4[/sup]+bx[sup]3[/sup]+cx[sup]2[/sup]+dx+e (definisjon på faktorisering)

Ut fra dette får vi:

i) a=tq
ii) b=tr+uq
iii) c=ts+ur+vq
iv) d=uv+rs
v) e=vs

Siden alt skal være heltall er det her begrensede muligheter. Du kan f.eks la programmet kjøre gjennom alle muligheter for t og q som oppfyller i). For hver av disse gå gjennom alle muligheter som oppfyller v). Sett t,q,v og s så inn i iii) og gå så gjennom alle muligheter for u og r. Sjekk deretter om ii) og iv) er oppfyllt for aktuelle verder på q,r,s,r,u og v. Er de det så har du klart faktoriseringen.

Deretter faktoriserer du de to andregradspolynomene på tilsvarende måte.
stubbscroll
Maskinmester
Maskinmester
Innlegg: 14
Registrert: 21/10-2003 14:10
Sted: Trondheim
Kontakt:

Hei, takk for at du tok deg bryet med å skrive et så utfyllende svar!

Jeg var inne på noe av det du skrev, i starten av prosedyren min gikk jeg igjennom alle mulige verdier av t, q, u og r. Problemet var at jeg ikke delte polynomet opp slik du gjorde (definisjonen av faktorisering), men jeg prøvde istedet å dividere fjerdegradspolynomet med forskjellige andregradspolynomer som bestod av alle kombinasjoner av t,q,v,s,u,r (hadde ikke noe godt system for å finne u og r) og endre opp med et ubrukelig tregt (men utrolig nok, korrekt) program.

Jeg har tenkt litt mer, hovedsakelig på fasen der man leter etter u og r, og kommet frem til følgende:

- Gå igjennom alle muligheter for t og q.
- For hver av disse, gå igjennom alle muligheter for v og s
(så langt er det overkommelig, det er bare et par tusen kombinasjoner på dette stadiet selv når koeffisientene a og e er 2 milliarder.)
- For hver godtatt kombinasjon av t,q,v,s, utfør et "3-ary search" (variant av binary search) etter korrekt r, der forskjellige verdier av r settes inn i ii), iii) og iv) på jakt etter en u-verdi som oppfyller alle disse (dette ble kanskje litt tungvint forklart, men denne fasen skal iallefall kjøre raskt...)
dischler
Guru
Guru
Innlegg: 242
Registrert: 01/03-2004 10:11

Kan ikke se at oppgaveteksten sier noe om størrelsen på heltallene. Framgangsmåten jeg skissert ville vel bli O(n^3) der n er størrselsen på heltallene. Dette burde vel være overkommelig. Men jeg er enig med deg i at det kan virke som det burde være mulig å forbedre kjøretiden ved å bruke bedre søkealgoritmer.
Gjest

Det at oppgaveteksten ikke nevner noe om størrelsene er som regel et dårlig tegn. Har fått bekreftet via assert() at koeffisientene er større enn 10 millioner, og da er man pent nødt til å ha en bra algoritme. Algoritmen min over (3-ary search) fungerte dårlig, så jeg må gå i tenkeboksen igjen...
stubbscroll
Maskinmester
Maskinmester
Innlegg: 14
Registrert: 21/10-2003 14:10
Sted: Trondheim
Kontakt:

Hmmm... er flink å glemme å logge inn :?
Svar