Algorytm Euklidesa

  1. Jeśli nie potrafisz wyznaczyć największego wspólnego dzielnika dwóch liczb x i y (jest to największa spośród liczb, które dzielą bez reszty zarówno x, jak i y), to nie martw się: arkusz kalkulacyjny Excel również nie potrafi zrobić tego sam z siebie. Możemy jednak odpowiednio poinstruować go jak to zrobić przedstawiając mu odpowiedni przepis postępowania zwany algorytmem Euklidesa (matematyk grecki żyjący w latach 365-300 p.n.e.). Jest to najstarszy (więc może najprostszy) znany algorytm, czyli sformalizowany zbiór reguł postępowania. Wyznaczanie największego wspólnego dzielnika przydaje się czasem np. przy skracaniu ułamków.

  2. Algorytm Euklidesa zapiszemy, wykorzystując pojęcie zmiennej. Jest to obiekt zawierający wartość liczbową, którą można zmieniać (tak, jak komórka w programie Excel). Do sformułowania algorytmu Euklidesa potrzebne nam będą dwie zmienne, które nazwiemy a i b. Oto algorytm:

        niech nową wartością a będzie x
        niech nową wartością b będzie y
        dopóki wartość a jest różna od wartości b, dopóty wykonuj, co następuje
           jeśli a > b, to niech nową wartością a będzie a - b
           w przeciwnym przypadku niech nową wartością b będzie b - a
        
    Ostateczny wynik (czyli największy wspólny dzielnik liczb x i y zawarty będzie w zmiennej a (lub b, bo na końcu ich wartości mają być przecież równe. A to ten sam algorytm w postaci schematu blokowego (!= znaczy tu różne od):


  3. Nauczymy teraz program Excel wyznaczania największego wspólnego dzielnika dwóch liczb. Trzeba to jednak zrobić w taki sposób, aby Excel zrozumiał, o co nam chodzi. Komórki A1 i B1 zawierać będą wartości zmiennych x i y odpowiednio. Algorytm Euklidesa działa tylko dla liczb naturalnych, więc musimy zabezpieczyć się przed wprowadzeniem nieprawidłowych danych początkowych. Zaznacz komórki A1:B1 i wybierz polecenie Sprawdzanie poprawności z menu Dane:



    ustaw opcję "Pełna liczba", "większa lub równa" od "1" (to jest definicja liczby naturalnej:



    wpisz komunikat powitalny:



    i ostrzeżenie o błędzie:



  4. Poszczególne wiersze arkusza Excela będą przechowywać wartości zmiennych a i b przed wykonaniem kolejnych powtórzeń pętli w algorytmie Euklidesa. Wiersz numer 1 odpowiada więc wartościom początkowym tych zmiennych (A1 = a, A1 = b). W wierszu 2 wpiszemy teraz formuły obliczające wartości tych zmiennych po wykonaniu pierwszego powtórzenia pętli. W przykładzie poniżej znajdziesz przykładową formułę obliczającą wartość zmiennej a (komórka A2) przy użyciu funkcji standardowej JEŻELI (zauważ, że jeśli b jest mniejsze lub równe a, to do komórki A2 przenosimy wartość zmiennej a z komórki A1):



  5. Wpisz sam do komórki B2 podobną formułę obliczającą wartość zmiennej b (wskazówka: tym razem użyj funkcji JEŻELI z warunkiem b < a).

  6. Nadaj początkowe wartości zmiennym a i b. W przykładzie poniżej a jest większe od b, więc nową wartością a staje się a - b, zaś wartość b pozostała bez zmian:



  7. Aby wykonać kolejne powtórzenia pętli skopiujmy formuły z komórek A2:B2 do komórek poniżej (zaznacz te komórki i przeciągnij uchwyt autowypełnienia w dół tak, jak na rysunku poniżej):



  8. Jeśli tylko przeciągnąłeś uchwyt odpowiednio daleko w dół, to liczby w obu kolumnach powinny stać się równe. Zawarta w nich wartość liczbowa jest wynikiem algorytmu Euklidesa, czyli największym wspólnym dzielnikiem liczb z komórek A1 i B1:



(c) 2001 by Marian Rusek