„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
a (→2. Feladat) |
a (→2. Feladat) |
||
| 9. sor: | 9. sor: | ||
}} | }} | ||
| − | ===2. Feladat=== | + | ===2. Feladat (Van megoldás)=== |
| − | Egy <math> A[i,j] </math> | + | 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> | + | {{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., 15:35-kori változata
Tartalomjegyzék
2013.04.03. ZH megoldásai
1. Feladat
TODO
Megoldás
TODO
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.
(Vagyis olyan [math]k, l[/math]-t keresünk, amire [math] \sum_{i \leq k, j \leq l}A[i,j] [/math] maximális.)
Megoldás
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.
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 ([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).
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
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 [math] \lt \lt \lt ... \lt \lt \gt \gt ... \gt \gt = [/math], vagyis nem állhat fel olyan helyzet, hogy [math] ... \lt \gt \lt ...=[/math] vagy [math] ... \gt \lt \gt ...=[/math].
Megjegyzés a feladathoz
- Szokásos rendezést használó bináris keresőfa: [math]bal(x) \lt x \lt jobb(x)[/math]
- Postorder:
- Rekurzívan [math] bal(x) \rightarrow jobb(x) \rightarrow x [/math]. 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.
- 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 [math] \lt \gt \lt [/math] sorrend van, ebből következik, hogy ilyen fa nem létezhet.
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
