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

• Kod źródłowy Implementacja