Strona główna » Algorytmy » Artykuły » Policz Wieżowce
 

Policz Wieżowce

Zadanie

Dana jest lista wysokości kolejnych wieżowców znajdujących się na wprost patrzącego. Sprawdź ile z nich jest tak naprawdę widocznych tzn. nie zostały przysłonięte przez inne wieżowce. Przyjmujemy, że wieżowiec przysłania inny jeśli jest co najmniej takiej samej wysokości i znajduje się bliżej obserwatora. Pierwszy element określa wysokość najbliższego wieżowca.

Przykład

Kolejne budynki wzdłuż kierunku wzroku obserwatora to {2, 1, 3, 4, 1, 2, 3}. Oto graficzna ilustracja danych:

Ilustracja przykładu

Obserwator widzi jedynie trzy budynki chociaż jest ich siedem. Pierwszy budynek przysłania drugi, ale kolejne dwa są widoczne. Pozostałe zostały zasłonięte przez najwyższy wieżowiec. Rozpatrując podane zadanie z drugiej strony to będzie widać jedynie dwa budynki (3 i 4).

Implementacja

Pierwszy budynek jest zawsze widoczny, a każdy kolejny równej bądź mniejszej wysokości nie będzie widoczny. W przypadku napotkania wyższego wieżowca należy pamiętać o aktualizacji dotychczas maksymalnej wysokości, aby przysłaniał on kolejne budynki. Algorytm ma złożoność liniową O(n).

Oto przykładowa implementacja funkcji ileWiezowcow(), która dla przekazanej tablicy wysokości wieżowców zwraca ile z nich jest widoczna dla obserwatora.

  1. int ileWiezowcow(vector<int> lista) {
  2.   if (lista.size() == 0)
  3.     return 0;
  4.   int ile = 1;
  5.   int max = lista[0];
  6.   for (int i = 1; i < lista.size(); i++) {
  7.     if (lista[i] > max) {
  8.       ile++;
  9.       max = lista[i];
  10.     }
  11.   }
  12.   return ile;
  13. }

Na początku znajduje się wyróżniony przypadek, gdy lista jest pusta. Następnie zmienna ile przechowuję liczbę dotychczas widocznych wieżowców, a max - aktualnie najwyższy wieżowiec, który został napotkany.

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższego fragmentu kodu:

  1. int main () {
  2.   int n, t;
  3.   cout << "Ile elementow ma lista?\n n = ";
  4.   cin >> n;
  5.   vector<int> lista;
  6.   for (int i = 0; i < n; i++) {
  7.     cin >> t;
  8.     lista.push_back(t);
  9.   }
  10.   int wynik = ileWiezowcow(lista);
  11.   cout << "Widocznych bydunkow: " << wynik;
  12.   system("pause");
  13.   return 0;
  14. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1