Diskuze – Lekce 9 - Největší společný dělitel (Euklidův algoritmus)
ZpětUpozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.
Mircosoft:13.7.2011 13:08
Tak jsem si to nakonec musel pořádně nastudovat 
http://en.wikipedia.org/…id_algorithm
Pravdu máme oba, postupným odečítáním menšího čísla vyjde to samé
číslo jako při jednom modu. Jediný rozdíl je v rychlosti a použitých
instrukcích.
David Hartinger:17.12.2011 11:25
Dobrý den,
algoritmus by neměl být problém použít pro více čísel. Např. pro
čísla a, b, c, d nejprve vypočítáte v1 = gcd(a,b); v2 = gcd(v1, c); v3 =
gcd(v2, d); Poslední výsledek v3 je ten konečný Stačí si jen naimplementovat
nějaký cyklus nad polem, který vezme vždy gcd z posledního výsledku a
dalšího prvku v poli.
Něco jako:
puvodni = pole[0];
for (i = 1; i < pole.length; i++)
{
puvodni = gcd(puvodni, pole[i]);
}Pro výpočet nejmenšího společného násobku lze použít opět funkci GCD (největšího společného dělitele):
int lcm(int a, int b) {
if (a == 0 || b == 0)
return 0;
return (a * b) / gcd(a, b);
}
Zobrazeno 10 zpráv z 11.