ALGORYTMIKA (26.2)

Ad 1.
Kiedy szukaliście rozwiązania zadania porządkującego kilka liczb, dało się zauważyć, jak pomocna może być analiza graficzna. Fakt ten wykorzystano tworząc standard opisu popularnie określany jako schemat blokowy.
Algorytm przedstawiony w takiej postaci składa się z charakterystycznych klocków, tzw. skrzynek. By łatwiej się nauczyć posługiwać tym sposobem opisu, rozpoczniemy od bardzo prostego przykładu. Będzie to algorytm z zadania domowego, obliczający sumę liczb, a dla większego uproszczenia pominiemy specyfikację zadania.
Jako lista kroków prezentuje się następująco:

krok 0. Wpisz liczby a, b.
krok 1. Przypisz S := a + b.
krok 2. Pisz S. Zakończ.

Zwróć uwagę na instrukcję przypisania w kroku 1. Jest to podstawowa instrukcja występująca w językach programowania, której przykładem może być zapis:

i := i + 1
Pozornie wydaje się , że mamy do czynienia z wyrażeniem sprzecznym. Tymczasem znak przypisania := nie jest znakiem równości. Powyższy zapis jest prostym zabiegiem zwiększjącym skokowo wartość np. licznika w pętli.
Wróćmy do naszego programiku i spróbujmy przełożyć zapis tekstowy na graficzny.

Ćwiczenie 1. Korzystając z powyższego przykładu zbuduj jeszcze w zeszycie algorytm obliczający obwód wybranej figury geometrycznej (skorzystaj z przykładów z poprzedniej lekcji).

Takie proste algorytmy nie wykorzystują instrukcji waunkowych, które na schemacie blokowym realizuje skrzynka warunkowa. Inaczej się stanie, gdy podniesiemy nieco poziom trudności poprzednich przykładów.

Ćwiczenie 2. Przedstaw na schemacie blokowym algorytm obliczania sumy dla dowolnej liczby składników.

Ćwiczenie 3. Zmodernizuj algorytm z ćw. 1 tak, by sprawdzał, czy wprowadzane liczby są dodatnie.

Ad 2.
Z lekcji matematyki znany jest sposób obliczania NWD - największego wspólnego dzielnika. Około 2000 lat temu gracki uczony Euklides opracował metodę, która (jeśli jej nie znasz) może zaskoczyć cię genialną prostotą.
Dane: liczby a, b różne od 0.
Wynik: NWD największy wspólny dzielnik.

krok 0. Wpisz liczby a, b.
krok 1. Jeżeli liczby a i b są równe, przejdź do kroku 4.
krok 2. Jeżeli a>b, przypisz a:=a-b i wróć do kroku 1.
krok 3. Przypisz b:=b-a i wróć do kroku 1.
krok 4. Pisz a. Zakończ.

W opisie słownym znaczy to tyle, że dopóki obie liczby są różne, należy od większej odejmować mniejszą, a potem zastępować tą większą liczbę różnicą. W momencie zrównania liczb otrzymujemy NWD.
Jeśli nie brzmi to dostatecznie zrozumiale, to pomóc może tylko schemat blokowy :) Zauważ, że mamy w tym przypadku do czynienia z algorytmem złożonym, w którym pojawiają się skrzynki warunkowe.

Ćwiczenie 4. Przerysuj do zeszytu schemat algorytmu Euklidesa i podpisz go.

Ćwiczenie 5. Przedstaw w formie graficznej algorytm sortowania 2 i 3 liczb.

Ćwiczenie 6. Przedstaw na schemacie blokowym algorytm obliczania średniej dla dowolnej liczby elementów.

SPIS TREŚCI