Jak vymyslet vzorec?
Ahoj, prosím o radu. Mám dvě periody jedna je dlouhá 25znaků a druhá perioda je dlouhá 17znaků. Po kolika znacích se sesynchronizují pokud první periodě zbývá do začátku nové periody 17znaků a druhé periodě do začátku nové periody zbývá 8 znaků? Umím to jen vypočítat, když začínají naráz to si spočtu nejmenší společný násobek u offsetu vůbec netuším :(. Dokážu si to i namalovat, ale na velký čísla to nemám šanci vypočítat :-(. Díky moc za radu Jirka
Jiří R.
10. 11. 2016 10:21
5 odpovědí
Jirko, protože neuvádíš, o jaké úrovni matematiky mluvíme, nebudu používat konečné okruhy, ale jenom selský rozum.
Sestavím si rovnice podle zadání a upravím je postupně do hezčí podoby, kde bude řešení vidět od pohledu.
17 + 25p = 8 + 17q / +8 25 + 25p = 16 + 17q 25(p + 1) = 17 + 17q - 1 25(p + 1) = 17(q + 1) - 1
Protože perioda 17 je o 8 prvků kratší a 25 - 1 = 8 * 3, musí být koeficient na pravé straně 3 = q + 1.
Pak je jasné, že na levé straně platí p + 1 = 2.
p = 1, q = 2 je tedy řešením.
Kontrola:
první perioda je 17 + 1 * 25 = 42
druhá perioda je 8 + 2 * 17 = 42
Pokud bych chtěl místo takhle jednoduchého příkladu získat obecné řešení, musím to udělat jinak.
Pro periody P a Q (P > Q) se zbývajícími prvky K a L sestavím rovnici na konečném okruhu modulo P.
Řešením je potom (K - L) * Q^-1 (mod P), to spočítáme pomocí rozšířeného Euklidova algoritmu
Kontrola:
q = (17 - 8) * 17^-1 (mod 25) = 9 * 3 = 2
Děkuji moc, budu to používat na velký čísla tak se to pokusím řešit pomocí Euklidova algoritmu.
Ahoj nějak nechápu ten Euklidův algoritmus :( v tý kontrole máš 9 * 3 = 2? Jinak modulo nemam na kalkulačce tak sem se to snažil napsat v c ale nechce mě to vzít tvar vzorce q=(K-L)*Q^-1%P to modulo má být u té -1 v mocnině nebo na celou rovnici požít modulo? Díky za rady :))
Modulus platí na celou rovnici, když to rozepíšu:
q = (17 - 8) * 17^-1 (mod 25)
q = 9 * 3 (mod 25)
q = 2 (mod 25)
Jestli to chceš naprogramovat v C, budeš si to muset všechno napsat ručně.
V příloze je kompletní výpočet, tohle musíš převést do C.
Navíc to bude fungovat jen pro případy, kdy jsou P a Q nesoudělné.
Já tam tyhle podmínky mám kontrolované implicitně díky euklidově algoritmu.
Pokud jsou soudělné, musíš zkontrolovat, jestli řešení neexistuje nebo existuje na zkráceném okruhu a pak dopočítat původní řešení.
Na závěr tě asi nepotěším, počkej s tím, až za sebou budeš mít základy algebry.
Diofantické rovnice nejsou jednoduché a potřebuješ na ně cit a trochu pokročilejší matematiku.
Díky moc, stejně to nějak nechápu :D, ale díky za snahu implementuji to cyklama, jen to nebude tak efektivní bohužel.