Algorytmy_cwiczenia_calgor.pdf

(587 KB) Pobierz
Algorytmy.
Æwiczenia
Autor: Bogdan Buczek
ISBN: 978-83-246-2007-4
Format: A5, stron: 272
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 osób zainteresowana jest zdobyciem
umiejêtnoœci programowania. Jednak¿e umiejêtnoœæ ta wymaga zarówno rozleg³ej
i rzetelnej wiedzy, jak i doœwiadczenia. Podstaw¹ owej wiedzy jest dobra znajomoœæ
algorytmów, która umo¿liwia przeprowadzanie kolejnych etapów programowania.
Pozwala ona na przechodzenie od analizy i zdefiniowania problemu, poprzez testowanie
i usuwanie b³êdów, a¿ do opracowania dokumentacji. Ksi¹¿ka, któr¹ 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 algorytmów oraz ich
klasyfikacjê. Dowiesz siê, jaki wp³yw ma zastosowanie okreœlonej metody obliczeniowej
na dok³adnoœæ wyników koñcowych, a tak¿e, na czym polega przetwarzanie danych
w pêtli programowej. Wykonuj¹c kolejne æwiczenia, opatrzone szczegó³owymi
komentarzami i wskazówkami, nauczysz siê pisaæ algorytmy, sporz¹dzaæ wykresy
i schematy blokowe oraz tworzyæ kod programu. Ksi¹¿ka jest doskona³ym
podrêcznikiem dla studentów informatyki, jednak dziêki temu, ¿e wszystkie informacje
przedstawiono tu w jasny i klarowny sposób, mo¿e z niej korzystaæ ka¿dy, kto chce
rozpocz¹æ samodzielne programowanie.
•
Sposoby opisu algorytmów
•
Klasyfikacja algorytmów
•
Algorytmy sekwencyjne
•
Kodowanie algorytmów
•
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
Wydawnictwo Helion
ul. Koœciuszki 1c
44-100 Gliwice
tel. 032 230 98 63
e-mail: helion@helion.pl
Poznaj algorytmy i zacznij myœleæ jak programista!
Spis tre ci
WstÚp
Rozdziaï 1. NiezbÚdne informacje o algorytmach
Czym jest algorytm?
Ocena jako ci algorytmu
Planowanie pracy
Sposoby opisu algorytmów
Klasyfikacja algorytmów
Podsumowanie
5
7
7
9
9
11
22
24
Rozdziaï 2. Algorytmy sekwencyjne. Kodowanie algorytmów
Algorytm sekwencyjny
Obliczanie warto ci funkcji
Kodowanie algorytmów
Liczymy koszt rozmowy telefonicznej
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
27
27
28
29
45
55
57
Rozdziaï 3. Algorytmy z rozgaïÚzieniami.
Sterowanie przepïywem w algorytmie
Algorytm z rozgaïÚzieniami
Miejsce zerowe funkcji, rozwiÈzanie równania liniowego
Obliczanie pierwiastków równania kwadratowego
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
59
59
61
68
86
88
4
Algorytmy • mwiczenia
Rozdziaï 4. Algorytmy iteracyjne. Przetwarzanie danych w pÚtli
programowej
Algorytm iteracyjny
Rysowanie gwiazdek
Co umo liwia iteracja?
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
91
91
94
102
110
111
Rozdziaï 5. Algorytmy rekurencyjne
Algorytm rekurencyjny
Funkcja silnia
Obliczanie potÚgi liczby rzeczywistej
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
115
115
116
127
134
137
Rozdziaï 6. Schemat Hornera. Obliczanie warto ci wielomianu
Schemat Hornera
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
139
139
165
167
Rozdziaï 7. Pozycyjne systemy liczbowe
System liczbowy
Obliczanie warto ci liczby zapisanej
w dowolnym systemie pozycyjnym
Przedstawianie liczb w dowolnym
pozycyjnym systemie liczbowym
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
169
169
174
194
214
216
Rozdziaï 8. Algorytmy sortowania danych
Sortowanie zbioru danych
Metody sortowania zbioru danych
Uwagi koñcowe
mwiczenia do samodzielnego wykonania
217
217
220
265
266
5
Algorytmy rekurencyjne
Algorytm rekurencyjny
Rekurencja,
zwana równie
rekursjÈ,
jest technikÈ programowania,
w której stosowany jest podprogram (funkcja lub procedura) wywo-
ïujÈcy sam siebie albo wywoïujÈcy innÈ procedurÚ, która wywoïa
podprogram pierwotny. W tym drugim przypadku mówimy o
rekur-
sji podwójnej
lub
skro nej.
Kolejne wywoïania trwajÈ, a do osiÈ-
gniÚcia warunku zakoñczenia rekurencji. Jest nim oczekiwany wynik
albo przekroczenie rozmiaru zbioru, na którym wykonywane sÈ obli-
czenia.
Liczba kolejnych wywoïañ
rekursywnych
nie ma znaczenia. CzÚsto
jest wrÚcz niemo liwa do okre lenia przed rozpoczÚciem przetwarza-
nia danych, nie zawsze bowiem da siÚ okre liÊ poziom zagïÚbienia
w wywoïania.
Wynik aktualnie realizowanego obliczenia rekurencyjnego zale y od
poprzedzajÈcego go powtórzenia. Ka de kolejne wywoïanie powo-
duje zmniejszenie rozmiaru badanego zbioru (np. tablicy) o 1, dziÚki
czemu problem zostaje rozbity na czÚ ci elementarne, które operujÈ
na mniejszej liczbie danych — sÈ zatem mniej skomplikowane. Do-
piero w momencie powrotu z wywoïañ wyznaczane sÈ wszystkie po-
przednie warto ci.
116
Algorytmy • mwiczenia
Rekurencja wokóï nas
PostÚpowanie o charakterze rekurencyjnym trwale zwiÈzane jest z wie-
loma czynno ciami zachodzÈcymi w otaczajÈcej nas rzeczywisto ci,
choÊ czÚsto nie zauwa amy tego lub nie jeste my wiadomi.
Mo na wskazaÊ wiele przykïadów czynno ci, które majÈ cechy rekur-
sji, a sÈ wykonywane przez czïowieka, zwierzÚta albo zaprogramo-
wane automaty. Chodzenie i bieganie, tañczenie, jedzenie, masowe
toczenie na tokarce, zbieranie rozsypanych przedmiotów, mycie, zry-
wanie owoców z drzewa itp.
Równie czÚsto opisujemy sïownie procesy, stosujÈc jÚzyk typowy dla
rekursji. InstruujÈc kogo , jak nale y myÊ stos talerzy, mówimy:
„Umyj talerz do czysta i myj dalej”. TïumaczÈc, jak uïo yÊ na póïce
rozsypane na podïodze ksiÈ ki, powiemy: „Podnie ksiÈ kÚ, ustaw
na póïce i podobnie ukïadaj kolejne”. Ten schemat postÚpowania jest
przedstawiony graficznie na rysunku 5.1. W obu przykïadach czynno Ê
jest powtarzana. Ró ne sÈ jednak warunki zakoñczenia rekurencji.
W pierwszym przykïadzie koniec powinien nastÈpiÊ, gdy talerze sÈ
czyste, w drugim — gdy braknie ksiÈ ek do ustawiania.
Rysunek 5.1.
Model rekurencyjnego ukïadania ksiÈ ek 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
wykonujÈcych stosowne obliczenia.
m 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!, nN.
Dokonaj analizy przepïywu w algorytmie
dla
n
= 3.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin