Algorytmy cwiczenia calgor

[ Pobierz całość w formacie PDF ]
Algorytmy.
Autor: Bogdan Buczek
ISBN: 978-83-246-2007-4
Format: A5, stron: 272
Wydawnictwo Helion
ul. Koľciuszki 1c
44-100 Gliwice
tel. 032 230 98 63
e-mail: helion@helion.pl
Poznaj algorytmy, a profesjonalne programowanie nie bķdzie miaĀo przed TobĴ tajemnic
¤
Jak zaprojektowaě rozwiĴzanie problemu w formie algorytmu?
¤
Jak stosowaě instrukcje iteracyjne?
¤
Jak przedstawiě algorytm w postaci schematu blokowego?
W czasach ery informatycznej coraz wiķksza liczba osb zainteresowana jest zdobyciem
umiejķtnoľci programowania. JednakŃe umiejķtnoľě ta wymaga zarwno rozlegĀej
i rzetelnej wiedzy, jak i doľwiadczenia. PodstawĴ owej wiedzy jest dobra znajomoľě
algorytmw, ktra umoŃliwia przeprowadzanie kolejnych etapw programowania.
Pozwala ona na przechodzenie od analizy i zdefiniowania problemu, poprzez testowanie
i usuwanie bĀķdw, aŃ do opracowania dokumentacji. KsiĴŃka, ktrĴ trzymasz w rķkach,
pomoŃe Ci zrozumieě kaŃdĴ z tych faz i nauczy Ciķ pisaě wĀasny kod.
âAlgorytmy. ĚwiczeniaÒ to niezbķdny elementarz dla kaŃdego przyszĀego programisty.
Dziķki temu podrķcznikowi poznasz rŃne sposoby opisu algorytmw oraz ich
klasyfikacjķ. Dowiesz siķ, jaki wpĀyw ma zastosowanie okreľlonej metody obliczeniowej
na dokĀadnoľě wynikw koĺcowych, a takŃe, na czym polega przetwarzanie danych
w pķtli programowej. WykonujĴc kolejne ěwiczenia, opatrzone szczegĀowymi
komentarzami i wskazwkami, nauczysz siķ pisaě algorytmy, sporzĴdzaě wykresy
i schematy blokowe oraz tworzyě kod programu. KsiĴŃka jest doskonaĀym
podrķcznikiem dla studentw informatyki, jednak dziķki temu, Ńe wszystkie informacje
przedstawiono tu w jasny i klarowny sposb, moŃe z niej korzystaě kaŃdy, kto chce
rozpoczĴě samodzielne programowanie.
¤
Sposoby opisu algorytmw
¤
Klasyfikacja algorytmw
¤
Algorytmy sekwencyjne
¤
Kodowanie algorytmw
¤
Algorytmy z rozgaĀķzieniami
¤
Przetwarzanie danych w pķtli programowej
¤
Algorytmy iteracyjne
¤
Funkcja silnia
¤
Instrukcje iteracyjne w Turbo Pascal i Visual Basic
¤
Algorytmy rekurencyjne
¤
Schemat Kornera
¤
Pozycyjne systemy liczbowe
¤
Algorytmy sortowania danych
Poznaj algorytmy i zacznij myľleě jak programista!
Ěwiczenia
Spis treci
Wstp
5
Rozdzia 1. Niezbdne informacje o algorytmach
7
Czym jest algorytm?
7
Ocena jakoci algorytmu
9
Planowanie pracy
9
Sposoby opisu algorytmów
11
Klasyfikacja algorytmów
22
Podsumowanie
24
Rozdzia 2. Algorytmy sekwencyjne. Kodowanie algorytmów
27
Algorytm sekwencyjny
27
Obliczanie wartoci funkcji
28
Kodowanie algorytmów
29
Liczymy koszt rozmowy telefonicznej
45
Uwagi kocowe
55
wiczenia do samodzielnego wykonania
57
Rozdzia 3. Algorytmy z rozgazieniami.
Sterowanie przepywem w algorytmie
59
Algorytm z rozgazieniami
59
Miejsce zerowe funkcji, rozwizanie równania liniowego
61
Obliczanie pierwiastków równania kwadratowego
68
Uwagi kocowe
86
wiczenia do samodzielnego wykonania
88
 4
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
91
Algorytm iteracyjny
91
Rysowanie gwiazdek
94
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
5
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.
[ Pobierz całość w formacie PDF ]