Matematické Fórum

Fester182lanarik

Dobry den riesim nasledovny problem, mam napisat program to je jedno v akom jazyku na eulerov alg. ale pomocou polynomov.
resp. ktory bude realizovat Euklidov algoritmus pre vypocet najvacsiejo spolocneho delitela polynomov r(x) = NSD(p(x),q(x)) v poli realnych cisel.

Code:

program eulerovalg;
var x,y:integer;
begin
 readln(x,y);
 repeat
       if x>y then x:= x-y;
       if y>x then y:= y-x;
 until x=y;
writeln('NSD= ',x);
readln;
end.

ja som si napisal program ale len na vypocet pomocou cisel. respektivne odcitavanie.

chcel by som vas teda poprosit o radu ako by mal vyzerat dany algoritmus ?

dakujem.

Kondr · 14. 11. 2009 21:14

Polynom je třeba mít uložen jako pole koeficientů (od konstantního k vyšším mocninám) a v nějaké proměnné si pamatovat jeho stupeň. Aby nám koeficienty nerostly moc rychle, budeme polynomy uchovávat v normovaném tvaru, tedy s koeficientem u nejvyšší mocniny rovným 1. Místo x:=x-y proběhne forcyklus, který odečte koeficienty u odpovídajících si* mocnin, navíc detekuje, jaký je poslední koeficient je nenulový (podle čehož uloží nový stupeň polynomu) a následně druhý forcyklus, který výsledný polynom normuje. Je kolem toho ještě pár technických detailů, ale ty jistě vyřešíš.

---
*odečítáme nejvyšší mocninu od nejvyšší, druhou nejvyšší od druhé nejvyšší ... kdyby byl x=t^3+2 a y=t+1, budou pole x a y obsahovat
x:2,0,0,1
y:1,1,
odečtením dostaneme v x 2,0,-1,0

Matematické Fórum

#1 04. 11. 2009 14:05 — Editoval Fester182lanarik (05. 11. 2009 15:32)

Euklidov algoritmus (polynomy)

Code:

#2 14. 11. 2009 21:14

Re: Euklidov algoritmus (polynomy)

Zápatí