Největší společný dělitel, nejmenší společný násobek (2019)

Přehled úkolů cvičení (konkrétní návod k řešení je uveden níže, body řešte postupně):
A) Napište dva algoritmy, pro hledání největšího společného dělitele dvou celých čísel.
První algoritmus bude realizovat algoritmus hledání největšího společného dělitele hrubou silou (funkce fsdM).
Druhý algoritmus bude realizovat algoritmus hledání největšího společného dělitele pomocí Euklidova algoritmu (funkce fsdE).

B) Napište algoritmus, který najde všechny společné dělitele dvou čísel (funkce fsd).

C) Napište algoritmus, který rozloží celé číslo na součin prvočísel (funkce Rozklad).

D) Napište algoritmus, který vypočte největšího společného dělitele dvou celých čísel, má-li k dispozici jejich rozklady na prvočísla (funkce fsdR).

E) Napište algoritmus, který vypočte nejmenší společný násobek dvou celých čísel, má-li k dispozici jejich rozklady na prvočísla (funkce nsn).

0) Při realizaci funkcí neprovádějte testy vstupních hodnot, pouze si promyslete, jaké by měly být. Funkce tedy volejte s parametry, pro které má daný algoritmus řešení. Pro případ, že chybový stav může nastat při řešení algoritmem, vraťte hodnotu -1 a ve funkci main vytiskněte text “při řešení ve funkci xxx nastala chyba“.

Pro řešení vytvořte nový projekt. Hlavní program s funkcí main dejte do souboru mainsd.c. Algoritmy tvořte v souboru sd.c a k němu vytvořte příslušný hlavičkový soubor sd.h s prototypy funkcí.

Ve funkci main nadefinujte dvě celá čísla val1 a val2 (unsigned) a inicializujte je. Tyto hodnoty používejte jako parametry funkcí při testování algoritmů.
Doporučené dvojice hodnot pro testování: (8;4) (6;8) (48;12) (16;8) (362880;362880) (362880;3628800)(362880;48360) (127008;48360)

Ad A) hledání největšího společného dělitele dvou čísel

Největší společný dělitel je například vhodný při krácení zlomků. Příklady vstupních dvojic a jejich řešení: (8;4) -> 4, (8;6) -> 2.

1) Napište funkci fsdM a v ní realizujte algoritmus pro hledání největšího společného dělitele ze dvou celých čísel hrubou silou. Funkce bude mít dva parametry – čísla, jejichž největší společný dělitel se hledá. Hodnota nalezeného největšího společného dělitele bude vrácena pomocí návratové hodnoty funkce.
unsigned fsdM(unsigned aVal1, unsigned aVal2);
Hledání proveďte tak, že budete postupně generovat kandidáty na společného jmenovatele (čísla postupně od menšího ze vstupní dvojice do hodnoty 1). Pro každého kandidáta zkuste, zda jsou jím obě čísla aVal1 a aVal2 dělitelná bezezbytku (pomocí operátoru % (tj. funkce modulo, nebo-li zbytek po celočíselném dělení)). První vyhovující kandidát je hledaným řešením.
2) Napište funkci fsdE a v ní realizujte algoritmus pro hledání největšího společného dělitele ze dvou celých čísel pomocí Eukleidova algoritmu. Funkce bude mít dva parametry – čísla, jejichž největší společný dělitel se hledá. Hodnota nalezeného největšího společného dělitele bude vrácena pomocí návratové hodnoty funkce.
unsigned fsdE(unsigned aVal1, unsigned aVal2);
Algoritmus naleznete například na wikipeii pod heslem Eukleidův algoritmus/Euclidean algorithm.

3) Ve funkci main zavolejte postupně obě funkce a oba výsledky vytiskněte od začátku řádku. Jednu hodnotu na řádek.

Ad B) Nalezněte všechny společné dělitele dvou čísel

1) Napište funkci fsd, která vytiskne na konzolu všechny celočíselné dělitele, kterými jsou dvě celá čísla dělitelná bezezbytku. (Tisk proveďte od největšího, včetně jedničky).
Funkce fsd má dva vstupní parametry typu unsigned. Pomocí návratové hodnoty funkce předá nalezený počet společných dělitelů (včetně jedničky).
unsigned fsd(unsigned aVal1, unsigned aVal2);
Nalezené hodnoty dělitelů pouze vytiskněte na konzolu (z funkce je nevrací). Formát tisku budou celá čísla oddělená středníkem a mezerou (viz příklad níže), bez odřádkování. Po tisku odřádkuje.
Příklad řešení pro vstupní dvojice :(8;4) -> 4; 2; 1 , (48;24) -> 24; 12; 8; 6; 4; 3; 2; 1. Počty nalezených dělitelů 3 a 8.
2) Ve funkci main zavolejte funkci fsd a vytiskněte na konzolu vrácený počet společných dělitelů.

