Implementacja algorytmu Euklidesa w języku C++

Problem 1

Zaimplementuj algorytm Euklidesa, wykorzystując:

  • odejmowanie,

  • resztę z dzielenia.

Specyfikacja problemu:

Dane:

  • a, b – liczby naturalne dodatnie dla których program będzie wyznaczał NWD

Wynik:

Na standardowym wyjściu program wypisuje NWD liczb a i  b.

R12aTlxfA6o4u
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Polecenie 1

Porównaj swoje rozwiązanie z filmem.

R12rgKYS7tEXF
Film nawiązujący do treści materiału algorytmu Euklidesa - zastosowanie różnych pętli.
Rg3ht0LLD4lF81

Przycisk do pobrania pliku TXT z kodami źródłowymi.

Plik TXT o rozmiarze 611.00 B w języku polskim
Polecenie 2

Przeanalizuj prezentację. Porównaj ze sobą działanie dwóch wersji algorytmu dla różnych par liczb.

R6WV2qBYxATV21
Wymyśl pytanie na kartkówkę związane z tematem abstraktu.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Podsumowanie

Problem 2

Wyznaczymy NWDNWDNWD liczb 3514 przy użyciu dwóch wariantów algorytmu Euklidesa.

Algorytm Euklidesa z odejmowaniem

W tej wersji algorytmu interesuje nas różnica liczb, których NWD chcemy znaleźć. Odejmujemy zawsze mniejszą liczbę od większej.

Szukając NWD liczb 3514, wykonamy następujące czynności:

  1. Odejmiemy 14 od 35 35>14 – powstaje nowa para liczb: 2114.

  2. Odejmiemy 14 od 21 – otrzymujemy następną parę: 714.

  3. Odejmiemy 7 od 14 – pozostaje nam para liczb 77.

Cykl odejmowania i tworzenia nowych par kończymy w chwili, gdy otrzymamy dwie identyczne liczby; każda z nich to NWD. W przypadku 3514 jest to 7.

Implementacja w języku C++

Linia 1. int a znak równości 35 średnik. Linia 2. int b znak równości 14 średnik. Linia 4. while otwórz nawias okrągły a wykrzyknik znak równości b zamknij nawias okrągły. Linia 5. otwórz nawias klamrowy. Linia 6. if otwórz nawias okrągły a zamknij nawias ostrokątny b zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy. Linia 8. a minus znak równości b średnik. Linia 9. zamknij nawias klamrowy. Linia 10. else. Linia 11. otwórz nawias klamrowy. Linia 12. b minus znak równości a średnik. Linia 13. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy.

Algorytm Euklidesa z resztą z dzielenia

Wykonujemy następujące działania:

  1. Obliczamy resztę z dzielenia 35 przez 14. Wynosi ona 7.

  2. Obliczamy resztę z dzielenia 14 przez 7; wynik operacji to 0. Pozostały nam liczby 70.

Ponieważ jedna z liczb ma wartość zero, druga z nich (czyli 7) jest największym wspólnym dzielnikiem.

Implementacja algorytmu w języku C++

Linia 1. int a znak równości 35 średnik. Linia 2. int b znak równości 14 średnik. Linia 4. while otwórz nawias okrągły b wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 5. otwórz nawias klamrowy. Linia 6. int pom znak równości a procent b średnik. Linia 7. a znak równości b średnik. Linia 8. b znak równości pom średnik. Linia 9. zamknij nawias klamrowy.

Słownik

NWD
NWD

akronim pojęcia „największy wspólny dzielnik”