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

A VIK Wikiből
Arklur (vitalap | szerkesztései)
Arklur (vitalap | szerkesztései)
9. sor: 9. sor:
}}
}}


===2. Feladat===
===2. Feladat (Van megoldás)===
Egy <math> A[i,j] </math>   <math>n</math> x <math>n</math>-es táblázat minden mezőjében egy egész szám van írva (nem feltétlenül csak pozitívak). Adjon <math> O(n^2) </math> lépésszámú algoritmust, ami eldönti, hogy melyik az a téglalap alakú része a táblázatnak, melynek bal felső sarka egybe esik a nagy táblázat bal felső sarkával és benne az elemek összege az egyik legnagyobb.  
Egy <math> A[i,j] </math> <math>n</math> x <math>n</math>-es táblázat minden mezőjében egy egész szám van írva (nem feltétlenül csak pozitívak). Adjon <math> O(n^2) </math> lépésszámú algoritmust, ami eldönti, hogy melyik az a téglalap alakú része a táblázatnak, melynek bal felső sarka egybe esik a nagy táblázat bal felső sarkával és benne az elemek összege az egyik legnagyobb.  


(Vagyis olyan <math>k, l</math>-t keresünk, amire <math> \sum_{i \leq k, j \leq l}A[i,j] </math> maximális.)
(Vagyis olyan <math>k, l</math>-t keresünk, amire <math> \sum_{i \leq k, j \leq l}A[i,j] </math> maximális.)
17. sor: 17. sor:
|szöveg=
|szöveg=


<math> T </math>
{{Rejtett
|mutatott=<big>''Megjegyzések a feladathoz''</big>
|szöveg=
 
*Ahogy az többször is segít, úgy most is, hogy felrajzolunk magunknak egy 3x3, vagy 4x4-es táblázatot, és nézegetjük, hogyan kéne dolgozni...
*A feladatban 1-1 lépésnek vettem:
**1 művelet (<math> +,- </math>) elvégzését ''(vagyis a <math> B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] </math> 3 lépés).''
**1 értéke beírása a cellába.
**1 összehasonlítás (és esetleges cserék).


}}
*Adott az <math> A </math> mátrix.
*Létrehozunk egy <math> B </math> mátrixot (szintén <math>n</math> x <math>n</math>-es).''(ez <math>\Rightarrow O(n^2)</math> lépés)''
*<math> B[1,1]:= A[1,1]</math>. ''(ez <math>\Rightarrow 1 </math> lépés)''
*<math> k=l=1 </math> és <math> aktmax=B[1,1] </math>.
*Először kitöltjük az 1. sort <math> \rightarrow  B[i,1]:=B[i-1,1]+A[i,1], i=2 \dots n  </math>. ''(ez <math>\Rightarrow 2(n-1)=O(n)</math> lépés)''
*Majd kitöltjük az 1. oszlopot <math> \rightarrow  B[1,i]:=B[1,i-1]+A[1,i], i=2 \dots n  </math>. ''(ez <math>\Rightarrow 2(n-1)=O(n)</math> lépés)''
*Minden további cellában pedig <math> B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] </math>. ''(ez <math>\Rightarrow 4(n-1)(n-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 </math> és <math> 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.
:::::::::::::::::[[File:A_B_matrix.PNG|400px]]


}}
}}

A lap 2013. június 13., 16:35-kori változata

2013.04.03. ZH megoldásai

1. Feladat

TODO

Megoldás
TODO

2. Feladat (Van megoldás)

Egy É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 A[i,j] } É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 n} x É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 n} -es táblázat minden mezőjében egy egész szám van írva (nem feltétlenül csak pozitívak). Adjon É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 O(n^2) } lépésszámú algoritmust, ami eldönti, hogy melyik az a téglalap alakú része a táblázatnak, melynek bal felső sarka egybe esik a nagy táblázat bal felső sarkával és benne az elemek összege az egyik legnagyobb.

