Algoritmuselmélet - PPZH, 2013.05.23.

A VIK Wikiből
A lap korábbi változatát látod, amilyen Rohamcsiga (vitalap | szerkesztései) 2014. május 25., 21:57-kor történt szerkesztése után volt. (→‎2. Feladat (Van megoldás))
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)


2013.05.23 - PPZH megoldásai

1. Feladat (Van megoldás)

Tudjuk, hogy az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f(n), g(n) : \textsc{N} \rightarrow \textsc{N} } függvényekre igaz, hogy és Lehetséges-e, hogy:

(a)

(b)

(Ez két, egymástól függetlenül megválaszolandó kérdés.)

Megoldás

a)

  • Ha
  • Akkor igaz az, hogy:
    • És az is, hogy
  • Tehát lehetséges.

b)

  • Ha
  • Akkor igaz az, hogy:
    • És az is, hogy
  • Tehát lehetséges.

2. Feladat (Van megoldás)

Távmunkában fogunk dolgozni mostantól n napon át. Nem kell minden nap bejárnunk, de at alábbi három feltételt be kell tartanunk:

  • két egymást követő benti munkanap között legfeljebb k nap telhet elm
  • az n nap során legfeljebb egyszer maradhatunk pontosan k napig távol,
  • az első és a n. napon be kell mennünk.

Sajnos a kék metróval járunk dolgozni, ami hol jár, hol nem, de szerencsére megjósolták nekünk, hogy a kötvetkező n napoban mely napokon lesz üzemzavar, ezeken a napokon nem akarunk dolgozni menni (az első és az utolsó napon nem lesz üzemzavar). Adjon algoritmust, ami a jóslás eredmények ismeretében O(nk) lépésben meghatározza, hogy legkevesebb hány bemenéssel tudjuk megúszni ezt az n munkanapot.

Megoldás

A megoldást először a 2. feltétel figyelembevétele nélkül írom le, anélkül sokkal egyszerűbb.

Vegyünk fel egy n méretű tömböt. Ennek az i-edik eleme legyen az a szám, ahány napot muszáj bent lennünk, ha az i. napon be akarunk menni.

Ha az i. napon üzemzavar van, akkor a tömb i-edik eleme legyen végtelen. Ha nincs üzemzavar, akkor legyen a tömb előző legfeljebb k elemének a minimuma plusz egy (amikor az előző k elemet nézzük, ott k-1 kihagyást engedünk meg).

Pl, ha n = 7, k = 3, és a 2. és az 5. napon lesz üzemzavar:

nap 1 2 3 4 5 6 7
érték 1 végtelen 2 2 3 végtelen 3

A második feltétel figyelembevételéhez egy két soros táblázattá kell bővítenünk a tömböt. A második sorába tároljuk azt, hogy hány napot kötelező bent lennünk, ha az i. napon bent vagyunk, és kihasználjuk azt is, hogy egyszer pontosan k napot is lehetünk távol. Ennek az értéke vagy végtelen, vagy a minimuma két lehetőségnek:

  • Ha most használtuk fel a k napos lógást, akkor k+1 nappal ezelőtti, első sorbeli elem + 1.
  • Ha már korábban felhasználtuk a k napos lógást, akkor az előző k napban nézzük a második sor elemeinek a minimumát + 1.

Pl, ha n = 7, k = 2, és az 5. és a 6. napon lesz üzemzavar:

nap 1 2 3 4 5 6 7
első sor 1 2 2 3 végtelen végtelen végtelen
második sor 1 2 2 2 végtelen végtelen 4
Az eredmény természetesen a második sor n-edik eleme. Az algoritmus O(n*k) lefut, hiszen 2*n mezőre kell k elem minimumát kiválasztani, ami - feltéve, hogy két elem minimimuma egy lépés - 2*n*k lépést jelent ami = O(n*k)

3. Feladat

TODO

Megoldás
TODO

4. Feladat

TODO

Megoldás
TODO

5. Feladat (Van megoldás)

Egy kupac elemeit preorder bejárás szerint kiolvasva az alábbi számsorozatot kapjuk: Rekonstruálható-e ebből a kupac?

Megoldás
  • A kupac egy teljes bináris fa, így tudjuk, hogy mi a fa alakja.
  • Nincs is más dolgunk, mint felrajzolni, majd a preorder bejárás alapján beírni az elemeket a megfelelő csúcsokba, és ellenőrizni, hogy sérül-e valahol a kupac adatszerkezet egy tulajdonsága.
  • Látszik, hogy minden rendben van, így a kupac rekonstruálható.

6. Feladat

TODO

Megoldás
TODO

7. Feladat

TODO

Megoldás
TODO

8. Feladat

TODO

Megoldás
TODO