PProg_cw_03.pdf

Podstawyprogramowania

IrokAutomatykaiRobotykaPWr

wiczenia–Zestaw3

Zakresmateriału

Algorytmy,ichzapis,r¦cznasymulacja,analizazło»ono±ciobliczeniowej.

Zadania

1.Zapisa¢wpostacidiagramublokowegolubpseudokodualgorytmwyznaczaj¡cynajwi¦kszy

wspólnydzielnikdwóchliczb.Przeprowadzi¢r¦cz¡symulacj¦ 1 algorytmudlaprzykładowych

danych.

Wskazówka:Jednymzrozwi¡za«powy»szegoproblemujestalgorytmEuklidesa.

2.Przeformułowa¢przedstawionynawykładziealgorytmwyznaczaniaci¡guliczbFibonacciego

wpostacirekurencyjnejdopostaciiteracyjnej.Przeprowadzi¢r¦czn¡symulacj¦algorytmu

dlaprzykładowychdanych.

3.Dlaalgorytmupot¦gowania x n zzadania9azzestawu2

(a)przeprowadzi¢r¦czn¡symulacj¦dlawybranychdanychwej±ciowych,

(b)wyznaczy¢zło»ono±¢obliczeniow¡przyjmuj¡c,»eoperacj¡elementarn¡jestoperacja

mno»enia.

4.Przeanalizowa¢podanyponi»ejalgorytmpot¦gowaniaszybkiegoanast¦pnie:

(a)przeprowadzi¢r¦czn¡symulacj¦dlawybranychdanychwej±ciowych,

(b)pokaza¢,»ealgorytmpoprawniewyliczawarto±¢ x n ,

(c)wyznaczy¢zło»ono±¢obliczeniow¡przyjmuj¡c,»eoperacjamielementarnymis¡operacje

mno»eniaidzielenia( wskazówka: wyznaczy¢liczb¦operacjiwnajgorszyminajlepszym

przypadku),

(d)porówna¢zezło»ono±ci¡algorytmuzpoprzedniegozadania.

r 1

while n > 0

ifnot 2 | n

r r · x

x x · x

n n div 2

Uwaga: zapis„2 | n”oznacza„2dzielin”,natomiast div jestoperacj¡dzieleniacałkowitego.

1 Prosteprzykładysposobuprzeprowadzeniar¦cznejsymulacjizawartes¡wplikachpdfdoł¡czonychdotych

¢wicze«jakoMateriały.

Podstawyprogramowania,IrokAutomatykaiRobotykaPWr 2

5.Problemwie»yHanoi.Wie»askładasi¦ztrzechpr¦tów(A,B,C),naktórychumieszczo-

nokr¡»kioró»nych±rednicach.Kr¡»kimo»naprzenosi¢tylkopojedynczo,niemo»nate»

umieszcza¢wi¦kszegonamniejszym.Zadaniepoleganaprzeniesieniuwie»yzpr¦taAnaC

(uło»eniewej±ciowepokazanejestnarysunku)

(a)zaproponowa¢algorytmukładaniawie»yHanoiodowolnejwysoko±ci,(zakładamy,»e

istniejefunkcja przeloz (x,y),któraprzenosikr¡»ekzpr¦taxnapr¦ty),

(b)wyznaczy¢zło»ono±¢algorytmuprzyzało»eniu,»eoperacj¡elementarn¡jestprzeło»enie

kr¡»ka.

6.Zaproponowa¢algorytmwyszukiwaniasłowawtek±cie(dokładnegodopasowania).Danymi

wej±ciowymialgorytmus¡dwanapisy(tabliceznaków),zktórychpierwszyjesttekstem,w

którymposzukujemysłowa,adrugi–poszukiwanymsłowem.Algorytmpowinienzwraca¢

pozycj¦pierwszegowyst¡pieniaposzukiwanegosłowalub-1gdysłowowtek±cieniewyst¦-

puje.

7.Zaproponowa¢algorytmsprawdzaniaczydanyci¡gznakówjestpalindromem(słowemczy-

tanymtaksamowprzódiwspak,np. kajak ).Algorytmpowiniennawej±ciuotrzymywa¢

napis(tablic¦znaków)izwraca¢1,gdysłowojestpalindromem,a0–gdynimniejest.

( wersjatrudniejsza: analiziepoddawanes¡całezdania,pomijasi¦wtedyodst¦pyiznaki

przestankowe–takimpalindromemjestnp.„kobyłamamałybok”).

8.Znale¹¢algorytmwyznaczaj¡cyprzyu»yciuoperacjisumowaniaelementy i -tegowierszatrój-

k¡taPascala,któregokilkapierwszychpoziomówprzedstawinoponi»ej.

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 1010 5 1

6 1 6 152015 6 1

7 1 7 213535 217 1

8 1 8 28567056 288 1

9 1 936 8412612684369 1

...................

Wskazówka:Zastanowi¢si¦wjakisposóbmo»nawyznaczy¢szukanewierszeprzyu»yciu

jednejtablicyjednowymiarowej.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: