Metody programowania / Ćwiczenia 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Zadanie 3 |
||
| Linia 13: | Linia 13: | ||
{{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 Pokrycie(N:integer; A:array[1..N] of real) : integer; | '''function''' Pokrycie(N:integer; A:'''array'''[1..N] '''of''' real) : integer; | ||
var i,j,licznik:integer; | '''var''' i,j,licznik:integer; | ||
koniec:boolean; | koniec:boolean; | ||
begin | '''begin''' | ||
sortuj(N,A); | sortuj(N,A); | ||
licznik:=0; | licznik:=0; | ||
| Linia 22: | Linia 22: | ||
// punkty A[1]..A[i-1] są pokryte za pomocą "licznik" odcinków | // punkty A[1]..A[i-1] są pokryte za pomocą "licznik" odcinków | ||
// punkty A[i]..A[N] są niepokryte | // punkty A[i]..A[N] są niepokryte | ||
while i<=N do begin | '''while''' i<=N '''do''' '''begin''' | ||
licznik:=licznik+1; | licznik:=licznik+1; | ||
j:=i+1; | j:=i+1; | ||
| Linia 28: | Linia 28: | ||
// punkty A[i]..A[j-1] są pokryte przez odcinek [A[i],A[i]+1] | // punkty A[i]..A[j-1] są pokryte przez odcinek [A[i],A[i]+1] | ||
// koniec --> j<=N i A[j]>A[i]+1 | // koniec --> j<=N i A[j]>A[i]+1 | ||
while j<=N and not koniec do begin | '''while''' j<=N '''and''' '''not''' koniec '''do''' '''begin''' | ||
if A[j]<=A[i]+1 then | '''if''' A[j]<=A[i]+1 '''then''' | ||
j:=j+1 | j:=j+1 | ||
else | '''else''' | ||
koniec:=true; | koniec:=true; | ||
end; | '''end'''; | ||
i:=j; | i:=j; | ||
end; | '''end'''; | ||
Pokrycie:=licznik; | Pokrycie:=licznik; | ||
end; | '''end'''; | ||
''Koszt czasowy'': koszt sortowania (<math>N \log N</math>) + | ''Koszt czasowy'': koszt sortowania (<math>N \log N</math>) + koszt liniowy względem <math>N</math>. | ||
''Koszt pamięciowy'': stały | ''Koszt pamięciowy'': stały | ||
| Linia 62: | Linia 62: | ||
==Zadanie 2== | ==Zadanie 2== | ||
Mamy dany zbiór N zajęć (każde zajęcia, mają swój czas rozpoczęcia i zakończenia) oraz nieskończony zbiór sal. Należy zaplanować wszystkie zajęcia | Mamy dany zbiór N zajęć (każde zajęcia, mają swój czas rozpoczęcia i większy od niego czas zakończenia) oraz nieskończony zbiór sal. Należy policzyć najmniejszą liczbę sal potrzebną aby zaplanować wszystkie zajęcia. Oczywiście w danym momencie w jednej sali mogą się odbywać tylko jedne zajęcia. | ||
{{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"> | ||
Minimalna liczba sal równa jest maksymalnej liczbie zajeć odbywających się równolegle w jakimś momencie. | |||
</div> | |||
</div> | |||
}} | |||
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
Aby policzyć maksymalną liczbę zajeć odbywających się równolegle, wystarczy przeglądać kolejne ''wydarzenia'', czyli początki i końce zajęć (zgodnie z mijającym czasem) i kontrolować ile zajęć odbywa się równolegle. | |||
</div> | </div> | ||
</div> | </div> | ||
| Linia 72: | Linia 78: | ||
{{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''' Sale(N:integer; P,K:'''array'''[1..N] '''of''' integer):integer; | |||
var ilesal, maxsal:integer; | // N>=0; P[i]<K[i] dla i=1..N | ||
'''var''' ilesal, maxsal:integer; | |||
pi,ki:integer; | pi,ki:integer; | ||
begin | '''begin''' | ||
sortuj(N,P); | sortuj(N,P); | ||
sortuj(N,K); | sortuj(N,K); | ||
| Linia 82: | Linia 89: | ||
ilesal:=0; | ilesal:=0; | ||
maxsal:=0; | maxsal:=0; | ||
// rozpoczęły się wszystkie zajęcia P[1..pi-1] | // rozpoczęły się wszystkie zajęcia odpowiadające czasom P[1..pi-1] | ||
// zakończyły się wszystkie zajęcia K[1..ki-1] | // zakończyły się wszystkie zajęcia odpowiadające czasom K[1..ki-1] | ||
// aktualnie trwające zajęcia potrzebują ilesal sal | // aktualnie trwające zajęcia potrzebują ilesal sal | ||
// maxsal to max ze wszystkich | // maxsal to max ze wszystkich dotychczasowych wartości ilesal | ||
// przyjmując P[0]=K[0]=- | // przyjmując P[0]=K[0]=-∞ mamy: P[pi-1],K[ki-1]<=P[pi],K[ki] | ||
while pi<=N do begin | '''while''' pi<=N '''do''' '''begin''' | ||
if P[pi]<K[ki] then begin | '''if''' P[pi]<K[ki] '''then''' '''begin''' | ||
ilesal:=ilesal+1; | ilesal:=ilesal+1; | ||
if ilesal>maxsal then maxsal:=ilesal; | '''if''' ilesal>maxsal '''then''' maxsal:=ilesal; | ||
pi:=pi+1; | pi:=pi+1; | ||
end | '''end''' | ||
else begin | '''else''' '''begin''' // P[pi]>=K[ki] | ||
// Tu zakładamy, że w jednej sali mogą się w tej samej chwili zakończyć | |||
// jedne zajęcia i rozpocząć następne. Dlatego jeśli P[pi]=K[ki] | |||
// najpierw rozpatrujemy zakończenie zajęć odpowiadających K[ki]. | |||
ilesal:=ilesal-1; | ilesal:=ilesal-1; | ||
ki:=ki+1; | ki:=ki+1; | ||
end; | '''end'''; | ||
end; | '''end'''; | ||
Sale:=maxsal; | Sale:=maxsal; | ||
end; //Sale | '''end'''; //Sale | ||
''Koszt czasowy'': | ''Koszt czasowy'': koszt sortowania (<math>N \log N</math>) + koszt liniowy względem <math>N</math>. | ||
''Koszt pamięciowy'': stały | |||
''Poprawność rozwiązania'': Oczywistym jest, że nie da się zaplanować zajęć w mniejszej liczbie sal niż maksymalna liczba zajęć odbywająca się równocześnie. Nasz program liczy właśnie tę liczbę. | |||
Program przegląda wydażenia w kolejności ich następowania (jeśli kilka wydarzeń następuje równocześnie, przyjmujemy, że zakończenia zajęć następują przed rozpoczęciami zajęć) i przy każdym obrocie pętli while zmienna ilesal oznacza liczbę zajęć, które trwają w danym momencie. | |||
Za każdym obrotem pętli uaktualnia się też zmienną maxsal, aby miała maksymalną dotychczasową wartość zmiennej ilesal. | |||
Łatwo wyobrazić sobie też przydział sal odpowiadający naszemu programowi. Wolne sale będziemy trzymać w kolejce, na początku wszystkie są wolne. Za każdym razem, gdy obrót pętli while mija początek zajęć, przydzielamy pierwszą salę z kolejki sal wolnych. Gdy kończą się jakieś zajęcia, wstawiamy zwolnioną salę na początek kolejki sal wolnych. Zauważmy, że zgodnie z tą strategią nową salę (taką, która nigdy wcześniej nie była przydzielona) przydzielimy tylko takim zajęciom, które powodują zwiększenie wartości zmiennej maxsal. | |||
</div> | </div> | ||
</div>}} | </div>}} | ||
{{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 koniecznej liczby sal, wypisywał faktyczny przydział sal do zajęć? | |||
</div> | |||
</div> | |||
}} | |||
==Zadanie 3== | |||
Trójramienny dźwig ustawia kontenery na wagonach kolejowych. Wagony są ponumerowane kolejno 1, 2, ... . Na każdym wagonie można postawić co najwyżej jeden kontener. W jednym ruchu dźwig pobiera ze składowiska | |||
trzy kontenery i ustawia je na wagonach o numerach i, i+p oraz i+p+q, albo na wagonach o numerach i, i+q oraz i+p+q (dla pewnych stałych p,q>=1). Dźwig trzeba zaprogramować tak, żeby załadował kontenerami pierwsze n wagonów pociągu (pociąg ma n+p+q wagonów). | |||
Program dźwigu składa się z ciągu instrukcji. Każda z instrukcji opisuje jeden ruch dźwigu. Instrukcja programu ma postać trójki (x,y,z), gdzie 1 < x < y < z < n+p+q, i określa numery wagonów, na które dźwig ma ustawić kontenery. Jeżeli po wykonaniu programu na każdym spośród n pierwszych wagonów pociągu znajduje się dokładnie jeden kontener, to mówimy, że program jest poprawny. | |||
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
Idziemy po kolei od i=1 i jesli i-ty wagon jest wolny to wstawiamy i,i+p,i+p+q (zał. że p<=q) jesli sie da, wpp. i,i+q,i+p+q. To co jest ciekawe to pokazanie, ze zawsze ten drugi ruch jest mozliwy (wystarczy przeanalizowac jaki ruch wczesniejszy moglby zablokowac ruch i,i+q,i+p+q). | |||
</div> | |||
</div> | |||
}} | |||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
</div> | |||
</div> | |||
}} | |||
Wersja z 16:36, 13 sie 2006
Ćwiczenia z programowania zachłannego
Zadanie 1
Podaj algorytm obliczający dla zadanego ciągu liczb rzeczywistych opisujących punkty leżące na prostej, minimalną liczbę jednostkowych domkniętych odcinków na prostej pokrywających wszystkie punkty .
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Zadanie 2
Mamy dany zbiór N zajęć (każde zajęcia, mają swój czas rozpoczęcia i większy od niego czas zakończenia) oraz nieskończony zbiór sal. Należy policzyć najmniejszą liczbę sal potrzebną aby zaplanować wszystkie zajęcia. Oczywiście w danym momencie w jednej sali mogą się odbywać tylko jedne zajęcia.
Wskazówka 1
{{{3}}}
Wskazówka 2
{{{3}}}
Rozwiązanie 1
{{{3}}}
Ćwiczenie 1
{{{3}}}
Zadanie 3
Trójramienny dźwig ustawia kontenery na wagonach kolejowych. Wagony są ponumerowane kolejno 1, 2, ... . Na każdym wagonie można postawić co najwyżej jeden kontener. W jednym ruchu dźwig pobiera ze składowiska trzy kontenery i ustawia je na wagonach o numerach i, i+p oraz i+p+q, albo na wagonach o numerach i, i+q oraz i+p+q (dla pewnych stałych p,q>=1). Dźwig trzeba zaprogramować tak, żeby załadował kontenerami pierwsze n wagonów pociągu (pociąg ma n+p+q wagonów).
Program dźwigu składa się z ciągu instrukcji. Każda z instrukcji opisuje jeden ruch dźwigu. Instrukcja programu ma postać trójki (x,y,z), gdzie 1 < x < y < z < n+p+q, i określa numery wagonów, na które dźwig ma ustawić kontenery. Jeżeli po wykonaniu programu na każdym spośród n pierwszych wagonów pociągu znajduje się dokładnie jeden kontener, to mówimy, że program jest poprawny.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
