„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
| 84. sor: | 84. sor: | ||
}} | }} | ||
===6. Feladat=== | ===6. Feladat (Van megoldás)=== | ||
Adott egy <math> n </math> hosszú tömb. Tudjuk, hogy a tömb első néhány (<math> k </math> darab) elem 0, a többi 1, de <math> k </math> értékét nem ismerjük. Adjon <math> O(logk) </math> (nem <math> O(logn) </math> )<sup>1</sup> összehasonlítást használó algoritmust, ami meghatározza <math> k </math> értékét. | |||
''<sup>1</sup> A feladatban <math> O(logk) </math> szerepel, de az csak elgépelés.'' | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Először nézzük meg, hogy az első 2 elem <math>0-1</math>-e, ha igen, akkor <math> k=1 </math>. | |||
*Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen <math> m </math>), ha pedig túl lépnénk a tömböt ezzel, akkor az utolsóba. | |||
*Vizsgáljuk meg, hogy "hol vagyunk": ''(az aktuális cellát, és a 2 szomszédját)'' | |||
**Ha <math>0-0-0</math>-t látunk, akkor ugrunk megint 2x akkorát ''(ugyanazzal a kritériummal, mint előbb)''. | |||
**Ha <math>0-0-1</math>-t látunk, akkor <math> k=m </math>. | |||
**Ha <math>0-1-1</math>-t látunk, akkor <math> k=m-1 </math>. | |||
**Ha <math>1-1-1</math>-t látunk, akkor egy bináris keresés segítségével<sup><big>(1)</big></sup> a 2 legutóbbi vizsgált elem közötti cellákban megkeressük a <math>0-1-1</math>, vagy <math>0-0-1</math> felállást, és a <math>k</math> értékét a látottak alapján beállítjuk <math>( k=m-1 </math> vagy <math> k=m )</math>. | |||
<sup><big>(1)</big></sup> '' Ha <math>0-0-0</math>-t lát, jobbra lép, ha <math>1-1-1</math>-t, akkor balra, másik 2 esetben pedig találatunk van.'' | |||
:::::::::::[[File:algel_pzh_2013tavasz_6_1.PNG|400px]] | |||
*Az algoritmus működése alapján belátható, hogy <math> O(logk) </math> időben fut. | |||
}} | }} | ||