Seminář PHP – Gymnázium Kolín

Úloha 10: Určení NSD a nsn (Eukleidův algoritmus)

Mírně pokročilý Eukleidův algoritmus cyklus while matematika MathML

Cíl úlohy

Vytvořte skript, který z formuláře přijme dvě přirozená čísla a a b a pomocí Eukleidova algoritmu nalezne jejich největšího společného dělitele NSD(a, b) a nejmenší společný násobek nsn(a, b).

Eukleidův algoritmus a nsn (MathML)

Eukleidův algoritmus je jeden z nejstarších známých matematických algoritmů (popsán kolem roku 300 př. n. l.). Využívá faktu, že pokud číslo dělí obě čísla a i b, musí dělit i jejich rozdíl:

NSD (a, b) = NSD (a - b, b) pro a > b

Jakmile známe NSD, nejmenší společný násobek nsn spočítáme ze vztahu:

nsn (a, b) = \frac{a \cdot b}{NSD (a, b)}

Úvahy a doporučený postup řešení

Odčítací verze Eukleidova algoritmu: Dokud $a != $b, od většího čísla odčítáme menší (if ($a > $b) $a = $a - $b; else $b = $b - $a;). Když se čísla vyrovnají, společná hodnota je NSD.
Rychlejší modulová verze: Pro velká čísla (např. 1 000 000 a 1) je odčítání pomalé. Rychlejší je nahradit odčítání zbytkem po dělení: $r = $a % $b; $a = $b; $b = $r; dokud $b != 0.
Zachování původních hodnot: Protože algoritmus v cyklu mění hodnoty $a a $b, uložte si na začátku jejich kopie do $a_orig a $b_orig, abyste mohli spočítat nsn a vypsat zadání.

Doplňující otázky k zamyšlení a náměty na rozšíření

1. Kdy nazýváme dvě čísla nesoudělná? Jaký je jejich NSD a nsn?
2. Kde v praktické matematice využíváme NSD (např. krácení zlomků do základního tvaru) a nsn (např. převod zlomků na společného jmenovatele při sčítání)?
3. Jak byste spočítali NSD pro 3 čísla a, b, c? (Nápověda: $NSD (a, b, c) = NSD (NSD (a, b), c)$ ).
4. O kolik kroků je rychlejší modulová varianta s % než odčítací varianta pro čísla $a = 1000000$ a $b = 3$ ?

Vyzkoušejte funkční řešení: Otevřít vzorovou úlohu nsd.php