Metody programowania / Ćwiczenia 5

Ćwiczenia z programowania zachłannego

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}