Implementacja algorytmu Euklidesa w języku C++

R12rgKYS7tEXF

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

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

Film dostępny pod adresem /preview/resource/R12rgKYS7tEXF

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

Podsumowanie

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:

1. Odejmiemy $14$ od $35$ $\left(35>14\right)$ – powstaje nowa para liczb: $21$ i $14$.

2. Odejmiemy $14$ od $21$ – otrzymujemy następną parę: $7$ i $14$.

3. 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:

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 $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