algorytmy. Ćwiczenia scan.pdf

A l g o r y t m y • w i c z e n i a

Rozdzia 4.

Algorytmy iteracyjne. Przetwarzanie danych w ptli

programowej

Algorytm iteracyjny

Rysowanie gwiazdek

Co umoliwia iteracja?

102

Uwagi kocowe

110

wiczenia do samodzielnego wykonania

111

Rozdzia 5.

Algorytmy rekurencyjne

115

Algorytm rekurencyjny

115

Funkcja silnia

116

Obliczanie potgi liczby rzeczywistej

127

Uwagi kocowe

134

wiczenia do samodzielnego wykonania

137

Rozdzia 6.

Schemat Hornera. Obliczanie wartoci wielomianu

139

Schemat Hornera

139

Uwagi kocowe

165

wiczenia do samodzielnego wykonania

167

Rozdzia 7.

Pozycyjne systemy liczbowe

169

System liczbowy

169

Obliczanie wartoci liczby zapisanej

w dowolnym systemie pozycyjnym

174

Przedstawianie liczb w dowolnym

pozycyjnym systemie liczbowym

194

Uwagi kocowe

214

wiczenia do samodzielnego wykonania

216

Rozdzia 8.

Algorytmy sortowania danych

217

Sortowanie zbioru danych

217

Metody sortowania zbioru danych

220

Uwagi kocowe

265

wiczenia do samodzielnego wykonania

266

Algorytmy rekurencyjne

Algorytm rekurencyjny

Rekurencja , zwana równie rekursj , jest technik programowania,

w której stosowany jest podprogram (funkcja lub procedura) wywo

ujcy sam siebie albo wywoujcy inn procedur, która wywoa

podprogram pierwotny. W tym drugim przypadku mówimy o rekur

sji podwójnej lub skronej . Kolejne wywoania trwaj, a do osi

gnicia warunku zakoczenia rekurencji. Jest nim oczekiwany wynik

albo przekroczenie rozmiaru zbioru, na którym wykonywane s obli

czenia.

Liczba kolejnych wywoa rekursywnych nie ma znaczenia. Czsto

jest wrcz niemoliwa do okrelenia przed rozpoczciem przetwarza

nia danych, nie zawsze bowiem da si okreli poziom zagbienia

w wywoania.

Wynik aktualnie realizowanego obliczenia rekurencyjnego zaley od

poprzedzajcego go powtórzenia. Kade kolejne wywoanie powo

duje zmniejszenie rozmiaru badanego zbioru (np. tablicy) o 1, dziki

czemu problem zostaje rozbity na czci elementarne, które operuj

na mniejszej liczbie danych — s zatem mniej skomplikowane. Do

piero w momencie powrotu z wywoa wyznaczane s wszystkie po

przednie wartoci.

1 1 6

A l g o r y t m y • w i c z e n i a

Rekurencja wokó nas

Postpowanie o charakterze rekurencyjnym trwale zwizane jest z wie

loma czynnociami zachodzcymi w otaczajcej nas rzeczywistoci,

cho czsto nie zauwaamy tego lub nie jestemy wiadomi.

Mona wskaza wiele przykadów czynnoci, które maj cechy rekur

sji, a s wykonywane przez czowieka, zwierzta albo zaprogramo

wane automaty. Chodzenie i bieganie, taczenie, jedzenie, masowe

toczenie na tokarce, zbieranie rozsypanych przedmiotów, mycie, zry

wanie owoców z drzewa itp.

Równie czsto opisujemy sownie procesy, stosujc jzyk typowy dla

rekursji. Instruujc kogo, jak naley my stos talerzy, mówimy:

„Umyj talerz do czysta i myj dalej”. Tumaczc, jak uoy na póce

rozsypane na pododze ksiki, powiemy: „Podnie ksik, ustaw

na póce i podobnie ukadaj kolejne”. Ten schemat postpowania jest

przedstawiony graficznie na rysunku 5.1. W obu przykadach czynno

jest powtarzana. Róne s jednak warunki zakoczenia rekurencji.

W pierwszym przykadzie koniec powinien nastpi, gdy talerze s

czyste, w drugim — gdy braknie ksiek do ustawiania.

Rysunek 5.1. Model rekurencyjnego ukadania ksiek na póce

Funkcja silnia

Zgodnie z obietnic dan w poprzednim rozdziale wracamy do funkcji

silnia . Tym razem poznamy algorytm i rekurencyjne wersje programów

wykonujcych stosowne obliczenia.

W I C Z E N I E

5.1

Algorytm rekurencyjnego obliczania n!

Przedstaw w postaci schematu blokowego rekurencyjny algorytm ob

liczania silni n !, n N . Dokonaj analizy przepywu w algorytmie

dla n = 3.

1 1 7

R o z d z i a 5 . • A l g o r y t m y r e k u r e n c y j n e

Rozwizanie

Dane: Liczba naturalna n wprowadzona przez uytkownika, równa

ostatniemu wyrazowi iloczynu.

Oczekiwany wynik : Warto funkcji n !.

Analiza problemu: Definicja silni n ! liczby naturalnej n wystpia

w poprzednim rozdziale w wiczeniu 4.4. Z definicji klasycznej n ! = 1

2 3 … n wynika wasno silni n ! = n ( n – 1)!, która pozwala okre

li t funkcj w postaci rekurencyjnej:

Obliczenie kolejnej wartoci n ! nastpuje poprzez pomnoenie war

toci poprzedniej ( n – 1)! przez nastpn liczb naturaln n . Tak zde

finiowana rekurencja nazywana jest liniow .

(

Proces obliczeniowy powinien by powtarzany, a n osignie warto

zadan przez uytkownika. Na podstawie powyszego mona zapisa

w innej formie rekurencyjn definicj funkcji silnia:

Algorytm przedstawiony na rysunku 5.2 skada si z dwóch czci:

algorytmu (programu) gównego i podprogramu realizujcego reku

rencyjne obliczanie funkcji silnia.

Powyszy algorytm mona próbowa scali, co pokazuje rysunek 5.3.

W tej formie rekurencyjny algorytm obliczania silni wystpuje w lite

raturze najczciej. Niestety obarczony jest powanym bdem, jakim

jest wczytywanie wartoci n przy kadym kolejnym odwoaniu reku

rencyjnym! Ten algorytm nie dziaa prawidowo.

Analiza przepywu w rekurencyjnym algorytmie obliczania silni

W algorytmie z rysunku 5.2 stosowane s dwie zmienne: n — liczba

naturalna wprowadzona przez uytkownika (dana wsadowa), Silnia

— warto funkcji silnia. Zapis z uyciem nawiasu: Silnia(argument)

oznacza warto funkcji dla podanego argumentu, na przykad Silnia(2)

oznacza warto funkcji silnia dla n = 2.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: