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. static int ileWiezowcow(int[] lista) {
  2.   if (lista.Length == 0)
  3.     return 0;
  4.   int ile = 1;
  5.   int max = lista[0];
  6.   for (int i = 1; i < lista.Length; 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. static void Main(string[] args) {
  2.   Console.WriteLine("Podaj wysokości wieżowców:");
  3.   string[] dane = Console.ReadLine().Split(' ');
  4.   int[] lista = new int[dane.Length];
  5.   for (int i = 0; i < lista.Length; i++) {
  6.     lista[i] = Convert.ToInt32(dane[i]);
  7.   }
  8.   int wynik = ileWiezowcow(lista);
  9.   Console.WriteLine("Widocznych budynków {0}", wynik);
  10.   Console.ReadKey();
  11. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1