Strona główna » Algorytmy » Artykuły » Budowanie Piramid
 

Budowanie Piramid

Zadanie

Napisz funkcja, który odpowie na pytanie jak dużą można zbudować piramidę z podanych elementów. Zakładamy, że wszystkie elementy mają tą samą wysokość i różnią się jedynie szerokością. Każdy z kolejnych poziomów musi być szerszy od poprzedniego i składać się z większej ilości elementów (co najmniej o 1 więcej). Do funkcji będzie przekazywana lista szerokości kolejnych elementów.

Przykład

Przykładowo dana jest lista [50, 50, 70, 70, 120, 150]. Maksymalnie można z niej ułożyć piramidę o 3 poziomach tak jak to zostało pokazana na rysunku poniżej:

Przykładowa piramida

W podanej piramidzie można zauważyć, że najniższy poziom można by ułożyć tylko z elementów 70 i 120, ale wtedy nie zostaje spełniony, że na każdym kolejnym poziomie ma być o co najmniej jeden element więcej niż na poprzednim.

Implementacja

Podejście Zachłanne

Zazwyczaj piramida ma szersze elementy jak najniżej, a węższe na samym szczycie. Rozwiązanie zachłanne wykorzystuje ten fakt poprzez posortowanie wprowadzonych elementów po ich szerokości, a następnie ustawia je w kolejnych rzędach. Działanie algorytmu kończy się, gdy wybrane zostaną wszystkie elementy, albo gdy nie można już ułożyć kolejnego poziomu, który spełni podane w poleceniu warunki.

  1. static int budujPiramide(int[] elementy) {
  2.   if (elementy.Length == 0)
  3.     return 0;
  4.   Array.Sort(elementy);
  5.   int ostSzer = 0;
  6.   int ostIlosc = 0;
  7.   int wybor = 0;
  8.   int ile = 0;
  9.   while (true) {
  10.     int terazSzer = 0;
  11.     int terazIlosc = 0;
  12.     while ((terazSzer <= ostSzer || terazIlosc <= ostIlosc) && wybor < elementy.Length) {
  13.       terazSzer += elementy[wybor];
  14.       terazIlosc++;
  15.       wybor++;
  16.     }
  17.     if (terazSzer > ostSzer && terazIlosc > ostIlosc) {
  18.       ostSzer = terazSzer;
  19.       ostIlosc = terazIlosc;
  20.       ile++;
  21.     } else {
  22.       return ile;
  23.     }
  24.   }
  25. }

Funkcja na początku powinna sprawdzić, że zostały podane jakiekolwiek elementy. Jeśli są to w nieskończonej pętli wybierany jest kolejny poziom, który jest szerszy niż poprzedni oraz składa się z większej ilości elementów. Jeśli po zakończeniu wybierania warunki nie są spełnione trzeba wyjść z pętli i zwrócić ile poziomów ma obliczona piramida.

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższego fragmentu kodu:

  1. static void Main(string[] args) {
  2.   Console.WriteLine("Podaj szerokości elementów");
  3.   string[] data = Console.ReadLine().Split(' ');
  4.   int[] lista = new int[data.Length];
  5.   for(int i = 0; i < data.Length; i++)
  6.     lista[i] = Convert.ToInt32(data[i]);
  7.   int wynik = budujPiramide(lista);
  8.   Console.WriteLine("Możliwych poziomów: {0}", wynik);
  9.   Console.ReadKey();
  10. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1