VIK Wiki

„Algoritmuselmélet - PPZH, 2013.05.23.” változatai közötti eltérés

← Régebbi szerkesztésÚjabb szerkesztés →
Vizuális
Arklur (vitalap | szerkesztései)
381 szerkesztés
Rohamcsiga (vitalap | szerkesztései)
424 szerkesztés
Nincs szerkesztési összefoglaló
33. sor: 33. sor:
}}
}}


===2. Feladat===
===2. Feladat (Van megoldás) ===
TODO
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.
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
|szöveg=


TODO
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:
 
<table>
<tr>
  <td>nap</td>
  <td>1</td>
  <td>2</td>
  <td>3</td>
  <td>4</td>
  <td>5</td>
  <td>6</td>
  <td>7</td>
</tr>
<tr>
  <td>érték</td>
  <td>1</td>
  <td>végtelen</td>
  <td>2</td>
  <td>2</td>
  <td>3</td>
  <td>végtelen</td>
  <td>4</td>
</tr>
</table>
 
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:
 
<table>
<tr>
  <td>nap</td>
  <td>1</td>
  <td>2</td>
  <td>3</td>
  <td>4</td>
  <td>5</td>
  <td>6</td>
  <td>7</td>
</tr>
<tr>
  <td>első sor</td>
  <td>1</td>
  <td>2</td>
  <td>2</td>
  <td>3</td>
  <td>végtelen</td>
  <td>végtelen</td>
  <td>végtelen</td>
</tr>
<tr>
  <td>második sor</td>
  <td>1</td>
  <td>2</td>
  <td>2</td>
  <td>2</td>
  <td>végtelen</td>
  <td>végtelen</td>
  <td>4</td>
</tr>
</table>
 
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)


}}
}}
A lap eredeti címe: „https://vik.wiki/Algoritmuselmélet_-_PPZH,_2013.05.23.”