Tanulási útmutató
Összefoglalás
A tananyag vége felé közeledve kitekintünk a továbblépési lehetőségekre. Olyan feladatokat nézünk át, amelyek alapvetően más tantárgyak témakörébe tartoznak, de a Programozási alapismeretek tantárgy eszközkészletével tökéletesen megoldhatóak.
Ebben a leckében segédösszegek kiszámításával gyorsítjuk egy feladat megoldását.
Követelmény
Önállóan megoldható feladatok
Segédösszegek
Egy földműves egy téglalap alakú területet szeretne vásárolni egy NxM-es téglalap alakú földterületen. Tudja minden megvásárolható földdarabról, hogy azt megművelve mennyi lenne a haszna vagy vesztesége.
Adjuk meg azt a téglalapot, amelyen a legnagyobb haszon érhető el!
Bemenet
N,M: Egész
T:Tömb[1..N,1..M:Egész]
Kimenet
P,Q,R,S:Egész
Előfeltétel
–
Utófeltétel
1≤P≤R≤N és 1≤Q≤S≤M és ∀i,j,k,l (1≤i≤k≤N,1≤j≤l≤M): érték(P,Q,R,S)≥érték(i,j,k,l)
érték(a,b,c,d)=SZUM(x=a..c) SZUM(y=b..d) T[x,y]
Az eddigiek alapján az utófeltétel segített a ciklusok meghatározásában. Most ciklust kellene írni i-re, j-re, k-ra, l-re, x-re és y-ra, azaz 6 ciklus lenne egymás belsejében. Ez sok!
Maximum(N,B,Db,T):
P:=1; Q:=1; R:=1; S:=1
Ciklus i=1-től N-ig
Ciklus j=1-től M-ig
Ciklus k=i-től N-ig
Ciklus l=j-től M-ig
Ha érték(i,j,k,l)>érték(P,Q,R,S) akkor P:=i; Q:=j; R:=k; S:=l
Ciklus vége
Ciklus vége
Ciklus vége
Ciklus vége
Eljárás vége.
érték(a,b,c,d):
e:=0
Ciklus x=a-től c-ig
Ciklus y=b-től d-ig
e:=e+T[x,y]
Ciklus vége
Ciklus vége
érték:=e
Függvény vége.
Próbáljunk az előző feladathoz hasonlóan valami részcélt kitűzni: számoljuk ki az (1,1) bal felső (u,v) jobb alsó sarkú téglalapok értékét!
Előkészítés(N,T,E):
Ciklus v=1-től M-ig
x=0
Ciklus u=1-től N-ig
x:=x+T[u,v]; E[u,v]=E[u,v-1]+x
Ciklus vége
Ciklus vége
Eljárás vége.
Definiáljuk E[k,l] segítségével az érték(i,j,k,l)-t!
érték(i,j,k,l)=E[k,l]-E[i-1,l]-E[k,j-1]+E[i-1,j-1]
A módszer neve: kumulatív összegzés.
Maximum(N,T,P,Q,R,S,E):
P:=1; Q:=1; R:=1; S:=1; Maxért:=T[1,1]
Ciklus i=1-től N-ig
Ciklus j=1-től M-ig
Ciklus k=i-től N-ig
Ciklus l=j-től M-ig
Ha E[k,l]-E[i-1,l]-E[k,j-1]+E[i-1,j-1]>Maxért akkor
P:=i; Q:=j; R:=k; S:=l; Maxért:=E[k,l]-E[i-1,l]-E[k,j-1]+E[i-1,j-1]
Elágazás vége
Ciklus vége
Ciklus vége
Ciklus vége
Ciklus vége
Eljárás vége.
Tekintse meg az alábbi animációt, amelyben összefoglaljuk a lecke lényegét!
