„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| (4 közbenső módosítás, amit 3 másik szerkesztő végzett, nincs mutatva) | |||
| 2. sor: | 2. sor: | ||
==2013.04.03. ZH megoldásai== | ==2013.04.03. ZH megoldásai== | ||
===1. Feladat Van megoldás)=== | ===1. Feladat (Van megoldás)=== | ||
Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math> | Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math> | ||
{{Rejtett | {{Rejtett | ||
| 46. sor: | 46. sor: | ||
*A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)'' | *A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)'' | ||
*<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | *<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | ||
:::::::::::::::::[[File: | :::::::::::::::::[[File:Algel zh 2013tavasz A B matrix.PNG|400px]] | ||
}} | }} | ||
| 73. sor: | 73. sor: | ||
**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | **Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Post tabla.png|400px]] [[File:Algel zh 2013tavasz Graf.png|300px]] | ||
}} | }} | ||
| 90. sor: | 90. sor: | ||
**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | **A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | ||
*Így a feladat ezzel meg is oldva. | *Így a feladat ezzel meg is oldva. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Csucs suly.png|300px|G gráf]][[File:Algel zh 2013tavasz El suly.png|400px|F gráf]] | ||
Talán egyszerűbben: mivel 0 az utazási idő (élsúlyok) és bármerre megyünk egy csúcsból, ugyanannyit kell várni, ezért tekinthetjük a csúcsból kimenő élek súlyának a csúcsban töltött időt (A-ból 0, mivel itt nem várakozunk, B-ből nem megyünk tovább...). Így az eredeti gráfon (az élsúlyok beírása után) alkalmazható a Dijkstra algo. | |||
--[[Szerkesztő:Deák Zsolt|Deák Zsolt]] ([[Szerkesztővita:Deák Zsolt|vita]]) 2015. április 8., 12:22 (UTC) | |||
}} | }} | ||
===5. Feladat=== | ===5. Feladat=== | ||
Adjacencia-mátrixával adott n csúcsú, élsúlyozott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya a városok közti távolságot adja meg. (Feltehetjük, hogy a távolságok egészek.) | |||
Adjon egy O(n<sup>6</sup>) lépésszámú algoritmust, ami eldönti, hogy lehetséges-e úgy kiválasztani öt várost, hogy ezektől bármely más város legfeljebb 50 kilométerre van. ''(Ezekbe a városokba lenne érdemes hókoztrókat telepíteni.)'' | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*A megoldáshoz először Floyd algoritmussal páronként meghatározzuk az összes város távolságát, ez O(n<sup>3</sup>).<br> | |||
*A város irányítatlan gráfként van megadva, de ezen könnyen segíthetünk úgy, hogy a jelenlegi élek helyett felveszünk két irányítottat, azonos súllyal. Ez O(n<sup>2</sup>).<br> | |||
*Ezek után brute force módszerrel az összes csúcsötösre ellenőrizzük, hogy azok öten lefedik-e (legfeljebb 50 km-re vannak) az összes várost.<br> | |||
**n<sup>5</sup> városötös van, mindegyikre le kell ellenőrizni, hogy jók-e. Az ellenőrzés során végignézzük, az összes csúcsra (n db.), hogy el lehet-e érni. Ez tehát O(n<sup>5</sup>*n)=O(n<sup>6</sup>).<br> | |||
*Összességében ezért O(n<sup>6</sup>) lépésszámú az algoritmus. | |||
}} | }} | ||
===6. Feladat=== | ===6. Feladat (Van megoldás)=== | ||
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 | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*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]] | |||
}} | }} | ||