Metody programowania / Ćwiczenia 5

Ćwiczenia z programowania zachłannego

Zadanie 1

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 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}}}