Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 11. 11. 2015 18:44 — Editoval honzik360 (11. 11. 2015 18:47)
Bezoutova věta / Rozšířený Eukleides
Ahoj,
algoritmizuji hledání řešení diofantických rovnic.
Př.
Mám rovnici 
Nyní to dělám tak, že hrubou silou najdu první nejnižší řešení pro x a nejvyšší řešení pro y.
Zde 
Dále podle Nejmenšího Společného Násobku (NSN) dohledám zbytek řešení, protože vím, že NSN těchto dvou čísel = 130 je rozdíl vzdáleností, čili 130 přičtu k x a zároveň odečtu od y.
To vše je vpořádku. ( řešení je 6 )
Problém je v tom, že nalezení prvního kladného řešení (Jak pro x tak pro y) Abych mohl algoritmus odstartovat, je výpočetně pro velká čísla př. ( 
) ohromně náročný.
Vím, že se to dá nějak vypočítat Rozšířeným Eukleidovým algoritmem + převodem na Bezoutovu rovnost. Ale nedaří se mi vymyslet jak.
Děkuji za jakoukoli radu.
Offline
#2 11. 11. 2015 19:31 — Editoval Eratosthenes (11. 11. 2015 19:31)
- Eratosthenes
- Příspěvky: 3111
- Reputace: 140
Re: Bezoutova věta / Rozšířený Eukleides
ahoj ↑ honzik360:,
No, nevím, co je na tom tak náročného, mně první řešení vyplivl kompl za necelou vteřinu...
x = 8 613 009;
y = 1 826 206 483;
Budoucnost patří aluminiu.
Offline
#3 11. 11. 2015 19:32
Re: Bezoutova věta / Rozšířený Eukleides
↑ Eratosthenes:
Jakým způsobem si to řešení spočítal?
Díky
Offline
#4 11. 11. 2015 19:35 — Editoval Eratosthenes (11. 11. 2015 19:36)
- Eratosthenes
- Příspěvky: 3111
- Reputace: 140
Re: Bezoutova věta / Rozšířený Eukleides
↑ honzik360:
Je to v Pascalu (přesněji řečeno v Delphi), jednotlivá řešení to při tomto zadání plive cca po vteřinách.
var m2, hranice, PocetReseni:Int64;
m1,k,q :Extended;
rozdil :double;
Reseni :boolean;
begin
PocetReseni:=0;
k:=-2791951/56676911;
q:= 103527789403704572/56676911;
hranice:=103527789403704572 div 2791951;
m2:=0;
Repeat
m2:=m2+1;
m1:=q+k*m2;
if abs(round(m1)-m1)<1e-15
then begin
PocetReseni:=PocetReseni+1;
StringGrid1.Cells[2,PocetReseni-1]:=IntToStr(m2);
StringGrid1.Cells[1,PocetReseni-1]:=FloatToStr(k*m2+q);
Application.ProcessMessages;
end;
Until m2>hranice;
end;
Budoucnost patří aluminiu.
Offline
#5 11. 11. 2015 19:41
Re: Bezoutova věta / Rozšířený Eukleides
↑ Eratosthenes:
Díky, kouknu na to! :-) Vypadá to dobře.
Offline