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

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.

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ń:

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

• Kod źródłowy Implementacja