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. def budujPiramide(elementy):
2.   if (len(elementy) == 0):
3.     return 0
4.   elementy.sort()
5.   ostSzer, ostIlosc = 0, 0
6.   wybor = 0
7.   ile = 0
8.   while True:
9.     terazSzer, terazIlosc = 0, 0
10.     while ((terazSzer <= ostSzer or terazIlosc <= ostIlosc) and wybor < len(elementy)):
11.       terazSzer += elementy[wybor]
12.       terazIlosc += 1
13.       wybor += 1
14.     if (terazSzer > ostSzer and terazIlosc > ostIlosc):
15.       ostSzer = terazSzer
16.       ostIlosc = terazIlosc
17.       ile += 1
18.     else:
19.       return ile

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. print("Podaj szerokości elementów")
2. lista = [int(x) for x in input().split()]
3. wynik = budujPiramide(lista)
4. print("Możliwych poziomów:", wynik)

• Kod źródłowy Implementacja