Javított buborékrendezés
A buborékrendezés egymás melletti elemeket cserél sorban. Egy sor csere hatására a legnagyobb elem a tömb végére vándorol; a következő körben azt már nem kell vizsgálni, hanem a tömb eggyel rövidebb részletét csak. Ezt kell folytatni addig, amíg el nem fogy a tömb.
A buborékrendezés hatékonysága javítható azzal, ha megjegyezzük, hogy a vizsgált tömbrészletnél volt-e csere. Ha nem volt, akkor minden pár jó sorrendben van. Akkor a rövidebb részt vizsgálva is ugyanerre az eredményre jutnánk, vagyis a külső ciklust már nem kell folytatni. Implementáld ezt a változatot!
Lineáris és bináris keresés
Töltsünk fel egy nagy tömböt véletlenszámokkal. Rendezzük a tömböt. Válasszunk egy elemet a tömb értékkészletéből, és keressük meg, hogy a rendezett tömb mely tartományában szerepel (hányadiktól hányadik indexig). Tegyük ezt a keresést a lehető leggyorsabban!
A három legkisebb
Írjunk programot, amelyik egy tömbből kiírja a három legkisebb elemet.
Medián
Írj függvényt, amely átvesz egy double elemekből álló tömböt, és visszaadja a medián elemét! A medián az az elem, amelynél annyi kisebb van a tömbben, ahány nagyobb. Felteheted, hogy a tömbben páratlan sok elem van, és nincs két egyforma. Tetszőlegesen használhatsz segédfüggvényeket, memóriát, de az eredeti tömböt nem változtathatod meg!
Dicsőséglista
Játékot kell írni, amely egy maximum 20 nevet tároló dicsőséglistát vezet. A
maximum 100 karakteres nevek mindegyikéhez egy egész pontszám tartozik.
Írd meg a következő függvényeket:
1. függvény: eldönti egy adott pontszámról, hogy felkerül-e a listára. Igaz/hamis értékkel tér vissza.
2. függvény: kiírja a képernyőre a dicsőséglistát.
3. függvény: felvesz egy új bejegyzést (név, pontszám) a listára, és visszatér a helyezéssel. (-1, ha nem került fel a listára.) A legkisebb pontszámú bejegyzés ilyenkor törlődik.
Negatívak indexei
A tanórákon szerepelt egy olyan feladat, amelyben egy tömbből ki kellett válogatni a negatív számokat, és az indexeiket egy másik tömbbe másolni. Az indexek alapján a negatív számok könnyen visszakereshetőek, mert tudni lehet, milyen sorszámokon szerepelnek az eredeti tömbben negatív számok:
Összesen 10 szám van. [0]=2.5 [1]=-69 [2]=5.4 [3]=-8 [4]=-7.7 [5]=6 [6]=2.9 [7]=-10 [8]=-3 [9]=9.8 Ebből 5 szám negatív. [1]=-69 [3]=-8 [4]=-7.7 [7]=-10 [8]=-3
A feladat most látszólag ugyanez, de fordítva: adott egy tömb, néhány negatív számmal, és adott a másik tömb, amely a negatív elemek indexeit tartalmazza. De nem a negatív számokat kell kilistázni az indextömböt felhasználva, hanem pont azokat, amelyek nem negatívak.
A megoldáshoz ne az eredeti tömbben keress, hanem használd föl a negatívak ismert indexeit! Általánosságban: adott egy tömb, valamilyen adatokkal, és adott mellé egy másik tömb, amely az előzőbe mutató indexeket tartalmaz. Azokat az elemeket kell kilistázni, amelyeket nem hivatkozik meg az indexelő tömb.
Meg lehet ezt a feladatot ϴ(n²) időben oldani? És meg lehet ϴ(n) időben oldani? Ha igen, mi a feltétele?
Számtani sorozat
Egy számtani sorozat minden elemét úgy kapjuk, hogy az eggyel előző eleméhez hozzáadjuk a különbséget (differenciát):
an = an-1 + d
A sorozatra függvényként tekintve, írj rekurzív függvényt, amelyik meghatározza egy számtani sorozat n-edik elemét!
A függvény paraméterei: szamtani(n, kezdo, diff), azaz a keresett elem sorszáma, a kezdőérték és a differencia.
Mi lesz a rekurzió báziskritériuma?
Írd meg ugyanígy azt a függvényt is, amelyik egy mértani sorozat valamely elemét határozza meg; ezt is rekurzívan! A definíció az előzőhöz hasonló, csak itt egy hányadossal szorzunk:
bn = bn-1 · q
Egészítsd ki úgy a programot, hogy kiírod egy-egy sorozat első tíz elemét!
5 7 9 11 13 15 17 19 21 23
5 10 20 40 80 160 320 640 1280 2560
Fibonacci
Írj programot, mely kiírja a képernyőre az első n Fibonacci számot. Az n változó értékét a felhasználó adhassa meg! Írd meg rekurzívan és iteratívan is!
Fibonacci szám-e
Készíts programot, mely a felhasználótól bekér egy természetes számot, majd megállapítja róla, hogy a szám Fibonacci szám-e!
Collatz-féle sorozat
A matematikában a Lothar Collatzról elnevezett sorozatot a következőképpen definiáljuk. Kezdőértéknek válasszunk egy tetszőleges egész számot. A sorozatnak minden további elemét az előzőből származtatjuk, méghozzá így:
- an+1 = an / 2, ha an páros
- an+1 = 3an + 1, ha an páratlan
A sejtés az, hogy ez a sorozat mindig eléri az 1-et – ezt máig senkinek nem sikerült sem bizonyítania, sem ellenpéldát találni rá. A sorozatban néha csak a kezdőelemnél kisebb számok vannak:
20 10 5 16 8 4 2 1
Néha azonban eléggé megnő:
23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Írj programot, amely a) kiírja a sorozatot egy meghatárázott értéktől kiindulva, b) megmondja, hogy hány lépés kell egy adott értéktől kiindulva 1-ig elérni! Írd meg ezeket iteratív és rekurzív változatban is!
Négyzetszámok lánca
A szóban forgó sorozatot úgy állítjuk elő, hogy mindig egy adott szám összes számjegyének négyzetét vesszük, és azok összege adja a sorozat következő elemét. Egészen addig ismételjük ezt, amíg el nem érünk egy olyan számhoz, amit már láttunk. Például:
44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Vagyis minden sorozat, amelyik 1-hez vagy 89-hez ér, elindul újra körbe. Ami érdekes, hogy bármilyen kiindulási szám esetén előbb utóbb az 1-hez vagy a 89-hez jutunk. A kérdés: tízmillió alatt hány olyan szám van, amelyik 89-hez ér?
Forrás: Project Euler.
Aknakereső
Írd meg azt az algoritmust, amely az aknakeresőben felfedi a pálya aknák nélküli részét! Egy két dimenziós pályán néhány akna van elszórva. A felhasználó szabadon léphet bármelyik mezőre. Ha aknára lép, veszít; ha nem, akkor megmutatjuk neki, hogy a választott mező mellett hány másik mező tartalmaz aknát (0 és 8 között). Ha 0, akkor a szomszédos mezők egyike sem tartalmaz aknát, vagyis azokra biztonságosan lehet lépni; ha azoknál is valamelyik mezőre 0 adódik, természetesen még tovább, arra is. Készíts függvényt, amely egy összefüggő, akna nélküli területet teljesen felderít!
Tükörszámok
Írj rekurzív programot, amely kilistázza az n számjegyből álló tükörszámokat!
Többféle elvű megoldás is lehetséges. Az egyik érdekes változat az, amikor a sok egymásba ágyazott for ciklust helyettesíti a rekurzió.
Emeletes ház (Dinesman feladata)
Ez a feladat már szerepelt egyszer:
Baker, Cooper, Fletcher, Miller és Smith egy ötemeletes ház különböző emeletein laknak. Baker nem a legfölső emeleten lakik, Cooper pedig nem az alsó szinten. Fletcher lakhelye sem a legalsó szinten van, de nem is a legfölsőn. Miller magasabban lakik, mint Cooper. Smith nem Fletcherrel szomszédos emeleten lakik, ahogy Cooper és Fletcher sem emelet-szomszédok. A kérdés: melyik emelet kié?
Akkor az a tipp szerepelt mellette, hogy az összes lehetőség közül (11111, 11112, 11113 stb.) első körben azokat kell kiszűrni, ahol az öt változó közül van két egyforma.
Oldd meg most másképp a feladatot! Tedd be egy tömbbe az öt különböző számot, amely tömb egyes elemei rendre Baker, Cooper, Fletcher, Miller és Smith emeleteinek számát mutatják. Írj függvényt, amely permutálja a tömböt, és írj olyan függvényt is, amely ellenőrzi a megkötéseket! Írj ezek használatával egy programot, amely megoldja a feladatot!
Bemenet megfordítása
Írj rekurziót használó programot, amely beolvassa a szabványos bemenetén érkező karaktersorozatot, és visszafelé írja ki azt! A program ne használjon tömböket!
Zárójelek párjai
Írj rekurzív programot, amelyik egy nyitó zárójellel kezdődő sztringben megtalálja a zárójel bezáró párját. (A zárójelek (egymásba () lehetnek)) ágyazva.
Írd meg ugyanezt iteratívan is!
Legnagyobb elem, rekurzívan
A maximumkeresés algoritmusa az előadáson is szerepelt, iteratív változatban.
Írd ezt most meg rekurzívan! Ehhez az alábbiakra kell gondolnod:
- Egy elemű tömb maximuma az egyetlen egy elem, ami van benne: ez a báziskritérium.
- Egy tömböt átvevő függvényt meghívható rövidebb tömbrészletre is:
eleje + 1pointerrel rámutatva a második elemre,db - 1elemszámot mutatva neki. - A tömb legnagyobb eleme lehet az első elem, vagy az összes többi elem közül a legnagyobb.
Rendezés közvetlen kiválasztással
Egy tömb rendezve: a legelejére rakjuk a legkisebb elemet, utána rendezzük a tömb fennmaradó részét. Minden iteráció átírható rekurzióvá: írjuk meg a közvetlen kiválasztásos rendezőt rekurzívan!
Három számjegyenkénti felosztás
Írj függvényt, amely a paraméterként kapott pozitív egész számot három számjegyenként csoportosított formában írja ki. Pl.: 16 077 216. Próbáld ki más számokra is: 999, 1000, 12, 0, 1000222!
Tipp
Használj rekurziót! Ez olyan, mintha ezres számrendszerben írnál ki.
Gyors hatványozás
A hatványozás elvégezhető annál gyorsabban is, mintha a kitevőnek megfelelő számú szorzást csinálnánk. Pl. a8=a4·a4, a4=a2·a2 és
a2=a·a miatt a nyolcadikra hatványozáshoz mindössze három szorzásra van szükség.
A következő megfigyelést tehetjük:
ak=(a2)k/2, hakpáros, ésak=a·ak-1, hakpáratlan.
Írj rekurzív függvényt, amely a fentiek alapján végzi el a hatványozást! Paraméterei legyenek az alap és a kitevő, visszatérési értéke pedig a hatvány. Írd ki kettő első tizenhat hatványát!
Hanoi tornyai – lépés sorszáma
A rekurziós előadáson volt szó a Hanoi tornyai feladatról. Ott szerepel egy megoldás, amely kiírja, mikor melyik korongot kell áthelyezni. Módosítsd azt a programot úgy, hogy beszámozza a lépéseket! (Ha esetleg globális változóra gondolnál, meg lehet oldani anélkül is!)
Hanoi tornyai – grafikusan
Írd át úgy a Hanoi tornyai programot, hogy valamilyen grafikus könyvtár segítségével (pl. SDL) ki is rajzolja a cseréket!
Járda kövezése
Hányféleppen lehet egy adott hosszúságú járdát kikövezni 1 és 2 méter hosszúságú járdalapokkal? Például ha 3 méteres a járda, a lehetőségek: 1+1+1, 1+2, 2+1, tehát összesen 3. Listázzuk ki az összes megoldási lehetőséget! (A feladat egyszerűbb változata: csak a megoldások darabszámát kell kiírni.)
Pénzváltás I.
Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot?
Pénzváltás II.
Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot? Listázzuk ki az összes megoldási lehetőséget!
Faktoriális – a kiértékelés megjelenítése
A rekurzív faktoriális függvény (n*(n-1)!) kiértékelését egy ilyen rajzzal lehet szemléltetni:
fakt(3)
fakt(2)
fakt(1)
fakt(0)
1
1*1
1
2*1
2
3*2
6
Módosítsd úgy a rekurzív faktoriális függvényt (maradjon is rekurzív), hogy egy ehhez hasonló rajzot készítsen a program kimenetén!