Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.12. Feladatok

1.12. Feladatok

  1. Adjunk meg algoritmust az alábbi problémák megoldására szövegesen is és pszeudokóddal is. Készítsük el a megfelelő folyamatábrát! Adjuk meg az algoritmus 7 jellemző vonását! Adjuk meg az algoritmus időbonyolultságát és tárbonyolultságát az input méretének függvényében! Adjuk meg ezen bonyolultságokra a növekedési rendet!

    • Két pozitív egész szám (az egyik jegyű, a másik jegyű) kézi összeadása.

    • Két pozitív egész szám (az egyik jegyű, a másik jegyű) kézi összeszorzása.

  2. Adjunk meg a Fibonacci számok növekedésének jellemzésében a definíciójának megfelelő konstansokat és küszöbméretet!

  3. Bizonyítsuk be, hogy !

  4. Oldjuk meg rekurzív visszahelyettesítéssel a következő rekurzív egyenletet!

  5. Adjunk aszimptotikus megoldást a következő rekurzív egyenletre a mester tétellel!