Laboratorium 2: Algorytm Euklidesa

1 Pętle

Tematem przewodnim zajęć jest zapoznanie się z dwiema podstawowymi konstrukcjami do tworzenia pętli:

  1. Polecenia while

    while ( warunek )
    {
    ...
    }
    
  2. Polecenie dowhile

    do
    {
    ...
    } while ( warunek );
    

W miejscu gdzie pojawiają się trzy kropeczki wstawiamy polecenie/polecenia, które będą wykonywane w pętli tak długo, jak długo warunek jest prawdziwy.

Polecenie while (oraz dowhile) istotnie różnią się od polecenia if. Na pierwszy rzut oka różnica nie jest specjalnie wielka:

if (m > n)
{
    m = m - n;
}

while (m > n)
{
    m = m - n;
}


ale istota pierwszego przykładu (if) jest taka: sprawdź czy $m$ jest większe od $n$ i jeżeli tak jest wykonaj operację odejmowania ($m = m - n$) zapisując wynik w $m$.

W drugim przypadku (while) tak długo jak $m$ jest większe od $n$ wykonuj operację odejmowania ($m = m - n$).

W pierwszym przypadku będzie jedno sprawdzenie i (gdy wynik będzie pozytywny) jedno wykonanie odejmowania.

W przypadku drugim będzie cykl: sprawdzenie warunku — ewentualne wykonanie odejmowania; zawsze po wykonanym odejmowaniu sprawdzany będzie ponownie warunek. Gdy warunek nie będzie spełniony — przechodzimy do wykonywania kolejnego polecenia.

Algorytm Euklidesa

Wszystkie zmienne są typu int!

Zadania do wykonania

  1. Zapoznać się z różnymi wariantami algorytmu Euklidesa zaprogramowanymi w Blockly:

  2. Napisać program realizujący algorytm Euklidesa (preferowana jest wersja „z resztą”. Algorytm powinien być zaprogramowany na co najmniej dwa sposoby: z wykorzystanie instrukcji while i dowhile. Ewentualnym, trzecim sposobem może być użycie pętli for.

Wersja „z resztą”

Dane są dwie dodatnie liczby całkowite $m$ i $n$. Należy znaleźć ich największy wspólny dzielnik, tj. największą dodatnią liczbę całkowitą, która dzieli bez reszty zarówno $m$ jak i $n$.

  • [E1] : [Znajdowanie reszty] Podziel $m$ przez $n$ i niech $r$ oznacza resztę z tego dzielenia.

  • [E2] : [Czy wyszło zero?] Jeśli $r=0$, zakończ algorytm; odpowiedzią jest $n$.

  • [E3] : [Upraszczanie] Wykonaj $m \leftarrow n$, $n \leftarrow r$ i wróć do kroku E1.

Wersja „z odejmowaniem"

Dane są dwie dodatnie liczby całkowite $m$ i $n$. Należy znaleźć ich największy wspólny dzielnik, tj. największą dodatnią liczbę całkowitą, która dzieli bez reszty zarówno $m$ jak i $n$.

  1. Jeżeli $m$ jest równe $n$ — koniec, największym wspólnym dzielnikiem jest $n$.

  2. Jeżeli $m> n$ przyjmij $m\leftarrow m-n$; w przeciwnym razie przyjmij $n\leftarrow n-m$

  3. Przejdź do kroku 1.

lub raczej, wersję zmodyfikowaną:

  1. Tak długo jak $m \ne n$ powtarzaj:

    1. Jeżeli $m> n$ przyjmij $m\leftarrow m-n$; w przeciwnym razie przyjmij $n\leftarrow n-m$
  2. Największym wspólnym dzielnikiem jest $n$.

Na czym polega problem?

Porównajmy uproszczone schematy blokowe

  • Algorytmu E

    flowchart LR AA((Start)) ---> A[Instrukcja1] ---> B{warunek} --->|Nie| C[Instukcja2] ---> A B --->|Tak| AAA((Stop))
  • polecenia while

    flowchart LR AA((Start)) ---> A{warunek} --->|Tak| B[Instrukcja] --- A A --->|Nie| AAA((Stop))
  • petli do

    flowchart LR AA((Start)) ---> A[Instrukcja] ---> B{Warunek} --->|Tak| A B -->|Nie| AAA((Stop))

while zaczyna się od warunku, jak jest spełniony — wykonujemy jakieś polecenia i powtarzamy

do — najpierw wykonujemy jakieś polecenie, później sprawdzamy warunek i jeżeli jest spełniony — powtarzamy.

Algorytm E ma instrukcje przed warunkiem (jak do) i po warunku (jak while). Natomiast jego istotą jest aby operacje były wykonywane w kolejności:

instrukcje 1 $\rightarrow$ warunek $\rightarrow$ instrukcje 2 $\rightarrow$ instrukcje 1 $\rightarrow$ warunek $\rightarrow$ instrukcje 2 $\rightarrow$ …$\rightarrow$ warunek

W każdym przypadku korzystając ze standardowych poleceń pętlowych trzeba te „nadmiarowe" instrukcje uwzględnić.

Poprzedni
Następny