Ocena brak

Na czym polega metoda algorytmiczna zwana „dziel i zwyciężaj”?

Autor /Barnim7777 Dodano /29.12.2011

Metoda „dziel i zwyciężaj” postępuje zgodnie z zasadą, że jeśli jakiś problem jest za duży by uporać się z nim w całości, to należy spróbować podzielić go na mniejsze części o takiej samej strukturze. Ta metoda algorytmiczna związana jest ściśle z procedurami rekurencyjnymi.

Przykładem wykorzystania metody „dziel i zwyciężaj” jest algorytm sortowania przez scalania. Najpierw dzielimy n -elementową listę wejściową na połowy, potem otrzymane połowy znów na połowy i tak do chwili kiedy nie otrzymamy n pojedynczych elementów. Potem porównujemy ze sobą pary elementów i tworzymy uporządkowane ciągi dwuelementowe, porównujemy ciągi dwuelementowe i tworzymy posortowane ciągi cztero elementowe, i tak do chwili kiedy nie otrzymamy jednej porządkowanej n elementowej listy.

Opis słowny rekurencyjnego algorytmu sortowania przez scalanie:

Procedura SORTUJ LISTĘ L:

1. jeśli lista zawiera 1 element to jest posortowana

2. w przeciwnym razie wykonaj co następuje:

a. podziel listę na L1 i L2

b. wywołaj SORTUJ L1

c. wywołaj SORTUJ L2

d. scal posortowane listy L1 i L2 w jedną posortowaną listę

3. wróć do poziomu wywołania

Podobne prace

Do góry