zajecia3.pdf

Zaj¦cia 3 Podstawowepoj¦ciainarz¦dziainformatyki

Podstawowyalgorytmówschematyblokoweipseudokod.

Algorytmyiteracyjneirekurencyjne.

Algorytm iteracyjny - algorytm, który uzyskuje wynik przez powtarzanie

danej operacji okre±lon¡ ilo±¢ razy.

Algorytm rekurencyjny - algorytm, który wywołuje sam siebie do roz-

wi¡zania tego samego problemu.

Informacje na temat schematów blokowych:

— Troch¦ o schamtach blokowych http://pl.wikipedia.org/wiki/Schema t_

blokowy

— Elementy schematów blokowych http://kasia315.republika.pl/kurs/

lekcja2.htm

Przykłady Schematów blokowych :

— Silnia iteracyjnie http://codecity.info/?q=node/41

— Algorytm Euklidesa http://codecity.info/?q=node/90

B¦dziemy na zaj¦ciach korzysta¢ z programu „Magiczne Bloczki” gdy»

pozwala on zweryﬁkowa¢ czy nasz algorytm jest poprawny:

— Magiczne bloczki instrukcja obsługi http://usersp.w.interia.pl/pomo c/

algorytm.htm

— Przykłady algorytmów zrobionych w Magicznych Bloczkach http://

magiczne.bloczki.prv.pl/algorytmy.htm

Drugim aspektem jest zapis algorytmów w pseudokodzie:

— Notacja u»ywana w pseudokodzie http://www.ics.p.lodz.pl/~akmieci k/

pl/dydaktyka/Algorytmy/pseudo.htm

Jako, »e macie pa«stwo zaj¦cia z programowania mo»na tak»e korzysta¢

zamiast notacji takiej jak powy»ej notacji z j¦zyka C, lub zbli»onej (ka»da

zrozumiała notacja jest poprawna).

Zadaniana¢wiczenia

Zadanie1

Narysowa¢ schemat blokowy algorytmu sprawdzania czy traﬁli±my szóst-

k¦ w Totka. Zakładamy, »e na wej±ciu znajduje si¦ sze±¢ posortowanych liczb

oraz na kuponie tak»e znajduje si¦ sze±¢ posortowanych liczb.

Tablice wej±ciowe podajemy podaj¡c liczby przedzielone przecinkiem. Do

i-tego elementu tablicy „kupon” odwołujemy si¦ poprzez „kupon[i]”. mo»na

skorzysta¢ z pliku obejmuj¡cego wczytywanie danych http://www.staff.

amu.edu.pl/~mw/DNIF/lotto.alg .

Zadanie2 Wyszukiwanie binarne jest algorytmem opieraj¡cym si¦ na

metodzie dziel i zwyci¦»aj. Szukaj¡c danego elementu w posortowanej n- ele-

mentowej tablicy sprawdzamy czy ±rodkowy element jest równy, mniejszy,

b¡d¹ wi¦kszy od szukanego. W zale»no±ci od wyniku kontynuujemy wyszu-

kiwanie na pierwszej lub drugiej połowie tablicy. W przypadku gdy element

Zaj¦cia 3 Podstawowepoj¦ciainarz¦dziainformatyki

jest równy szukanemu ko«czymy wyszukiwanie. Zapisz w pseudokodzie al-

gorytm wyszukiwania binarnego w postaci iteracyjnej i rekurencyjnej.

Zadanie3

Narysowa¢ w Magicznych Bloczkach schemat blokowy algorytmu sor-

towania przez wstawianie. Opis algorytmu mo»na znale¹¢ tutaj http://

kondel.ko.funpic.de/?pid=53 .

Zadanie4

Narysowa¢ w Magicznych Bloczkach schemat blokowy algorytmu sorto-

wania b¡belkowego. Opis algorytmu mo»na znale¹¢ tutaj http://pl.wikiped ia.

org/wiki/Sortowanie_b%C4%85belkowe .

Zadanie5

Napisa¢ psudokod iteracyjnego i rekurencyjnego algorytmu obliczaj¡cego

N-ty element ci¡gu zdeﬁniowanego w nast¦puj¡cy sposób:

8 > > > > > > <

> > > > > > :

0 dla n = 0;

1 dla n = 1;

2 dla n = 2;

F n − 1 + F n − 2 + F n − 3 dla n> 2 .

(czyli ci¡g ten wygl¡da nast¦puj¡co 0,1,2,3,6,11,20,...). Zaimplementowa¢

w magicznych bloczkach wersj¦ iteracyjn¡ algorytmu. Sprawdzi¢ jaki jest 25

element tego ci¡gu.

Informacjeko«cowe

Jedne z zada« na kolokwium b¦dzie obejmowało narysowanie na kartce

schematu blokowego oraz rozpisania w pseudokodzie wybranego algorytmu.

St¡d z zaj¦¢ tych nie ma zadania domowego.

F n :=

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: