Metody programowania / Ćwiczenia 6: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 8: | Linia 8: | ||
==Zadanie 1 (Odcinki)== | ==Zadanie 1 (Odcinki)== | ||
Dana jest tablica 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"> | ||
| Linia 95: | Linia 95: | ||
{{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? | ||
</div> | |||
</div> | |||
}} | |||
==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. | |||
{{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]. Licząc B[i,j], jeśli A[i,j] jest zerem, 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]. | |||
</div> | |||
</div> | |||
}} | |||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
function MaksKwadrat(N: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 | |||
var i,j,maks,r,bok : integer; | |||
B : array [1..N,1..M] of integer; | |||
begin | |||
for i:=1 to N do //wypełniamy pierwszy wiersz tablicy B | |||
if A[i,1]=0 then B[i,1]:=1 | |||
else B[i,1]:=0; | |||
for j:=1 to M do //wypełniamy pierwszą kolumnę tablicy B | |||
if A[1,j]=0 then B[1,j]:=1 | |||
else B[1,j]:=0; | |||
maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | |||
for j:=2 to M 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] | |||
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 A[i-r,j-r]=0 then bok:=r+1 | |||
else bok:=r | |||
else bok:=min(B[i-1,j], r)+1; | |||
B[i,j]:=bok; | |||
if bok > maks then maks:=bok; | |||
end | |||
else B[i,j]:=0; //jeśli A[i,j] <> 0 wtedy B[i,j]=0 | |||
MaksKwadrat:=maks; | |||
end | |||
''Koszt czasowy'': liniowy względem N×M. | |||
''Koszt pamięciowy'': liniowy względem N×M. | |||
</div> | |||
</div> | |||
}} | |||
{{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 [1..N] of integer. | |||
</div> | |||
</div> | |||
}} | |||
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
function MaksKwadrat2(N: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 | |||
var i,j,maks,r,bok : integer; | |||
B : array [1..N] of integer; | |||
begin | |||
for i:=1 to N do //wypełniamy tablicę B zgodnie z pierwszym wierszem A | |||
if A[i,1]=0 then B[i]:=1 | |||
else B[i]:=0; | |||
maks:=0; //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu | |||
for j:=2 to M do begin | |||
stareB:=B[1]; | |||
if A[1,j]=0 then B[1]:=1 | |||
else B[1]:=0; | |||
for i:=2 to N do | |||
if A[i,j]=0 then begin //jeśli A[i,j]=0 to wartośc B[i] zależy od stareB i B[i] | |||
r:=B[i]; | |||
if stareB=r then //jeśli stareB=r to trzeba zbadać A[i-r,j-r] | |||
if A[i-r,j-r]=0 then bok:=r+1 | |||
else bok:=r | |||
else bok:=min(stareB, r)+1; | |||
B[i]:=bok; | |||
stareB:=r; | |||
if bok > maks then maks:=bok; | |||
end | |||
else B[i]:=0; //jeśli A[i,j] <> 0 wtedy B[i]=0 | |||
MaksKwadrat2:=maks; | |||
end | |||
''Koszt czasowy'': liniowy względem N×M. | |||
''Koszt pamięciowy'': liniowy względem N. | |||
</div> | |||
</div> | |||
}} | |||
==Zadanie 3 (Prostokąt)== | |||
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"> | |||
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]. Licząc B[i,j], jeśli A[i,j] jest zerem, 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]. | |||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
Wersja z 08:56, 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 rozmiar (długość boku) największego kwadratu w tej tablicy składającego się z samych zer.
Wskazówka 1
{{{3}}}
