Przeczytaj

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

Polecenie 1

Porównaj swoje rozwiązanie z filmem.

R12rgKYS7tEXF

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Podsumowanie

Problem 2

Wyznaczymy NWDNWDNWD liczb 35 i 14 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 35 i 14, wykonamy następujące czynności:

Odejmiemy $14$ od $35$ $(35 > 14)$ – powstaje nowa para liczb: $21$ i $14$ .
Odejmiemy $14$ od $21$ – otrzymujemy następną parę: $7$ i $14$ .
Odejmiemy $7$ od $14$ – pozostaje nam para liczb $7$ i $7$ .

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

Implementacja w języku C++

int a = 35;
int b = 14;

while (a != b)
{
	if (a > b)
    {
    	a -= b;
    }
    else
    {
  		b -= a;
    }

}

Algorytm Euklidesa z resztą z dzielenia

Wykonujemy następujące działania:

Obliczamy resztę z dzielenia $35$ przez $14$ . Wynosi ona $7$ .
Obliczamy resztę z dzielenia 14 przez 7; wynik operacji to $0$ . Pozostały nam liczby $7$ i $0$ .

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

Implementacja algorytmu w języku C++

int a = 35;
int b = 14;

while (b != 0)
{
	int pom = a % b;
    a = b;
    b = pom;
}

Słownik

NWD

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

Wprowadzenie

Audiobook