Schemat blokowy to graficzny zapis algorytmu rozwiązania zadania, przedstawiający opis i kolejność wykonywania czynności realizujących dany algorytm. W schemacie blokowym poszczególne operacje przedstawione są za pomocą odpowiednio połączonych skrzynek (klocków, bloków). Połączenia określają kolejność i sposób wykonywania operacji realizujących dany algorytm.

Poprawność całkowita- Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniają warunek WK.

Stos jest to dynamiczna struktura danych, w której usuwany jest element najpóźniej dodany

stad nazwa LIFO - last in, first out. Z punktu widzenia implementacji jest to tablica S [1..n] z

dodatkowym parametrem top [S] wskazującym na szczyt stosu.

Kolejka jest to dynamiczna struktura danych, w której usuwany jest element najwcześniej

dodany stad nazwa FIFO - first in, first out. Z punktu widzenia implementacji jest to tablica

K [1..n] z dwoma parametrami head [K] - wskazującym początek kolejki oraz tail [K] wskazującym

na koniec kolejki. W kolejce elementy zdejmowane sa oczywiście od początku kolejki

Drzewo algorytmu -Graficzna reprezentacja algorytmu przyjmująca postać drzewa. W takiej reprezentacji, wierzchołki pośrednie drzewa zawierają wykonywane w algorytmie operacje, a w wierzchołkach końcowych znajdują się wszystkie możliwe wyniki wykonania algorytmu.

Odwrotna notacja polska, inaczej RPN (z ang. Reverse Polish Notation) to sposób zapisu wyrażeń arytmetycznych beznawiasowo. Czyli, np. mając wyrażenie (zapis infiksowy): (2+1)*3-4*(7+4) to w RPN: 2 1 + 3 * 4 7 4 + * -

Zadanie:

B1:k=0 u=455v=712

Jedna z liczb jest nieparzysta, więc nie powtarzamy, przechodzimy do punktu B2

 B2:u jest nieparzyste stąd t=-712 przechodzimy do B4

 B4:t jest parzyste więc przechodzimy do B3

 B3: t=-712/2=-356

 B4;t jest nadal parzyste więc przechodzimy do B3

 B3:t=-356/2=-178

 B4;t jest nadal parzyste więc przechodzimy do B3

 B3:t=-178/2=-89

B4: t jest nieparzyste, a więc w końcu przechodzimy do B5

 B5:t jest ujemne, więc v=89

B6:t=u-v=455-89=366 i wracamy z powrotem do B3:

B3: t=366/2=183

B4:t jest nieparzyste więc

B5:u=183 (ponieważ t>0)

B6:t=u-v=183-89=94 wracamy do B3

B3: t=94/2=47

B4:t jest nieparzyste

B5:u=47 (ponieważ t>0)

B6:t=47-89=-42 wracamy do B3

 

B3:t=-42/2=-21

B4: t jest nieparzyste

B5: v=21 ( t jest <0)

B6: t=47-21=26 wracamy do B3

B3: t=26/2=13

B4:t jest nieparzyste

B5:u=13 (t>o)

 

B6:t=13-21=-8 wracamy do B3

B3: t=-8/2=-4

B4: wracamy do B3

B3: t=-4/2=-2

B4: wracamy do B3

B3: t=-2/2=-1

B4: t jest nieparzyste

B5: v=1 (t<0)

B6: t=13-1=12 wracamy do B3

B3: t=12/2=6

B4: wracamy do B3

B3: t=6/2=3

B4: t jest nieparzyste

B5: u=3 (t>0)

B6: t=3-1=2 wracamy do B3

 

B3:t=2/2=1 (uff w końcu)

B4:t jest nieparzyste

B5: u=1 (t>0)

B6:t=1-1=0

 Odp. Najwiekszym wspólnym dzielnikiem liczb 455 i 712 jest 1 ;).

Co się zgadza ponieważ:

455=5*7*13

712=2*2*89

Czyli liczby są względnie pierwszymi.

---