Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PYMERG - Python: Scalanie

logo


Witajcie! Jest to kolejny z serii tutoriali uczący Pythona, a w przyszłości być może nawet Cythona i Numby. Jeśli chcesz nauczyć się nowych, zaawansowanych konstrukcji to spróbuj rozwiązać kilka następnych zadań. Powodzenia! 


Zadanie

Sortowanie jest fundamentalnym problemem w informatyce. W tym zadaniu nauczysz się prostej metody sortowania. Co więcej, w kolejnym zadaniu będziesz testować wadliwe implementacje sortowania. Motywem przewodnim w kolejnych kilku zadaniach jest testowanie prostych ale błędnych implementacji algorytmów. Najpierw nauczysz się jak rozwiązać dany problem, a później będziesz testował rozwiązania innych.



Najpierw proste wyjaśnienie w jaki sposób odbywa się sortowanie:

1. Początkowe dzielenie

Na początku posiadamy listę bliżej nieokreślonych elementów. Elementy nie mają żadnego porządku. Kolejny etap będzie potrzebował uporządkowanych list. Zastosujemy więc prosty zabieg: stworzymy listę pojedynczych elementów. Dla przykładu:

.

2. Scalanie 

Dwie uporządkowane listy możemy scalić w jedną, także uporządkowaną. Zasada jest prosta: Wybieramy mniejszy element na początku obu list, wyjmujemy go i przenosimy na koniec wynikowej listy. Dla przykładu:

.

3. Podziel i zwyciężaj

Powyższe dwie metody wykorzystamy do zaimplementowania sortowania. Na początku, dzielimy początkową listę na listę pojedynczych elementów. Następnie parami scalamy listy. Powstanie w ten sposób dwa razy mniej list o dwa razy więcej elementach. Ponownie scalamy parami listy. Ponownie, powstanie dwa razy mniej list. Na samym końcu pozostanie tylko jedna lista. Dla przykładu:

.

4. Testowanie

Twoim zadaniem jest zaimplementować funkcje o nazwach divide, merge i sorting. Pobierz szablon kodu, po uzupełnieniu odeślij jako zgłoszenie. Szablon zawiera doklejony kod, który sam pobierze dane wejściowe i wypisze dane wyjściowe. Musisz jedynie zaimplementować trzy metody.

.

Przykładowe dane oraz wyniki są dostępne do pobrania.

 


Dodane przez:Arkadiusz Bulski
Data dodania:2015-02-22
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:PYTHON PYPY
Pochodzenie::)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.