8 Lab
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 8 Lab as PDF for free.
More details
- Words: 530
- Pages: 2
A 8. laborat´ orium anyaga 1. ´Irja meg az egy sz´am faktori´alis´at kisz´amol´o f¨ uggv´enyt iterat´ıvan ´es rekurz´ıvan is. Hasonl´ıtsa ¨ossze a fut´asi id˝oket egy nagyobb sz´ammal val´o h´ıv´as eset´en. 2. Haszn´alja a fejleszt˝ok¨ornyezet debugger szolg´altat´as´at (vagy pl. a gdb programot) ´es figyelje meg a program fut´as´at, amikor megh´ıvja az el˝oz˝o feladat rekurz´ıv f¨ uggv´eny´et. 3. ´Irjon C f¨ uggv´enyt, amely megkapja egy binomi´alis egyenlet foksz´am´at ´es az egy¨ utthat´o sorsz´am´at, ´es visszat´er a megfelel˝o egy¨ utthat´oval. Eml´ekeztet˝ o: a binomi´alis t´etel a k¨ovetkez˝o: n
(a + b) =
n ³ ´ X n k=0
teh´at az el˝o´all´ıtand´o ´ert´ek:
³n´ k
=
k
an−k · bk
n! k! · (n − k)!
ahol n az egyenlet foksz´ama, k pedig az egy¨ utthat´o sorsz´ama. Az egy¨ utthat´ok itt 0-t´ol sz´amoz´odnak!
4. ´Irja meg a fenti f¨ uggv´enyt a Pascal-h´aromsz¨og felhaszn´al´as´aval rekurz´ıvan! Eml´ekeztet˝ o: a Pascal h´aromsz¨og a k¨ovetkez˝ok´eppen n´ez ki: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 Egy adott elem a felette l´ev˝o kett˝o ¨osszege. A harmadik sor a m´asodfok´ u egyenlet egy¨ utthat´oit tartalmazza, a negyedik a harmadfok´ u´et ´es ´ıgy tov´abb, teh´at a fenti feladatban adott k´epletben n a Pascal-h´aromsz¨ og n. sora, k pedig a sor k. eleme.
5. Gondolkodjon el a fenti feladat k´et megold´asa k¨ozti k¨ ul¨onbs´egeken. Melyik el˝ony¨osebb? Tipp: ´altal´aban az iterat´ıv megold´asok gyorsabbak ´es kisebb a mem´oriaig´eny¨ uk. Ebben az esetben azonban a faktori´alis kisz´am´ıt´asa t´ ulcsordul´ast okozhat olyankor is, amikor a v´egeredm´eny m´eg nem okozna.
6. Defini´aljon egy mutat´ot´ıpust, amely egyv´altoz´os matematikai f¨ uggv´enyek c´ım´et k´epes elt´arolni. 7. ´Irjon f¨ uggv´enyt, amely k´epes egy tetsz˝oleges matematikai f¨ uggv´eny lok´alis minimum´at megkeresni egy adott intervallumban ´es felbont´assal. Tipp: az adott intervallum hat´arai k¨oz¨ott a megadott felbont´asnak megfelel˝o l´ep´esk¨ozzel kell v´egighaladni ´es minimumot keresni.
1
8. ´Irjon f¨ uggv´enyt, amely ´atvesz egy intervallumot, egy l´ep´esk¨ozt ´es egy egyv´altoz´os matematikai f¨ uggv´enyt ´es egy dinamikusan l´etrehozott t¨ombben visszaadja a f¨ uggv´eny els˝o deriv´altj´at azon az intervallumon. Tipp: a t¨ombnek annyi eleme lesz, amennyiszer a megadott l´ep´esk¨oz megvan az intervallum m´eret´eben. A deriv´altak sz´am´ıt´as´ahoz mindig k´et elem kell, ´ıgy egy (f´el) elemmel el lesznek tol´odva az ´ert´ekek – ez a v´eges felbont´as k¨ovetkezm´enye.
9. ´Irjon f¨ uggv´enyt, amely ´atvesz egy k´etdimenzi´os karaktert¨omb¨ot ´es egy elem k´et index´et. A karaktert¨omb egy labirintust tartalmaz, ahol p´eld´aul X karakterek jelzik a falakat, ´es sz´ok¨oz¨ok a j´aratokat. A labirintust a fala teljesen bekeretezi, kiv´eve egy pontot, amely a kij´arat. A f¨ uggv´eny a megadott kiindul´o poz´ıci´ot´ol indulva keresse meg a kij´aratot ´es az odavezet˝o u ´tvonalat rajzolja bele a labirintusba. A f¨ uggv´eny megv´altoztathatja a labirintust, p´eld´aul jel¨olheti azokat a pontokat, ahol m´ar j´art.
Gyakorl´ o p´ eld´ ak a rekurzi´ ohoz 1. ´Irjon programot, amely rekurz´ıvan kisz´amolja k´et sz´am legnagyobb k¨oz¨os oszt´oj´at! 2. ´Irjon programot, amely whitespace-ekkel hat´arolt szavakat olvas a standard inputr´ol. 3. Az u ´gynevezett Schr¨oder sz´am megadja, hogy egy n × n m´eret˝ u n´egyzeth´al´on mennyi elemi l´ep´essel juthatunk el a bal als´o sarokb´ol a jobb fels˝obe mindig a f˝o´atl´on, vagy alatta haladva. Tudjuk, hogy S0 = 1, valamint Sn = Sn−1 +
n−1 X
Sk · Sn−1−k
k=0
´Irjon f¨ uggv´enyt, amely kisz´am´ıtja, az n-edik Schr¨oder sz´amot.
2
(a + b) =
n ³ ´ X n k=0
teh´at az el˝o´all´ıtand´o ´ert´ek:
³n´ k
=
k
an−k · bk
n! k! · (n − k)!
ahol n az egyenlet foksz´ama, k pedig az egy¨ utthat´o sorsz´ama. Az egy¨ utthat´ok itt 0-t´ol sz´amoz´odnak!
4. ´Irja meg a fenti f¨ uggv´enyt a Pascal-h´aromsz¨og felhaszn´al´as´aval rekurz´ıvan! Eml´ekeztet˝ o: a Pascal h´aromsz¨og a k¨ovetkez˝ok´eppen n´ez ki: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 Egy adott elem a felette l´ev˝o kett˝o ¨osszege. A harmadik sor a m´asodfok´ u egyenlet egy¨ utthat´oit tartalmazza, a negyedik a harmadfok´ u´et ´es ´ıgy tov´abb, teh´at a fenti feladatban adott k´epletben n a Pascal-h´aromsz¨ og n. sora, k pedig a sor k. eleme.
5. Gondolkodjon el a fenti feladat k´et megold´asa k¨ozti k¨ ul¨onbs´egeken. Melyik el˝ony¨osebb? Tipp: ´altal´aban az iterat´ıv megold´asok gyorsabbak ´es kisebb a mem´oriaig´eny¨ uk. Ebben az esetben azonban a faktori´alis kisz´am´ıt´asa t´ ulcsordul´ast okozhat olyankor is, amikor a v´egeredm´eny m´eg nem okozna.
6. Defini´aljon egy mutat´ot´ıpust, amely egyv´altoz´os matematikai f¨ uggv´enyek c´ım´et k´epes elt´arolni. 7. ´Irjon f¨ uggv´enyt, amely k´epes egy tetsz˝oleges matematikai f¨ uggv´eny lok´alis minimum´at megkeresni egy adott intervallumban ´es felbont´assal. Tipp: az adott intervallum hat´arai k¨oz¨ott a megadott felbont´asnak megfelel˝o l´ep´esk¨ozzel kell v´egighaladni ´es minimumot keresni.
1
8. ´Irjon f¨ uggv´enyt, amely ´atvesz egy intervallumot, egy l´ep´esk¨ozt ´es egy egyv´altoz´os matematikai f¨ uggv´enyt ´es egy dinamikusan l´etrehozott t¨ombben visszaadja a f¨ uggv´eny els˝o deriv´altj´at azon az intervallumon. Tipp: a t¨ombnek annyi eleme lesz, amennyiszer a megadott l´ep´esk¨oz megvan az intervallum m´eret´eben. A deriv´altak sz´am´ıt´as´ahoz mindig k´et elem kell, ´ıgy egy (f´el) elemmel el lesznek tol´odva az ´ert´ekek – ez a v´eges felbont´as k¨ovetkezm´enye.
9. ´Irjon f¨ uggv´enyt, amely ´atvesz egy k´etdimenzi´os karaktert¨omb¨ot ´es egy elem k´et index´et. A karaktert¨omb egy labirintust tartalmaz, ahol p´eld´aul X karakterek jelzik a falakat, ´es sz´ok¨oz¨ok a j´aratokat. A labirintust a fala teljesen bekeretezi, kiv´eve egy pontot, amely a kij´arat. A f¨ uggv´eny a megadott kiindul´o poz´ıci´ot´ol indulva keresse meg a kij´aratot ´es az odavezet˝o u ´tvonalat rajzolja bele a labirintusba. A f¨ uggv´eny megv´altoztathatja a labirintust, p´eld´aul jel¨olheti azokat a pontokat, ahol m´ar j´art.
Gyakorl´ o p´ eld´ ak a rekurzi´ ohoz 1. ´Irjon programot, amely rekurz´ıvan kisz´amolja k´et sz´am legnagyobb k¨oz¨os oszt´oj´at! 2. ´Irjon programot, amely whitespace-ekkel hat´arolt szavakat olvas a standard inputr´ol. 3. Az u ´gynevezett Schr¨oder sz´am megadja, hogy egy n × n m´eret˝ u n´egyzeth´al´on mennyi elemi l´ep´essel juthatunk el a bal als´o sarokb´ol a jobb fels˝obe mindig a f˝o´atl´on, vagy alatta haladva. Tudjuk, hogy S0 = 1, valamint Sn = Sn−1 +
n−1 X
Sk · Sn−1−k
k=0
´Irjon f¨ uggv´enyt, amely kisz´am´ıtja, az n-edik Schr¨oder sz´amot.
2
