Tag: <span>Algorytm Euklidesa</span>

Algorytm Euklidesa z odejmowaniem - schemat blokowy

CC BY oblicz.com.pl

Spróbujmy napisać program, który policzy NWD (największy wspólny dzielnik) za pomocą algorytmu Euklidesa z odejmowaniem.

Aby to zrobić, zapoznajmy się z schematem działania. Dla przykładu policzymy NWD dla 16 i 56. Nasze zadanie będzie polegało na odejmowaniu od liczby większej liczbę mniejszą, tak długo, aż otrzymamy dokładnie te same wartości obu liczb.

  1. krok: niech a=16 i b=56;
  2. krok: 56 jest większe od 16, to b=b-a=56-16=40, bez zmian a=16;
  3. krok: 40 jest większe od 16, to b=b-a=40-16=24, bez zmian a=16,
  4. krok: 24 jest większe od 16, to b=b-a=24-16=8, bez zmian a=16,
  5. krok: 16 jest większe od 8, to a=a-b=16-8=8, bez zmian b=8,
  6. krok: a=b, czyli NWD(16,56)=a=b=8

Poniższe kroki możemy zapisać w postaci schematu blokowego:

Powyższy algorytm jest algorytmem iteracyjnym.

Czytaj dalej"Algorytm Euklidesa z odejmowaniem - schemat blokowy"

NWD

Największy wspólny dzielnik (w skrócie NWD) Czym jest największy wspólny dzielnik? Każdy zbiór liczb naturalnych ma zbiór wspólnych dzielników. "W najgorszym" przypadku taki zbiór wspólnych dzielników (liczb, przez które one obie dzielą się bez reszty) składa się z jednego elementu: ponieważ każda liczba naturalna jest podzielna przez . Przyjrzyjmy się parze liczb, którą otrzymałem przez losowanie w pseudolosowym kalkulatorze: Oczywiście, że możemy wyznaczyć wszystkie dzielniki dla tej pary, ale chyba nie będzie to najłatwiejszy przykład. Zastąpmy to czymś prostszym, np. : Wymieńmy wszystkie dzielniki obu liczb: dla liczby mamy zbiór dzielników (liczb przez które   dzieli się bez reszty): dla liczby …