Algorytmy cwiczenia.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

Rozdzia 1. Niezbdne informacje o algorytmach

Czym jest algorytm?

Ocena jakoci algorytmu

Planowanie pracy

Sposoby opisu algorytmów

Klasyfikacja algorytmów

Podsumowanie

Rozdzia 2. Algorytmy sekwencyjne. Kodowanie algorytmów

Algorytm sekwencyjny

Obliczanie wartoci funkcji

Kodowanie algorytmów

Liczymy koszt rozmowy telefonicznej

Uwagi kocowe

wiczenia do samodzielnego wykonania

Rozdzia 3. Algorytmy z rozgazieniami.

Sterowanie przepywem w algorytmie

Algorytm z rozgazieniami

Miejsce zerowe funkcji, rozwizanie równania liniowego

Obliczanie pierwiastków równania kwadratowego

Uwagi kocowe

wiczenia do samodzielnego wykonania

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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: