11093

bezpośrednie następstwo - wykonaj instrukcję A, potem instrukcję B, potem instrukcję C, itd.

wybór warunkowy - jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj instrukcję B.

iteracja ograniczona - wykonaj instrukcję A dokładnie N razy. iteracja warunkowa „dopóki" - dopóki warunek Q jest spełniony wykonuj instrukcję A.

Iteracja warunkowa „aż do" - wykonuj instrukcję A dopóki warunek Q jest spełniony.

2) Algorytmy rekurencyjne( definicja rekurencji, schemat Homera, algorytm Euklidesa, szereg Fibonacciego, wieże Hanoi).

Rekurencja jest zatem sposobem programowania, w którym stosuje się procedury wywołujące same siebie. Ilość tych wywołań nie ma znaczenia, fakt wywołania jest podstawą do określenia algorytmu jako rekurencyjnego Schemat Homera to sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń. Jest to również algorytm dzielenia wielomianuW(x) przez dwumian x - c.

Schemat Homera pozwala na wyznaczenie ilorazu 0(x) z dzielenia wielomianu W(x) = aj<" + 3„.iX"'' + ... + a₂x² + apr + ao przez dwumian x - c.

Algorytm Euklidesa jest algorytmem rekurencyjnym, chociaż w bardzo prosty sposób można go przekształcić do formy iteracyjnej. Mając do policzenia NWD(a, b) sprawdzamy, czy b = 0. Jeśli tak jest to NWD(a, b) = a. W przeciwnym wypadku wywołujemy rekurencyjnie algorytm dla liczb b i reszty z dzielenia a przez b.

W matematyce , liczbach Fibonacciego liczby w następujących sekwencji inteaer:

0,1,2,3,5,8,13,21,34,55,89,144... (Sekwencja A000045 w OEIS )

Z definicji, w pierwszych dwóch liczb Fibonacciego to 0 i 1, a każdy kolejny numer jest sumą dwóch poprzednich. Niektóre źródła pominąć początkowe 0, zamiast początku sekwencji z dwoma ls.

Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyineao lub iteracyjnego.

*    Oznaczmy kolejne słupki literami A, B i C.

*    Niech n będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C posługując się słupkiem B jako buforem.

Rozwiązanie rekurencyjne:

Algorytm rekurencyjny składa się z następujących kroków:

1.    przenieś (rekurencyjnie) n-1 krążków ze słupka A na słupek B posługując się słupkiem C,

2.    przenieś jeden krążek ze słupka A na słupek C,

3.    przenieś (rekurencyjnie) n-1 krążków ze słupka B na słupek C posługując się słupkiem A

LUB

przez X-»Y oznaczmy czynność przenoszenia krążka z położenia X do położenia Y, w takim razie zadanie wykonane na poprzednim slajdzie można zapisać następująco: