Metody programowania / Ćwiczenia 5

To są ćwiczenia z programowania zachłannego

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Zadanie 1 (Pokrycie punktów odcinkami jednostkowymi)

Podaj algorytm obliczający dla zadanego ciągu liczb rzeczywistych $a_1,\dots ,a_n$ opisujących punkty leżące na prostej, minimalną liczbę jednostkowych domkniętych odcinków na prostej pokrywających wszystkie punkty $a_1,\dots ,a_n$.

Wskazówka

Rozwiązanie zachłannie: sortujemy punkty, zaczynamy od najmniejszego, ustawiamy pierwszy odcinek lewym końcem na nim. Następnie dla punktów jeszcze niepokrytych robimy to samo.

Rozwiązanie

function Pokrycie(N:integer; A:array[1..N] of real) : integer;
var i,j,licznik:integer;
  koniec:boolean;
begin
  sortuj(N,A);
  licznik:=0;
  i:=1
  // punkty A[1]..A[i-1] są pokryte za pomocą "licznik" odcinków
  // punkty A[i]..A[N] są niepokryte
  while i<=N do begin
    licznik:=licznik+1;
    j:=i+1;
    koniec:=false;
    // punkty A[i]..A[j-1] są pokryte przez odcinek [A[i],A[i]+1]
    // koniec --> j<=N i A[j]>A[i]+1
    while j<=N and not koniec do begin
      if A[j]<=A[i]+1 then 
        j:=j+1
      else
        koniec:=true;
    end;
    i:=j;     
  end;
  Pokrycie:=licznik;
end;

Koszt czasowy: koszt sortowania ($N\log N$) + koszt liniowy względem $N$.

Koszt pamięciowy: stały

Poprawność rozwiązania: udowodnimy przez indukcję po liczbie punktów w ciągu $a_1,\dots ,a_n$, że każde optymalne rozwiązanie (tj. używające najmniejszej możliwej liczby odcinków) można przerobić na rozwiązanie otrzymane przez nasz algorytm bez zwiększania liczby odcinków.

Jeśli jest 0 punktów, nasz algorytm zachowuje się poprawnie (zwróci wartość 0).

Jeśli punktów jest więcej niż 0, weźmy dowolne optymalne rozwiązanie $R$, niekoniecznie otrzymane przez nasz algorytm.

Weźmy najmniejszy punkt w zadanym ciągu $a_1,\dots ,a_n$. Niech będzie to $a_i$. Punkt ten na pewno jest pokryty przez jakiś odcinek. Jeśli przesuniemy ten odcinek tak, aby jego lewy koniec był równy $a_i$, na pewno nie odkryjemy żadnego punktu, ponieważ nie ma odcinków mniejszych od $a_i$.

Jeśli usuniemy z $R$ odcinek pokrywający $a_i$ (otrzymując $R^{\prime }$), otrzymamy optymalne pokrycie dla ciągu punktów otrzymanego przez usunięcie z ciągu $a_1,\dots ,a_n$ wszystkich punktów pokrytych przez odcinek $[a_i,a_i+1]$. Istotnie $R^{\prime }$ jest optymalnym pokryciem nowego ciągu, gdyż w przeciwnym przypadku, jeśli istniałoby pokrycie $R^{″}$ o mniejszej liczbie odcinków, $R^{″}\cup \{[a_i,a_i+1]\}$ byłoby pokryciem ciągu $a_1,\dots ,a_n$ o mniejszej liczbie odcinków niż $R$.

Zauważmy, że punkty w nowym ciągu odpowiadają dokładnie elementom A[i..N] po pierwszym obrocie zewnętrznej pętli while.

Ponieważ nowy ciąg ma mniej punktów niz ciąg $a_1,\dots ,a_n$, z założenia indukcyjnego odcinki w $R^{\prime }$ możemy poprzesuwać tak, aby otrzymać rozwiązanie zgodne z naszym algorytmem, co łącznie z pierwszym odcinkiem da rozwiązanie dla ciągu $a_1,\dots ,a_n$.

Zadanie 2 (Planowanie zajęć w salach)

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

Minimalna liczba sal równa jest maksymalnej liczbie zajeć odbywających się równolegle w jakimś momencie.

Wskazówka 2

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.

Rozwiązanie

