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.

2 Algorytm Euklidesa

Zadania do wykonania

  1. Zapoznać się z różnymi wariantami algorytmu Euklidesa zaprogramowanyi w Blockly:
  2. Napisać program realizujący algorytm Euklidesa. Algorytm powinien być zaprogramowany na dwa sposoby: z wykorzystanie instrukcji whiledowhile.

2.1 Wersja „z resztą”

Dane są dwie dodatnie liczby całkowite mn. 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 n, n r i wróć do kroku E1.

2.2 Wersja „z odejmowaniem”

Dane są dwie dodatnie liczby całkowite mn. 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 mn; w przeciwnym razie przyjmij n nm
  3. Przejdź do kroku 1.

lub raczej, wersję zmodyfikowaną:

  1. Tak długo jak m = n powtarzaj:
    1. Jeżeli m > n przyjmij m m n; w przeciwnym razie przyjmij n n m
  2. Największym wspólnym dzielnikiem jest n.

2.3 Zadania z listy

Jest również dostępna lista zadań.

3 Wersja PDF tego dokumentu…

pod adresem.

Wersja: 8 z drobnymi modyfikacjami! data ostatniej modyfikacji 2016-02-22 20:53:24 +0100