Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.3. Feladatok

1.3. Feladatok

  1. Bizonyítsuk be az alsó és felső egészrész függvényeknek a szövegben összefoglalt 1.-5.- tulajdonságait!

  2. Adott egy előjel nélküli egész számokat tároló, duplaszavas elemekből álló tömb a memóriában, amely egy alsó háromszög mátrixot tárol. Alsó háromszög mátrixnak nevezzük azt a négyzetes mátrixot, amelynek a fődiagonálisa feletti elemei garantáltan zérusok. A mátrixot sorfolytonosan tároljuk. A fődiagonális feletti elemeket nem tároljuk, hiszen tudjuk, hogy azok zérusok. Adjon formulát az elem kezdő byte-ja tömbkezdethez képest relatív indexének kiszámítására! A relatív indexeket zérustól kezdve számláljuk. Ha a tömbelem nincs tárolva, az index legyen negatív (mondjuk -1). Feltételezzük, hogy az indexpár az -es tömb valódi elemére mutat, azaz teljesül.

  3. Legyen a következő P(a,b) kétváltozós függvényünk, amelyet nemnegatív egész argumentumokra értelmezünk rekurzívan: zérus, ha , , ha pozitív és páros, egyébként. Procedúrahívással számíttassuk ki a számot! Hogyan alakul a verem felépítése, mélysége? Mekkora a minimális méretű verem, amely a feladat elvégzéséhez szükséges? Hány rekurzív hívás lesz a számolás során?