function Sale(N:integer; P,K:array[1..N] of integer):integer;
// N>=0; P[i]<K[i] dla i=1..N
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 odpowiadające czasom P[1..pi-1]
  // zakończyły się wszystkie zajęcia odpowiadające czasom K[1..ki-1]
  // aktualnie trwające zajęcia potrzebują ilesal sal
  // maxsal to max ze wszystkich dotychczasowych wartości ilesal
  // przyjmując P[0]=K[0]=-∞ 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 // 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;
      ki:=ki+1;
    end;
  end;
  Sale:=maxsal;
end; //Sale 
  

Koszt czasowy: koszt sortowania ($N\log N$) + koszt liniowy względem $N$.

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.

Ćwiczenie

Jak zmodyfikować nasz program, aby zamiast liczenia koniecznej liczby sal, wypisywał faktyczny przydział sal do zajęć?

Zadanie 3 (Dźwig)

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

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. Tylko dlaczego to jest dobrze?

Rozwiązanie

procedure Dzwig(n,p,q:integer);
// n,p,q>=1
var i:integer;
  wagony:array[1..n] of boolean;

  function wagon(var j:integer):boolean;
  begin
    if j>n then 
      wagon:=false
    else
      wagon:=wagony[j]
  end //wagon

begin //Dzwig
  for i:=1 to n do wagony[i]:=false;
  if p>q then begin i:=p; p:=q; q:=i end; 
  // teraz p<=q
  for i:=1 to n do begin
    if not wagony[i] then
      if not wagon(i+p) then 
        writeln(i,' ',i+p,' ',i+p+q)
      else
        writeln(i,' ',i+q,' ',i+p+q)
  end
end //Dzwig

Koszt czasowy: koszt liniowy względem n.

Koszt pamięciowy: kozst liniowy względem n.

Poprawność rozwiązania: Należy zauważyć, że jeśli pole i jest wolne, a ruch (i,i+p,i+p+q) jest niemożliwy to (i,i+q,i+p+q) na pewno jest możliwy. Istotnie, zająć pole i+q mógł tylko wcześniejszy ruch (i-p, i-p+q,i+q). Ale skoro pole i jest wolne, więc rozpatrując pole i-p zostałby wybrany ruch (i-p,i,i+q), który zająłby i. Sprzeczność. Zatem o ile i jest wolne jeden z ruchów zaproponowanych przez program jest wykonalny.

Zadanie 4 (Uczta kinomana)

Dany jest zbiór N seansów, z podanymi godzinami rozpoczęcia i zakończenia. Ile maksymalnie seansów może obejrzeć zapalony kinoman, przy założeniu, że seansy zawsze ogląda w całości, nigdy nie ogląda dwóch filmów na raz i dowolnie szybko może przejść z jednego seansu na inny?

Wskazówka

Należy zawsze wybierać te seanse, które najwcześniej się kończą.

Rozwiązanie

function Kinoman(N:integer; S:array[1..N] of record r,z:integer; tytul:string end):integer;
// N>=1
var i,ile:integer;
  cz:real;
begin
  sortZR(N,S); //sortowanie wg z, przy rownych z decyduje r
  ile:=1;
  i:=2;
  cz:=S[1].z;
  // ile to największa liczba filmów, które da się obejrzeć, by ostatni 
  // skończył się w czasie <= cz
  while i<=N do begin
    if cz<=S[i].r then 
    else begin
      // writeln('Kolejny film: ',s,', start: ',r,', koniec: ',z);
      cz:=S[i].z;
      ile:=ile+1;
    end;
    i:=i+1
  end;
  Kinoman:=ile;
end; //Kinoman 

Koszt czasowy: koszt sortowania ($N\log N$) + koszt liniowy względem $N$.

Koszt pamięciowy: stały

Poprawność rozwiązania: Każdy rozkład seansów kinomana można przerobić na zgodny z naszym rozwiązaniem, w taki sposób, żeby liczba seansów nie zmalała. Zauważmy, że jeśli w danym rozkładzie pierwszy seans kończy się później, niż ten wybrany przez algorytm, to można go zastąpić tym wybranym przez algorytm. Poza tym wszystkie seanse, które ominie nasz algorytm (przed wybraniem kolejnego seansu) nie mogą juz być w rozkładzie. Zatem po odrzuceniu tych seansów, dostajemy mniejszy zbiór seansów i przez indukcję pokazujemy, że nasz algorytm da optymalny wynik.

