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. int budujPiramide(vector<int> elementy) {
2.   if (elementy.size() == 0)
3.     return 0;
4.   sort(elementy.begin(), elementy.end());
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.size()) {
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. int main () {
2.   int n, t;
3.   cout << "Ile elementow?\n n = ";
4.   cin >> n;
5.   cout << "Podaj szerokosci elementow:\n";
6.   vector<int> lista;
7.   while (n--) {
8.     cin >> t;
9.     lista.push_back(t);
10.   }
11.   int wynik = budujPiramide(lista);
12.   cout << "Mozliwych poziomow: " << wynik;
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja