ID: 2623
Algorytmy
Łatwe
Źródło: Arkusze CKE
Strategia budowania algorytmu poprzez podział na dwa lub więcej mniejszych podproblemów tak długo, aż fragmentu staną się proste do bezpośredniego rozwiązania jest metodą:
Warianty odpowiedzi
-
A
heurystyczną
-
B
najkrótszej ścieżki
-
C
dziel i zwyciężaj
-
D
komiwojażera
Wyjaśnienie
Podejście "dziel i zwyciężaj" (ang. divide and conquer) polega na rozbijaniu skomplikowanego, dużego problemu na mniejsze, łatwiejsze do opanowania fragmenty.
W praktyce algorytm dzieli dane na pół, potem te połówki znowu na pół, aż dojdzie do elementów tak prostych, że odpowiedź staje się oczywista. Następnie wyniki cząstkowe są ze sobą łączone w jedno rozwiązanie końcowe.
To dokładnie tak, jak przy porządkowaniu wielkiego magazynu – łatwiej posprzątać osobno każdą półkę niż cały obiekt naraz. Doskonałym przykładem tej strategii w kodzie jest sortowanie przez scalanie (Merge Sort) oraz sortowanie szybkie (Quick Sort).