Zadanie 5 (Autostrada)

Jedziesz samochodem po autostradzie. Pełny bak benzyny pozwala na przejechanie n kilometrów. Wzdłuż autostrady rozmieszczonych jest M stacji benzynowych, których rozmieszczenie podane jest w tablicy B (odległośi kolejnych stacji od początku autostrady). Wypisz na których stacjach należy tankować, by przejechać do ostatniej stacji przy jak najmniejszej liczbie postojów na pozostałych stacjach benzynowych.

Można założyć, że odległości stacji od siebie oraz od początku i końca trasy są mniejsze niż n.

Wskazówka

Należy zawsze jechać tak daleko jak się da.

Rozwiązanie

procedure Autostrada(n:real; M:integer; B:array[1..M] of real);
// n>0, M>=0, B posortowane
// zakladając B[0]=0, dla i=1..M mamy B[i]-B[i-1]<=n
var i:integer;
  t:real;
begin
  t:=n;
  i:=1;
  // benzyny wystarczy do t
  while i<=M-1 do begin
    if B[i+1]>t then begin
      writeln('Kolejny postój: ',B[i]);
      t:=B[i]+n;
    end
    i:=i+1;
  end;
  writeln('Koniec: ',B[M]);
end; //Autostrada

Koszt czasowy: koszt liniowy względem M.

Koszt pamięciowy: stały.

Poprawność rozwiązania: Każdy rozkład postojów można zastąpić generowanym przez nasz algorytm bez zwiększania liczby postojów. Jeśli pierwszy planowany postój nie jest najdalszym możliwym, można go przesunąć. Następnie mamy do czynienia z sytuacją analogiczną jak sytuacja wyjściowa, tylko liczba stacji jest mniejsza. Zatem indukcyjnie można pokazać, że nasz algorytm da wynik optymalny.

Ćwiczenie

Jak należy zmienić powyższą procedurę, gdybyśmy zrezygnowali z założenia o dobrym rozmieszczeniu stacji? Procedura powinna wypisywać "Nie da się" lub wskazywać stacje na których należy tankować.

Zadanie 6 (Wbijanie gwoździ)

Na nieskończenie długiej desce leżą nieskończenie cienkie (za to skończone) listewki. Jaka jest minimalna liczba gwoździ potrzebna do przybicia wszystkich listewek do deski? Zakładamy, że gwóźdź wbity w danym miejscu przybija wszystkie listewki przez które przechodzi, również jeśli jest wbity na samym końcu danej listewki. Początki i końce każdej z N listewek dane są w tablicy L rekordów o polach l i p typu real. Ponadto listewki nie moga mieć zerowej długości.

Wskazówka

Należy posortować listewki wg końców i wbijać gwoździe tak daleko jak tylko się da.

Rozwiązanie

function Wbijaj(N:integer; L:array[1..N] of record l,p:real end):integer;
// N>0, dla i=1..N, L[i].l<L[i].p
var i,ile:integer;
  g:real;
begin
  sortujPL(N,L);
  ile:=1;
  g:=L[1].k;
  i:=2;
  // wszystkie listewki, ktore zaczynaja sie przed g sa przybite
  // wszystkie listewki, ktore zaczynaja sie po g nie sa przybite
  while i<=N do begin
    if L[i].l>=g then begin
      ile:=ile+1;
      g:=L[i].p;
    end;
    i:=i+1;
  end
  Wbijaj:=ile;
end;

Koszt czasowy: koszt sortowania ($N\log N$) + koszt liniowy względem $N$.

Koszt pamięciowy: stały

Poprawność rozwiązania: Każdy rozkład gwoździ można przerobić na zgodny z naszym rozwiązaniem, w taki sposób, żeby liczba gwoździ nie zwiększyła się. Istotnie, listwa, którą nasz algorytm wbije jako pierwszą musi być przybita jakimś gwoździem. Ponieważ żadna inna listwa nie kończy się wcześniej można ten gwóźdź przesunąć do końca listwy w prawo. Przybiliśmy w ten sposób wszystkie listwy, które mają z nią część wspólną, więc można je wszystkie usunąć. Pozostałe gwoździe przybijaja pozostałe listwy, a ponieważ jest ich mniej, więc z założenia indukcyjnego rozkład gwoździ można przesunąć tak, by był zgodny z naszym algorytmem.