Nejmenší společný násobek, největší společný dělitel, Euklidův algoritmus
Tato úloha slouží k procvičení jednoduchého příkladu na hledání NSN a NSD. Můžeme jí rozdělit na dvě fáze, v první budou studenti pomocí metody hrubé síly hledat NSN, NSD. V druhé budou počítat NSD pomocí Euklidova algoritmu a NSN pomocí nalezeného vzorečku na internetu.
Jednotlivé fáze úlohy je možné řešit nezávisle na sobě (tudíž třeba jen jednu z nich). Autor ale nedoporučuje přistoupit pouze k druhé části bez předchozího vyřešení první.
Zadání je pro obě fáze stejné:
Vymyslete vlastní funkce pro výpočet největšího společného dělitele a nejmenšího společného násobku. Pro výpočet využijte
vlastních funkcí nejvetsiDelitel a nejmensiNasobek.
- Vstup:
77, 28 - Výstup:
Nejvetsi spolecny delitel cisel 77 a 28 je: 7, nejmensi spolecny nasobek je: 308
Dedukce - hledání hrubou silou
V první fázi úlohy by studenti neměli mít s ničím problémy. Na úloze díky její jednoduchosti pracují samostatně bez předchozí diskuse. Jediný problém může nastat v době, kdy ve snaze najít co nejlepší řešení bude vymýšlet složité postupy, které ho můžou zmást. Jednoduchou dedukcí dojdou k tomu, že v případě hledání NSN budou testovat větší číslo než je jedno z těch zadaných a zkoušet, jestli se jedná o dělitele v obou případech. Dané číslo poté vypíší. Obdobě to funguje i při hledání NSD, kdy naopak testujeme dělitelnost od jednoho ze zadaných čísel do 1 pro obě čísla.
Výsledný program 1_brute-force je velice primitivní. Za zajímavost stojí zmínit, že v ukázce všech jazyků je přidána řádka
popsaná jako „Kontrolni vraceni 0“. Toto je podstatné například u jazyka C++, kdy bez tohoto příkazu kompilátor ve
většině případů vrátí chybu, jelikož nebyly ošetřeny všechny možnosti. Obdobný problém může nastat i u dalších
jazyků. Než tuto skutečnost prozradíme, tak můžeme zahájit diskusi dle otázek v sekci Otázky do diskuse.
#include <iostream>
using namespace std;
// Deklarace a inicializace funkci
int nejvetsiDelitel(int i, int j); // Funkce pro nalezeni nejvetsiho spolecneho delitele
int nejmensiNasobek(int i, int j); // Funkce pro nalezeni nejmensiho spolecneho nasobku
int main() {
// Demonstrace
cout << "Nejvetsi spolecny delitel cisel 77 a 28 je: " << nejvetsiDelitel(77, 28) << ", nejmensi spolecny nasobek je: " << nejmensiNasobek(77, 28) << endl;
cout << "Nejvetsi spolecny delitel cisel 1517 a 2952 je: " << nejvetsiDelitel(1517, 2952) << ", nejmensi spolecny nasobek je: " << nejmensiNasobek(1517, 2952) << endl;
}
// Funkce pro nalezeni nejvetsiho spolecneho delitele
int nejvetsiDelitel(int i, int j) {
// Otestujeme nejprve cisla na nuly
if (i == 0 || j == 0) {
// Vratime nulu
return 0
}
// Cyklus na testovani delitele
for(int k = j; k >= 1; k--) {
// Pokud najdu cislo, ktere je delitelem
if(i % k == 0 && j % k == 0) {
// Vratim ho
return k;
}
}
// Kontrolni vraceni 0
return 0;
}
// Funkce pro nalezeni nejmensiho spolecneho nasobku
int nejmensiNasobek(int i, int j) {
// Cyklus na testovani nasobku
for(int k = i; k <= i*j; k++) {
// Pokud najdu cislo, ktere je nasobkem
if(k % i == 0 && k % j == 0) {
// Vratim ho
return k;
}
}
// Kontrolni vraceni 0
return 0;
}
// Demonstrace
console.log("Nejvetsi spolecny delitel cisel 77 a 28 je: " + nejvetsiDelitel(77, 28) + ", nejmensi spolecny nasobek je: " + nejmensiNasobek(77, 28));
console.log("Nejvetsi spolecny delitel cisel 1517 a 2952 je: " + nejvetsiDelitel(1517, 2952) + ", nejmensi spolecny nasobek je: " + nejmensiNasobek(1517, 2952));
// Funkce pro nalezeni nejvetsiho spolecneho delitele
function nejvetsiDelitel(i, j) {
// Otestujeme nejprve cisla na nuly
if (i == 0 || j == 0) {
// Vratime nulu
return 0
}
// Cyklus na testovani delitele
for(var k = j; k >= 1; k--) {
// Pokud najdu cislo, ktere je delitelem
if(i % k == 0 && j % k == 0) {
// Vratim ho
return k;
}
}
// Kontrolni vraceni 0
return 0;
}
// Funkce pro nalezeni nejmensiho spolecneho nasobku
function nejmensiNasobek(i, j) {
// Cyklus na testovani nasobku
for(var k = i; k <= i*j; k++) {
// Pokud najdu cislo, ktere je nasobkem
if(k % i == 0 && k % j == 0) {
// Vratim ho
return k;
}
}
// Kontrolni vraceni 0
return 0;
}
# Funkce pro nalezeni nejvetsiho spolecneho delitele
def nejvetsiDelitel(i, j):
# Otestujeme nejprve cisla na nuly
if i == 0 or j == 0:
# Vratime nulu
return 0
# Cyklus na testovani delitele
for k in range(i, 0, -1):
# Pokud najdu cislo, ktere je delitelem
if i % k == 0 and j % k == 0:
# Vratim ho
return k
# Kontrolni vraceni 0
return 0
# Funkce pro nalezeni nejmensiho spolecneho nasobku
def nejmensiNasobek(i, j):
# Cyklus na testovani nasobku
for k in range(i, i*j+1):
# Pokud najdu cislo, ktere je nasobkem
if k % i == 0 and k % j == 0:
# Vratim ho
return k
# Kontrolni vraceni 0
return 0
# Demonstrace
print("Nejvetsi spolecny delitel cisel 77 a 28 je:", nejvetsiDelitel(77, 28), ", nejmensi spolecny nasobek je:", nejmensiNasobek(77, 28))
print("Nejvetsi spolecny delitel cisel 77 a 28 je:", nejvetsiDelitel(1517, 2952), ", nejmensi spolecny nasobek je:", nejmensiNasobek(1517, 2952))
Je vhodné na toto navázat po vyřešení příkladů studenty promítnutím ukázkového příkladu a rozebrat jednotlivé části programu. Autor důrazně doporučuje provést demonstraci ve vícero jazycích, kdy odstraníme tento kontrolní return a sledujeme překladače kterých jazyků si s tím poradí.
Otázky do diskuse
- Má libovolná dvojice přirozených čísel vždy nejmenší společný násobek? A jak je to u největšího společného dělitele?
- Co bude výstupem programu po zadání čísel 13 a 23 (poznámka: jedná se o prvočísla)?
- Co musíme zadat za čísla, aby funkce u NSD nebo NSN vrátila číslo 0?
- Z jakého důvodu tedy máme u obou promítnutých funkcí „Kontrolni vraceni 0“?
- Proč zrovna jazyk C++ musí obsahovat tento řádek a například Python nebo JavaScript ne? (tip: Podívejte se do způsobu deklarace funkce v jednotlivých jazycích)
Možné problémy
- Studentovi ve striktním jazyku nefunguje program kvůli chybějícímu vrácení. – Postup řešení tohoto problému je popsán výše. Je možné taky studenty pobídnout ke zkopírování chyby do internetového vyhledávače a tak dojít k nalezení odpovědi.
Euklidův algoritmus
V druhé fázi si napíšeme efektivnější program na výpočet NSN a NSD. Úlohu si rozdělíme na dvě části. V první budeme počítat NSD pomocí Euklidova algoritmu.
K vysvětlení Euklidova algoritmu je vhodné využít pomocný slide s názvem eukliduv_algoritmus.png.
Důrazně je doporučeno promítnout pomocný slide, či provést rozbor na tabuli. Vysvětlení vlastními slovy: Mějme číslo A a B. Pro nalezení NSD budeme odečítat od čísla A číslo B, dokud nám nevznikne zbytek po dělení. Hodnotu čísla B uložíme do A a zbytek po dělení vložíme do B. Toto opakujeme do doby, než bude zbytek nulový. V případě, že je zbytek nulový, tak jsme našli největšího společného dělitele.
Dále dáme studentům volný prostor, aby na internetu našli způsob, jakým se dá efektivně vypočítat nejmenší společný násobek dvou čísel. Měli by
vyhledávat na internetu fráze typu „least common multiple algorithm“, případě podobné výrazy. Narazit by měli (např. zde:
https://stackoverflow.com/a/3154503) na vzoreček:
NSN(a,b)=(a*b)÷NSD(a,b). Toto se již jednoduše zapracuje do funkce. Výsledný program
2_eukliduv-algoritmus bychom měli studentům předvést a následně v případě potřeby vysvětlit.
#include <iostream>
using namespace std;
// Deklarace a inicializace funkci
int nejvetsiDelitel(int i, int j); // Funkce pro nalezeni nejvetsiho spolecneho delitele
int nejmensiNasobek(int i, int j); // Funkce pro nalezeni nejmensiho spolecneho nasobku
int main() {
// Demonstrace
cout << "Nejvetsi spolecny delitel cisel 77 a 28 je: " << nejvetsiDelitel(77, 28) << ", nejmensi spolecny nasobek je: " << nejmensiNasobek(77, 28) << endl;
cout << "Nejvetsi spolecny delitel cisel 1517 a 2952 je: " << nejvetsiDelitel(1517, 2952) << ", nejmensi spolecny nasobek je: " << nejmensiNasobek(1517, 2952) << endl;
}
// Funkce pro nalezeni nejvetsiho spolecneho delitele
int nejvetsiDelitel(int i, int j) {
// Otestujeme nejprve cisla na nuly
if (i == 0 || j == 0) {
// Vratime nulu
return 0
}
// Pokud najdu cislo, ktere je delitelem
if(i % j == 0) {
// Vratim ho
return j;
}
// Jinak
else {
// Zavolam funkci s prohozenymi parametry
return nejvetsiDelitel(j, i % j);
}
}
// Funkce pro nalezeni nejmensiho spolecneho nasobku
int nejmensiNasobek(int i, int j) {
// Vratime nasobek pomoci vzorecku
return (i * j) / (nejvetsiDelitel(i, j));
}
// Demonstrace
console.log("Nejvetsi delitel cisel 77 a 28 je: " + nejvetsiDelitel(77, 28) + ", nejmensi spolecny nasobek je: " + nejmensiNasobek(77, 28));
console.log("Nejvetsi delitel cisel 1517 a 2952 je: " + nejvetsiDelitel(1517, 2952) + ", nejmensi spolecny nasobek je: " + nejmensiNasobek(1517, 2952));
// Funkce pro nalezeni nejvetsiho spolecneho delitele
function nejvetsiDelitel(i, j) {
// Otestujeme nejprve cisla na nuly
if (i == 0 || j == 0) {
// Vratime nulu
return 0
}
// Pokud najdu cislo, ktere je delitelem
if(i % j == 0) {
// Vratim ho
return j;
}
// Jinak
else {
// Zavolam funkci s prohozenymi parametry
return nejvetsiDelitel(j, i % j);
}
}
// Funkce pro nalezeni nejmensiho spolecneho nasobku
function nejmensiNasobek(i, j) {
// Vratime nasobek pomoci nalezeneho vzorecku
return i * j / (nejvetsiDelitel(i, j));
}
# Funkce pro nalezeni nejvetsiho spolecneho delitele
def nejvetsiDelitel(i, j):
# Otestujeme nejprve cisla na nuly
if i == 0 or j == 0:
# Vratime nulu
return 0
# Pokud najdu cislo, ktere je delitelem
if(i % j == 0):
# Vratim ho
return j
# Jinak
else:
# Zavolam funkci s prohozenymi parametry
return nejvetsiDelitel(j, i % j)
# Funkce pro nalezeni nejmensiho spolecneho nasobku
def nejmensiNasobek(i, j):
# Vratime nasobek pomoci nalezeneho vzorecku
return int(i * j / (nejvetsiDelitel(i, j)))
# Demonstrace
print("Nejvetsi delitel cisel 77 a 28 je:", nejvetsiDelitel(77, 28), ", nejmensi spolecny nasobek je: ", nejmensiNasobek(77, 28))
print("Nejvetsi delitel cisel 1517 a 2952 je:", nejvetsiDelitel(1517, 2952), ", nejmensi spolecny nasobek je: ", nejmensiNasobek(1517, 2952))
Otázky do diskuse
- Co se stane s Euklidovým algoritmem, pokud je číslo B větší než A? Má toto nějaký vliv na funkčnost?
Možné problémy
- Neočekávají se žádné problémy.