Metody programowania / Ćwiczenia 5: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania_/_Ćwiczenia_5&oldid=15730”