Ad C) Rozklad čísla na součin prvočísel

1) Napište funkci Rozklad, která rozloží celé číslo na součin prvočísel. Funkce bude mít tři parametry: číslo určené ke zpracování aVal, pole aVysl pro uložení prvočísel (činitelů součinu), výsledkem jejichž násobení bude číslo aVal (budou-li se činitelé opakovat, uložte je všechny), a délku aDelka pole aVysl. Návratovou hodnotou funkce bude počet činitelů.
int Rozklad(unsigned aVal, size_t aDelka, unsigned aVysl[]);
Navrhněte vhodný algoritmus pro rozklad čísla na součin prvočísel. Pro urychlení výpočtů můžete použít tabulku prvočísel. Prvočísla do 10000 (jak je uvádí wikipedia) naleznete zde.
Jednotlivé činitele ukládejte podle velikosti do pole aVysl. V případě, že nebude možné umístit celý rozklad do předaného pole, vraťte hodnotu -1. V případě, že se vyčerpají všechna prvočísla a nebude ukončen rozklad, vraťte hodnotu -2.

2) Ve funkci main nadefinujte dvě pole Roz1 a Roz2. Délka polí bude N. Pomocí příkazu #define definujte N na hodnotu 40.
Funkci Rozklad zavolejte pro proměnné val1 a val2. Výsledky uložte do polí Roz1, Roz2. Počty nalezených činitelů (návratové hodnoty funkce Rozklad) uložte do proměnných Pocet1 a Pocet2.

Ad D) Největší společný dělitel dvou celých čísel určený z jejich rozkladu na prvočísla

1) Napište funkci fsdR, která implementuje algoritmus, pomocí kterého z rozkladů dvou čísel na prvočísla určí jejich největší společný dělitel. Funkce bude mít čtyři parametry: dvě pole rozkladů na prvočísla aRoz1 a aRoz2 a příslušné počty činitelů v polích aPocet1 a aPocet2. Funkce vrátí pomocí návratové hodnoty největší společný dělitel. Během algoritmu vypíše na konzolu činitele, ze kterých se největší společný dělitel vypočte. Jednotlivé hodnoty budou odděleny středníkem a mezerou.
unsigned fsdR(size_t aPocet1, size_t aPocet2, unsigned aRoz1[], unsigned aRoz2[]);
Algoritmus: největší společný dělitel je násobkem těch činitelů, jejichž hodnoty jsou společné oběma polím (průnik hodnot). Pokud se hodnota vyskytuje vícekrát, použije se tolikrát, kolik je menší z počtů této hodnoty v obou polích.
2) Ve funkci main zavolejte funkci fsdR s hodnotami získanými v předchozím bodě C). Na konzolu vytiskněte znak '=' a hodnotu, kterou vrátila funkce fsdR.

Ad E) Nejmenší společný násobek dvou celých čísel určený z jejich rozkladu na prvočísla

1) Napište funkci nsn, která implementuje algoritmus, pomocí kterého z rozkladů dvou čísel na prvočísla určí jejich nejmenší společný násobek. Funkce bude mít čtyři parametry: dvě pole rozkladů na prvočísla aRoz1 a aRoz2 a příslušné počty činitelů v polích aPocet1 a aPocet2. Funkce vrátí pomocí návratové hodnoty nejmenší společný násobek. Během algoritmu vypište na konzolu činitele, ze kterých se nejmenší společný násobek vypočte. Jednotlivé hodnoty budou odděleny středníkem a mezerou.
unsigned fnsn(size_t aPocet1, size_t aPocet2, unsigned aRoz1[], unsigned aRoz2[]);
Algoritmus: nejmenší společný násobek je násobkem všech hodnot činitelů obou rozkladů (sjednocení hodnot), s tím, že činitelé, jejichž hodnoty jsou společné oběma rozkladům, se použijí pouze jednou.
2) Ve funkci main zavolejte funkci nsn s hodnotami získanými v předchozím bodě C). Na konzolu vytiskněte znak '=' a hodnotu, kterou vrátila funkce nsn.

Poslední změna 2019-02-22