Strona główna » Algorytmy » Artykuły » Kłopotliwy Most
 

Kłopotliwy Most

Zagadka

Przez stary most chciała przejść czwórka przyjaciół. Niestety na moście mogą jednocześnie znaleźć się dwie osoby, więc nie mogą przejść wszyscy równocześnie. Dodatkowym utrudnieniem jest fakt, że jest ciemno, a mają tylko jedną pochodnie. Bez niej przejście przez dziurawy most jest niebezpieczne. Każdy z przyjaciół przechodzi most w jedną stronę w innym czasie 1 min., 2 min., 7 min. oraz 8 min. W jakim najkrótszym czasie przyjaciele znajdą się po drugiej stronie mostu? Zakładamy, że dwie osoby w parze idą tempem osoby wolniejszej.

Rozwiązanie

Odpowiedź to 15 min.

Analiza zadania

Większość osób uzyskuje odpowiedź 19 min. Wydaje się, że strategia, która polega na przeprowadzeniu wszystkich po kolei przy pomocy najszybszej osoby jest najskuteczniejsza. Nie jest to jednak metoda najskuteczniejsza, ponieważ osoby w parze idą zawsze tempem tej wolniejszej.

Z tego powodu najważniejsze, aby w parze osoby różniły się jak najmniej czasem przechodzenia przez most. Jednak czy możliwe jest, aby przez most przeszły razem osoby o czasach przejścia 7 min. i 8min.? Tak, ale najpierw muszą odpowiednio przejść osoby z czasami 1 min. i 2 min. Najpierw to właśnie oni przekraczają most, a potem osoba z czasem 1 min. wraca po pozostałe, ale przekazuje pochodnie i czeka, aż tamci przekroczą i wróci po nią osoba, która przechodzi w 2 min., a potem przechodzą razem. Kolejne kroki przedstawia poniższa tabelka:

Lewy brzegNa mościeCzasPrawy brzeg
1, 2, 7, 8---
7, 8>> 1, 2 >>2-
7, 8<< 1 <<12
1>> 7, 8 >>82
1<< 2 <<27, 8
->> 1, 2 >>27, 8
---1, 2, 7, 8

Łączny czas przejścia to 2 + 1 + 8 + 2 + 2 czyli 15 min.

Implementacja

Spróbujmy zaimplementować teraz poznaną technikę do rozwiązania zadania. Program musi być jednak przygotowany na dowolną ilość osób, więc rozpatrzmy możliwe przypadki. Dla jednej oraz dwóch osób program ma zawsze zwrócić wiekszą wartość. Dla trzech osób sprawdzi się technika "najszybszego człowieka", a dla czterech poznana technika. Dla większej ilości osób możemy powtarzać scenariusz z zadania. Najszybsza osoba przynosi z powrotem pochodnie i druga najszybsza później przyprowadza tamtą z powrotem. Jednak może się zdarzyć, że po lewej stronie brzegu zostanie nieparzysta ilość osób. Jednak przeprowadzając po dwie osoby przypadek zostanie uproszczony do ewentualnej jednej osoby po lewej stronie. Jednak wtedy wystarczy wysłać po nią najszybszą osobę.

Powyższe rozumowanie przeprowadza poniższa funkcja podajCzas(), która dla podanej tablicy tab, która zawiera czasy przejścia poszczególnych osób zwraca najkrótszy czas w jakim mogą one przejść przez most. Zakładamy, że czasy są posortowane rosnąco.

C++
C#
  1. int podajCzas(int* tab, int n) {
  2.   if (n == 1) return tab[0];
  3.   if (n == 2) return tab[1];
  4.   int czas = tab[1];
  5.   for (int i = 0; i < (n - 2) / 2; i++) {
  6.     czas += tab[0];
  7.     czas += tab[n - 1 - i * 2];
  8.     czas += tab[1] + tab[1];
  9.   }
  10.   if (n % 2 == 1)
  11.     czas += tab[0] + tab[2];
  12.   return czas;
  13. }

Na początek rozpatrzmy (2. - 3.) trywialne przypadki. Jeśli jednak osób jest więcej niż dwie to przechodzimy do obliczania czasu. Na początek zawsze (4.) dwie najszybsze osoby przechodzą na drugą stronę mostu. Potem (5. - 9.) symulujemy przeprowadzanie kolejnych par najwolniejszych osób. Na koniec (10.) trzeba pamiętać o tym, że na koniec może zostać jedna osoba. Wtedy (11.) przeprowadzamy ją dzięki najszybszej osobie. Potem (12.) zwracamy łączny czas.

Testowanie funkcji

W celu przetestowania napisanej funkcji można posłużyć się poniższym fragmentem kodu, który wczyta od użytkownika potrzebne dane do obliczeń:

C++
C#
  1. int main () {
  2.   int n;
  3.   cout << "Podaj ile jest osob:\n n = ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj czasy przechodzenia przez most osob (rosnaco):\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   int w = podajCzas(tab, n);
  10.   cout << "Osoby moga przejsc w " << w << " min." << endl;
  11.   system("pause");
  12.   return 0;
  13. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1