(Vagyis olyan É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 k, l} -t keresünk, amire É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 \sum_{i \leq k, j \leq l}A[i,j] } maximális.)

Megoldás
Megjegyzések a feladathoz
  • Ahogy az többször is segít, úgy most is, hogy felrajzolunk magunknak egy 3x3, vagy 4x4-es táblázatot, és nézegetjük, hogyan kéne dolgozni...
  • A feladatban 1-1 lépésnek vettem:
    • 1 művelet (É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 +,- } ) elvégzését (vagyis a É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 B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] } 3 lépés).
    • 1 értéke beírása a cellába.
    • 1 összehasonlítás (és esetleges cserék).
  • Adott 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 A } mátrix.
  • Létrehozunk egy É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 B } mátrixot (szintén É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 n} x É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 n} -es).(ez É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 \Rightarrow O(n^2)} lépés)
  • É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 B[1,1]:= A[1,1]} . (ez É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 \Rightarrow 1 } lépés)
  • É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 k=l=1 } és É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 aktmax=B[1,1] } .
  • Először kitöltjük az 1. sort É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 \rightarrow B[i,1]:=B[i-1,1]+A[i,1], i=2 \dots n } . (ez É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 \Rightarrow 2(n-1)=O(n)} lépés)
  • Majd kitöltjük az 1. oszlopot É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 \rightarrow B[1,i]:=B[1,i-1]+A[1,i], i=2 \dots n } . (ez É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 \Rightarrow 2(n-1)=O(n)} lépés)
  • Minden további cellában pedig É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 B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] } . (ez É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 \Rightarrow 4(n-1)(n-1)=O(n^2)} lépés)
  • A keresett É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 k,l } párost pedig folyamat nyilván tartjuk: ha É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 B[i,j] \geq aktmax \Rightarrow k=i, l=j } és É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 aktmax = B[i,j] } . (ez É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 \Rightarrow n^2-1=O(n^2)} lépés)
  • É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 1+2O(n)+ 3O(n^2)=O(n^2)} lépésszámú algoritmusunk van, tehát jók vagyunk.
  • Fájl:A B matrix.PNG

    3. Feladat (Van megoldás)

    Kaphatjuk-e az 1,7,3,6,11,15,22,17,14,12,9 számsorozatot úgy, hogy egy (a szokásos rendezést használó) bináris keresőfában tárolt elemeket posztorder sorrendben kiolvasunk?

    Megoldás
    Megjegyzés a feladathoz
    • Szokásos rendezést használó bináris keresőfa: É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 bal(x) < x < jobb(x)}
    • Postorder:
      • Rekurzívan É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 bal(x) \rightarrow jobb(x) \rightarrow x } . Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.
      • Egyik fontos tulajdonsága, hogy a gyökér az mindig a (figyelt) lista végén van.
  • Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...).
  • A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) (a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista). Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy É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 < < < ... < < > > ... > > = } , vagyis nem állhat fel olyan helyzet, hogy É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 ... < > < ...=} vagy É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 ... > < > ...=} .
    • Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. (Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)
    • A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának.
    • A 3. sorban 14 lesz a gyökér, így a 14-est felrajzoljuk a 12-es jobb fiának.
    • A 4. sorban a 17 lesz a gyökér, így ez a 14-es jobb fia lesz. A 15 és 22 pedig értelemszerűen a bal, és jobb fia lesz 17-nek.
    • 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 É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 < > < } sorrend van, ebből következik, hogy ilyen fa nem létezhet.
  • Fájl:Post tabla.png Fájl:Graf.png

    4. Feladat

    TODO

    Megoldás
    TODO

    5. Feladat

    TODO

    Megoldás
    TODO

    6. Feladat

    TODO

    Megoldás
    TODO

    7. Feladat

    TODO

    Megoldás
    TODO

    8. Feladat

    TODO

    Megoldás
    TODO