Zadanie o krowach. Napiszmy algorytm, który zwróci prawdę jeśli da się tak ustawić krowy, aby każde dwie z nich były oddalone od siebie o co najmniej k jednostek. Zadanie to daje się rozwiązać zachłannie. Dla pierwszej krowy wybieramy oborę położoną najbardziej na lewo. Następnie usuwamy wszystkie obory, które znajdują się mniej niż k jednostek od tej. Powtarzamy to do momentu, w którym zabraknie nam krów lub miejsc w oborach. Jeśli braknie nam krów to znaczy, że da się tak ułożyć w oborach, aby każde dwie były oddalone od siebie o co najmniej k. Jeśli braknie nam obór, to oznacza że się nie da.
Zadanie o złodzieju. Sprawdzamy czy da się wybrać tak i przedmiotów, aby określony w zadaniu iloraz był większy bądź równy k. Dokonując kolejnych modyfikacji ilorazu, dostajemy następujący wzór (jako I rozumiemy w tym wzorze zbiór wybranych przez złodzieja przedmiotów):
Wzór ten można łatwo sprawdzić. Wybieramy i przedmiotów, których wartość cena - k * waga jest najmniejsza wśród wszystkich przedmiotów. Jeśli suma tych wartości i przedmiotów jest większa lub równa od zera to znaczy że da się wybrać i przedmiotów aby iloczyn sumy cen do sumy wag był większy bądź równy niż k. Jeśli jest mniejsza od zera to nie da się.Zadanie o zabytkach. Sprawdzamy czy po k dniach będzie można wybrać jakiś zabytek, a następnie autostradami przejechać przez kilka innych zabytków i wrócić do pierwszego. To zadanie z tych trzech jest chyba najprostsze. Bierzemy zabytki jako wierzchołki, k pierwszych autostrad jako krawędzie skierowane i sprawdzamy czy tak utworzony graf jest grafem cyklicznym.
Mamy trzy procedury, które w czasie liniowym (czyli bardzo szybko) mówią nam, czy k spełnia określone w zadaniach warunki. W następnej części napiszę, jak na podstawie tych funkcji napisać procedurę, która znajdzie najmniejsze (największe) takie k, które spełnia warunki zadania.
Brak komentarzy:
Prześlij komentarz