„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 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]] | |||
}} | }} | ||