Metody programowania / Ćwiczenia 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 69: | Linia 69: | ||
</div> | </div> | ||
}} | }} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | |||
procedure Sale(N:integer; P,K:array[1..N] of integer); | |||
var ilesal, maxsal:integer; | |||
pi,ki:integer; | |||
begin | |||
sortuj(N,P); | |||
sortuj(N,K); | |||
pi:=1; | |||
ki:=1; | |||
ilesal:=0; | |||
maxsal:=0; | |||
// rozpoczęły się wszystkie zajęcia P[1..pi-1] | |||
// zakończyły się wszystkie zajęcia K[1..ki-1] | |||
// aktualnie trwające zajęcia potrzebują ilesal sal | |||
// maxsal to max ze wszystkich przeszłych wartości ilesal | |||
// przyjmując P[0]=K[0]=-infinity mamy: P[pi-1],K[ki-1]<=P[pi],K[ki] | |||
while pi<=N do begin | |||
if P[pi]<K[ki] then begin | |||
ilesal:=ilesal+1; | |||
if ilesal>maxsal then maxsal:=ilesal; | |||
pi:=pi+1; | |||
end | |||
else begin | |||
ilesal:=ilesal-1; | |||
ki:=ki+1; | |||
end; | |||
end; | |||
Sale:=maxsal; | |||
end; //Sale | |||
''Koszt czasowy'': | |||
''Koszt pamięciowy'': | |||
</div> | |||
</div>}} | |||
Wersja z 00:56, 12 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 zakończenia) oraz nieskończony zbiór sal. Należy zaplanować wszystkie zajęcia używając jak najmniejszej liczby sal.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
