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

← Régebbi szerkesztés Újabb szerkesztés →

VizuálisWikiszöveges

@@ 104. sor: / 104. sor: @@
 }}
-===6. Feladat===
+===6. Feladat (Van megoldás)===
-TODO
+Egy tömbben adott <math>n</math> darab 0-tól különböző egész szám (lehetnek negatívak is köztük) és adott egy <math>k</math> egész szám is. Adjon <math>O(n \cdot logn)</math> lépésszámú algoritmust, ami eldönti, hogy melyik az a <math>k</math> elem a tömbben, melyek szorzata maximális.
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
-TODO
+*Első lépésben csökkenő sorrendbe rendezzük az elemeket azok '''abszolút értéke''' szerint. <math> (O(n \cdot logn) </math> pl. összefésüléses rendezéssel. <math>)</math>
+*Vesszük az első <math>k</math> szám szorzatát.
+**Ha ez pozitív, akkor jók vagyunk, nincs más dolgunk. [[File:algel_zh_2013tavasz_6_1.PNG|250px]]
+**Ha ez negatív, akkor kiválasztjuk a listából a legkisebb pozitív <math>(A^+)</math> és negatív <math>(A^-)</math> elemet, a maradék listából pedig a legnagyobb pozitív <math>(B^+)</math> és negatív <math>(B^-)</math> elemet. Most meg kell nézni, hogy mit éri meg lecserélni? A pozitívat negatívra, vagy a negatívat pozitívra?
+***Ha <math> (A^- \cdot B^-) < (A^+ \cdot B^+) </math>, akkor a listából kivesszük <math> A^- </math>-t, és berakjuk <math> B^+ </math>-t
+***Ha <math> (A^+ \cdot B^+) < (A^- \cdot B^-) </math>, akkor a listából kivesszük <math> A^+ </math>-t, és berakjuk <math> B^- </math>-t<br>[[File:algel_zh_2013tavasz_6_2.PNG|500px]]
+***Ha nincs a listában pozitív szám, akkor kivesszük a <math>A^-</math>-t, és berakjuk <math>B^+</math>-t<br>[[File:algel_zh_2013tavasz_6_3.PNG|500px]]
+***Ha nincs az egész listában pozitív szám, akkor a legnagyobb számot akkor kapjuk, ha a <math>k</math> darab utolsó elemet vesszük be.<br>[[File:algel_zh_2013tavasz_6_4.PNG|500px]]
 }}