Metody programowania / Ćwiczenia 6: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Zadania na kwadrat i prostokąt |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
Zadania z programowania dynamicznego. | Zadania z programowania dynamicznego. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
Oglądaj wskazówki i rozwiązania __SHOWALL__<br> | Oglądaj wskazówki i rozwiązania __SHOWALL__<br> | ||
Ukryj wskazówki i rozwiązania __HIDEALL__ | Ukryj wskazówki i rozwiązania __HIDEALL__ | ||
</div> | </div> | ||
==Zadanie 1 (Odcinki)== | ==Zadanie 1 (Odcinki)== | ||
Dana jest tablica A zawierająca posortowane rosnąco liczby rzeczywiste oznaczające współrzędne punktów na prostej. Oblicz maksymalną sumę długości rozłącznych odcinków (tzn. nie stykających się nawet końcami), które można otrzymać łącząc wybrane sąsiednie punkty. Nie ma obowiązku użycia wszystkich punktów i nie wolno zmieniać zawartości tablicy. | Dana jest tablica A zawierająca posortowane rosnąco liczby rzeczywiste oznaczające współrzędne punktów na prostej. Oblicz maksymalną sumę długości rozłącznych odcinków (tzn. nie stykających się nawet końcami), które można otrzymać łącząc wybrane sąsiednie punkty. Nie ma obowiązku użycia wszystkich punktów i nie wolno zmieniać zawartości tablicy. | ||
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Przeglądaj A od lewej od prawej, pamiętając dwie liczby: najlepszą sumę używającą ostatniego punktu i najlepszą sumę nieużywającą ostatniego punktu. | Przeglądaj A od lewej od prawej, pamiętając dwie liczby: najlepszą sumę używającą ostatniego punktu i najlepszą sumę nieużywającą ostatniego punktu. | ||
| Linia 15: | Linia 15: | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
function Odcinki(N:integer; var A:array[1..N] of real) : real; | '''function''' Odcinki(N:integer; '''var''' A:'''array'''[1..N] '''of''' real) : real; | ||
// N>=0; A posortowana | // N>=0; A posortowana | ||
var i : integer; | '''var''' i : integer; | ||
zost, bezost, zost_pom, bezost_pom : real; | zost, bezost, zost_pom, bezost_pom : real; | ||
begin | '''begin''' | ||
zost:=0; | zost:=0; | ||
bezost:=0; | bezost:=0; | ||
// zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu i-1 | // zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu i-1 | ||
for i:=2 to N do begin | '''for''' i:=2 '''to''' N '''do''' '''begin''' | ||
bezost_pom:=max(zost,bezost); | bezost_pom:=max(zost,bezost); | ||
zost_pom:=bezost+A[i]-A[i-1]; | zost_pom:=bezost+A[i]-A[i-1]; | ||
| Linia 32: | Linia 32: | ||
bezost:=bezost_pom; | bezost:=bezost_pom; | ||
zost:=zost_pom; | zost:=zost_pom; | ||
end; | '''end'''; | ||
// zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu N | // zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu N | ||
// wystarczy wybrać tą większą | // wystarczy wybrać tą większą | ||
Odcinki:=max(zost,bezost); | Odcinki:=max(zost,bezost); | ||
end // Odcinki | '''end''' // Odcinki | ||
''Koszt czasowy'': liniowy względem N. | |||
''Koszt pamięciowy'': stały | ''Koszt pamięciowy'': stały | ||
''Poprawność rozwiązania'': poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów: | ''Poprawność rozwiązania'': poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów: | ||
bezost[1]=0 | bezost[1]=0 | ||
zost[1]=0 | zost[1]=0 | ||
bezost[i]=max(zost[i-1],bezost[i-1]) | bezost[i]=max(zost[i-1],bezost[i-1]) | ||
zost[i]=bezost[i-1]+A[i]-A[i-1] | zost[i]=bezost[i-1]+A[i]-A[i-1] | ||
gdzie bezost[i] (odp. zost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], nieblokujących (odp. blokujących) punkt A[i]. Istotnie jeśli chcemy mieć największą sumę odcinków nieblokujących i to można wziąć albo blokujące i-1 albo nieblokujące. Jeśli chcemy największą sumę odcinków blokujących i, to do największej sumy odcinków nieblokujących i-1 należy dodać długość odcinka z i-1 do i. Wartości początkowe są oczywiście poprawne (budząca wątpliwość wartość zost[1] nie jest istotna, bo w następnej operacji zost[1] występuje tylko w wyrażeniu max(zost[1],bezost[1]), więc jego wartość 0 niczego nie popsuje). | gdzie bezost[i] (odp. zost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], nieblokujących (odp. blokujących) punkt A[i]. Istotnie jeśli chcemy mieć największą sumę odcinków nieblokujących i to można wziąć albo blokujące i-1 albo nieblokujące. Jeśli chcemy największą sumę odcinków blokujących i, to do największej sumy odcinków nieblokujących i-1 należy dodać długość odcinka z i-1 do i. Wartości początkowe są oczywiście poprawne (budząca wątpliwość wartość zost[1] nie jest istotna, bo w następnej operacji zost[1] występuje tylko w wyrażeniu max(zost[1],bezost[1]), więc jego wartość 0 niczego nie popsuje). | ||
Ponieważ, jak widać ze wzorów do obliczenia wartości dla i wystarczy pamiętać wartości dla i-1, rezygnujemy z pamiętania całych tablic zost i bezost. | Ponieważ, jak widać ze wzorów do obliczenia wartości dla i wystarczy pamiętać wartości dla i-1, rezygnujemy z pamiętania całych tablic zost i bezost. | ||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
function Odcinki2(N:integer; var A:array[1..N] of real) : real; | '''function''' Odcinki2(N:integer; '''var''' A:'''array'''[1..N] '''of''' real) : real; | ||
// N>=0; A posortowana | // N>=0; A posortowana | ||
var i : integer; | '''var''' i : integer; | ||
mozezost, bezost, mozezost_pom, bezost_pom : real; | mozezost, bezost, mozezost_pom, bezost_pom : real; | ||
begin | '''begin''' | ||
mozezost:=0; | mozezost:=0; | ||
bezost:=0; | bezost:=0; | ||
// mozezost i bezost oznaczaja maksymalna sumę dlugosci odcinków | // mozezost i bezost oznaczaja maksymalna sumę dlugosci odcinków | ||
// mogących i niemogących blokować punkt i-1 | // mogących i niemogących blokować punkt i-1 | ||
for i:=2 to N do begin | '''for''' i:=2 '''to''' N '''do''' '''begin''' | ||
bezost_pom:=mozezost; | bezost_pom:=mozezost; | ||
mozezost_pom:=max(bezost+A[i]-A[i-1],mozezost); | mozezost_pom:=max(bezost+A[i]-A[i-1],mozezost); | ||
| Linia 73: | Linia 73: | ||
bezost:=bezost_pom; | bezost:=bezost_pom; | ||
mozezost:=mozezost_pom; | mozezost:=mozezost_pom; | ||
end; | '''end'''; | ||
Odcinki2:=mozezost; | Odcinki2:=mozezost; | ||
end // Odcinki2 | '''end''' // Odcinki2 | ||
''Koszt czasowy'': liniowy względem <math>N</math>. | ''Koszt czasowy'': liniowy względem <math>N</math>. | ||
''Koszt pamięciowy'': stały | ''Koszt pamięciowy'': stały | ||
''Poprawność rozwiązania'': poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów: | ''Poprawność rozwiązania'': poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów: | ||
bezost[1]=0 | bezost[1]=0 | ||
mozezost[1]=0 | mozezost[1]=0 | ||
bezost[i]=mozezost[i-1] | bezost[i]=mozezost[i-1] | ||
mozezost[i]=max(bezost[i-1]+A[i]-A[i-1],mozezost[i-1]) | mozezost[i]=max(bezost[i-1]+A[i]-A[i-1],mozezost[i-1]) | ||
gdzie bezost[i] (odp. mozezost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], które nie mogą blokować (odp. mogą blokować) punkt A[i]. W tym rozwiązaniu pozbywamy się wątpliwości związanych z zost[1]. | gdzie bezost[i] (odp. mozezost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], które nie mogą blokować (odp. mogą blokować) punkt A[i]. W tym rozwiązaniu pozbywamy się wątpliwości związanych z zost[1]. | ||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
{{cwiczenie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{cwiczenie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Jak zmodyfikować nasz program, aby zamiast liczenia maksymalnej sumy, wypisywał ciąg odcinków o maksymalnej sumie? | Jak zmodyfikować nasz program, aby zamiast liczenia maksymalnej sumy, wypisywał ciąg odcinków o maksymalnej sumie? | ||
| Linia 98: | Linia 98: | ||
</div> | </div> | ||
}} | }} | ||
==Zadanie 2 (Kwadrat)== | ==Zadanie 2 (Kwadrat)== | ||
Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz rozmiar (długość boku) największego kwadratu w tej tablicy składającego się z samych zer. | Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz rozmiar (długość boku) największego kwadratu w tej tablicy składającego się z samych zer. | ||
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
W pomocniczej tablicy B tego samego typu trzymamy rozmiary największych kwadratów składających się z zer o prawym dolnym rogu w A[i,j]. Jeśli A[i,j]=0 to licząc B[i,j] patrzymy na B[i-1,j] i B[i,j-1] (oczywiście uważając na brzegi). W przypadku gdy B[i-1,j]=B[i, j-1]=r trzeba jeszcze zbadać A[i-r,j-r]. | W pomocniczej tablicy B tego samego typu trzymamy rozmiary największych kwadratów składających się z zer o prawym dolnym rogu w A[i,j]. Jeśli A[i,j]=0 to licząc B[i,j] patrzymy na B[i-1,j] i B[i,j-1] (oczywiście uważając na brzegi). W przypadku gdy B[i-1,j]=B[i, j-1]=r trzeba jeszcze zbadać A[i-r,j-r]. | ||
| Linia 107: | Linia 107: | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
function MaksKwadrat(N,M:integer; var A:array[1..N,1..M] of integer) : integer; | '''function''' MaksKwadrat(N,M:integer; '''var''' A:'''array'''[1..N,1..M] '''of''' integer) : integer; | ||
// N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer | // N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer | ||
var i,j,maks,r,bok : integer; | '''var''' i,j,maks,r,bok : integer; | ||
B : array [1..N,1..M] of integer; | B : '''array''' [1..N,1..M] '''of''' integer; | ||
begin | '''begin''' | ||
maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | ||
for i:=1 to N do //wypełniamy pierwszy wiersz tablicy B | '''for''' i:=1 '''to''' N '''do''' //wypełniamy pierwszy wiersz tablicy B | ||
if A[i,1]=0 then begin | '''if''' A[i,1]=0 '''then''' '''begin''' | ||
B[i,1]:=1 | B[i,1]:=1 | ||
maks:=1; | maks:=1; | ||
end | '''end''' | ||
else B[i,1]:=0; | '''else''' B[i,1]:=0; | ||
for j:=1 to M do //wypełniamy pierwszą kolumnę tablicy B | '''for''' j:=1 '''to''' M '''do''' //wypełniamy pierwszą kolumnę tablicy B | ||
if A[1,j]=0 then begin | '''if''' A[1,j]=0 '''then''' '''begin''' | ||
B[1,j]:=1 | B[1,j]:=1 | ||
maks:=1; | maks:=1; | ||
end | '''end''' | ||
else B[1,j]:=0; | '''else''' B[1,j]:=0; | ||
for j:=2 to M do | '''for''' j:=2 '''to''' M '''do''' | ||
for i:=2 to N do | '''for''' i:=2 '''to''' N '''do''' | ||
if A[i,j]=0 then begin //jeśli A[i,j]=0 to wartośc B[i,j] zależy od B[i-1,j] i B[i,j-1] | '''if''' A[i,j]=0 '''then''' '''begin''' //jeśli A[i,j]=0 to wartośc B[i,j] zależy od B[i-1,j] i B[i,j-1] | ||
r:=B[i,j-1]; | r:=B[i,j-1]; | ||
if B[i-1,j]=r then //jeśli B[i-1,j]=B[i,j-1] to trzeba zbadać A[i-r,j-r] | '''if''' B[i-1,j]=r '''then''' //jeśli B[i-1,j]=B[i,j-1] to trzeba zbadać A[i-r,j-r] | ||
if A[i-r,j-r]=0 then bok:=r+1 | '''if''' A[i-r,j-r]=0 '''then''' bok:=r+1 | ||
else bok:=r | '''else''' bok:=r | ||
else bok:=min(B[i-1,j], r)+1; | '''else''' bok:=min(B[i-1,j], r)+1; | ||
B[i,j]:=bok; | B[i,j]:=bok; | ||
if bok > maks then maks:=bok; | '''if''' bok > maks '''then''' maks:=bok; | ||
end | '''end''' | ||
else B[i,j]:=0; //jeśli A[i,j] <> 0 wtedy B[i,j]=0 | '''else''' B[i,j]:=0; //jeśli A[i,j] <> 0 wtedy B[i,j]=0 | ||
MaksKwadrat:=maks; | MaksKwadrat:=maks; | ||
end | '''end''' | ||
''Koszt czasowy'': liniowy względem N×M. | ''Koszt czasowy'': liniowy względem N×M. | ||
''Koszt pamięciowy'': liniowy względem N×M. | ''Koszt pamięciowy'': liniowy względem N×M. | ||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Ponieważ nidgy nie sięgamy więcej niż o jeden wiersz w górę (i nigdy w prawo) wystarczy pomocnicza tablica B typu array [0..N] of integer (gdzie B[0]=0). | Ponieważ nidgy nie sięgamy więcej niż o jeden wiersz w górę (i nigdy w prawo) wystarczy pomocnicza tablica B typu array [0..N] of integer (gdzie B[0]=0). | ||
| Linia 155: | Linia 155: | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
function MaksKwadrat2(N,M:integer; var A:array[1..N,1..M] of integer) : integer; | '''function''' MaksKwadrat2(N,M:integer; '''var''' A:'''array'''[1..N,1..M] '''of''' integer) : integer; | ||
// N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer | // N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer | ||
var i,j,maks,r,bok,stareB : integer; | '''var''' i,j,maks,r,bok,stareB : integer; | ||
B : array [0..N] of integer; | B : '''array''' [0..N] '''of''' integer; | ||
begin | '''begin''' | ||
maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | ||
B[0]:=0; | B[0]:=0; | ||
for i:=1 to N do //wypełniamy tablicę B zgodnie z pierwszym wierszem A | '''for''' i:=1 '''to''' N '''do''' //wypełniamy tablicę B zgodnie z pierwszym wierszem A | ||
if A[i,1]=0 then begin | '''if''' A[i,1]=0 '''then''' '''begin''' | ||
B[i]:=1 | B[i]:=1 | ||
maks:=1; | maks:=1; | ||
end | '''end''' | ||
else B[i]:=0; | '''else''' B[i]:=0; | ||
for j:=2 to M do //przechodzimy po kolejnych wierszach | '''for''' j:=2 '''to''' M '''do''' //przechodzimy po kolejnych wierszach | ||
for i:=1 to N do //przechodzimy po kolejnych kolumnach | '''for''' i:=1 '''to''' N '''do''' //przechodzimy po kolejnych kolumnach | ||
if A[i,j]=0 then begin //jeśli A[i,j]=0 to wartośc B[i] zależy od B[i-1] i B[i] | '''if''' A[i,j]=0 '''then''' '''begin''' //jeśli A[i,j]=0 to wartośc B[i] zależy od B[i-1] i B[i] | ||
r:=B[i]; | r:=B[i]; | ||
if B[i-1]=r then //jeśli B[i-1]=r to trzeba zbadać A[i-r,j-r] | '''if''' B[i-1]=r '''then''' //jeśli B[i-1]=r to trzeba zbadać A[i-r,j-r] | ||
if A[i-r,j-r]=0 then bok:=r+1 | '''if''' A[i-r,j-r]=0 '''then''' bok:=r+1 | ||
else bok:=r | '''else''' bok:=r | ||
else bok:=min(B[i-1], r)+1; | '''else''' bok:=min(B[i-1], r)+1; | ||
B[i]:=bok; | B[i]:=bok; | ||
if bok > maks then maks:=bok; | '''if''' bok > maks '''then''' maks:=bok; | ||
end | '''end''' | ||
else B[i]:=0; //jeśli A[i,j] <> 0 wtedy B[i]=0 | '''else''' B[i]:=0; //jeśli A[i,j] <> 0 wtedy B[i]=0 | ||
MaksKwadrat2:=maks; | MaksKwadrat2:=maks; | ||
end | '''end''' | ||
''Koszt czasowy'': liniowy względem N×M. | ''Koszt czasowy'': liniowy względem N×M. | ||
''Koszt pamięciowy'': liniowy względem N. | ''Koszt pamięciowy'': liniowy względem N. | ||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
==Zadanie 3 (Prostokąt)== | ==Zadanie 3 (Prostokąt)== | ||
Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz maksymalne pole prostokąta składającego się z samych zer w tej tablicy. | Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz maksymalne pole prostokąta składającego się z samych zer w tej tablicy. | ||
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Ponieważ prostokątów zaczepionych prawym dolnym rogiem w danym polu może być dużo i nie bardzo wiadomo który z nich zapamiętać, rozwiązanie zadania z kwadratami nie przenosi sie bezpośrednio na zadanie o prostokątach. | Ponieważ prostokątów zaczepionych prawym dolnym rogiem w danym polu może być dużo i nie bardzo wiadomo który z nich zapamiętać, rozwiązanie zadania z kwadratami nie przenosi sie bezpośrednio na zadanie o prostokątach. | ||
| Linia 200: | Linia 200: | ||
</div> | </div> | ||
}} | }} | ||
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
W pomocniczej tablicy B należy trzymać wysokość najdłuższego słupka zer w A o dolnym końcu w A[i,j]. W celu obliczenia maksymalnego pola prostokąta zaczepionego w A[i,j] należy przechodzić tablicę B indeksem r od prawej do lewej zaczynając od i, i obliczać maksymalne pola prostokątów o podstawie A[i-r,j] A[i,j]. | W pomocniczej tablicy B należy trzymać wysokość najdłuższego słupka zer w A o dolnym końcu w A[i,j]. W celu obliczenia maksymalnego pola prostokąta zaczepionego w A[i,j] należy przechodzić tablicę B indeksem r od prawej do lewej zaczynając od i, i obliczać maksymalne pola prostokątów o podstawie A[i-r,j] A[i,j]. | ||
Podobnie jak w zadaniu o kwadratach wystarczy do tego liniowa dodatkowa pamięć. | Podobnie jak w zadaniu o kwadratach wystarczy do tego liniowa dodatkowa pamięć. | ||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
function MaksProstokąt(N,M:integer; var A:array[1..N,1..M] of integer) : integer; | '''function''' MaksProstokąt(N,M:integer; '''var''' A:'''array'''[1..N,1..M] '''of''' integer) : integer; | ||
// N, M >=0; szukamy maksymalnego pola prostokąta w A składającego się z samych zer | // N, M >=0; szukamy maksymalnego pola prostokąta w A składającego się z samych zer | ||
var i,j,maks,r,podstawa,wysokośc,pole, : integer; | '''var''' i,j,maks,r,podstawa,wysokośc,pole, : integer; | ||
B : array [0..N] of integer; | B : '''array''' [0..N] '''of''' integer; | ||
begin | '''begin''' | ||
maks:=0; //na maks będziemy pamiętać maksymalne pole dotychczas napotkanego prostokąta | maks:=0; //na maks będziemy pamiętać maksymalne pole dotychczas napotkanego prostokąta | ||
B[0]:=0; | B[0]:=0; | ||
for i:=1 to N do //wypełniamy tablicę B zgodnie z pierwszym wierszem A | '''for''' i:=1 '''to''' N '''do''' //wypełniamy tablicę B zgodnie z pierwszym wierszem A | ||
if A[i,1]=0 then begin | '''if''' A[i,1]=0 '''then''' '''begin''' | ||
B[i]:=1 | B[i]:=1 | ||
maks:=1; | maks:=1; | ||
end | '''end''' | ||
else B[i]:=0; | '''else''' B[i]:=0; | ||
for j:=2 to M do | '''for''' j:=2 '''to''' M '''do''' | ||
for i:=1 to N do begin | '''for''' i:=1 '''to''' N '''do''' '''begin''' | ||
if A[i,j]=0 then begin //modyfikujemy B[i] | '''if''' A[i,j]=0 '''then''' '''begin''' //modyfikujemy B[i] | ||
B[i]:=B[i]+1; | B[i]:=B[i]+1; | ||
else B[i]:=0; | '''else''' B[i]:=0; | ||
podstawa:=1; //w pętli obliczamy maksymalne pole prostokąta zaczepionego prawym dolnym | podstawa:=1; //w pętli obliczamy maksymalne pole prostokąta zaczepionego prawym dolnym | ||
wysokość:=B[i]; //rogiem w A[i,j] | wysokość:=B[i]; //rogiem w A[i,j] | ||
pole:=B[i]; | pole:=B[i]; | ||
r:=i-1; ; | r:=i-1; ; | ||
while B[r] <> 0 do begin //nie przekroczymy zakresu tablicy B bo B[0]=0 | '''while''' B[r] <> 0 '''do''' '''begin''' //nie przekroczymy zakresu tablicy B bo B[0]=0 | ||
podstawa:=podstawa+1; | podstawa:=podstawa+1; | ||
wysokość:=min(wysokość, B[r]); | wysokość:=min(wysokość, B[r]); | ||
pole:=max(pole, podstawa*wysokość); | pole:=max(pole, podstawa*wysokość); | ||
end; | '''end'''; | ||
if pole > maks then maks:=pole; | '''if''' pole > maks '''then''' maks:=pole; | ||
end; //for i | '''end'''; //for i | ||
MaksProstokąt:=maks; | MaksProstokąt:=maks; | ||
end | '''end''' | ||
''Koszt czasowy'': liniowy względem N×N×M. | ''Koszt czasowy'': liniowy względem N×N×M. | ||
Wersja z 16:58, 3 paź 2006
Zadania z programowania dynamicznego.
Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__
Zadanie 1 (Odcinki)
Dana jest tablica A zawierająca posortowane rosnąco liczby rzeczywiste oznaczające współrzędne punktów na prostej. Oblicz maksymalną sumę długości rozłącznych odcinków (tzn. nie stykających się nawet końcami), które można otrzymać łącząc wybrane sąsiednie punkty. Nie ma obowiązku użycia wszystkich punktów i nie wolno zmieniać zawartości tablicy.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Rozwiązanie 2
{{{3}}}
Ćwiczenie 1
{{{3}}}
Zadanie 2 (Kwadrat)
Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz rozmiar (długość boku) największego kwadratu w tej tablicy składającego się z samych zer.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Wskazówka 2
{{{3}}}
Rozwiązanie 2
{{{3}}}
Zadanie 3 (Prostokąt)
Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz maksymalne pole prostokąta składającego się z samych zer w tej tablicy.
Wskazówka 1
{{{3}}}
Wskazówka 2
{{{3}}}
Rozwiązanie 1
{{{3}}}
