ID: 2673
Algorytmy
Łatwe
Źródło: Arkusze CKE
Technika konstruowania algorytmu polegająca na rozbiciu na dwa lub więcej mniejszych podproblemów, aż do momentu, gdy ich części będą wystarczająco proste do bezpośredniego rozwiązania, nosi nazwę:
Warianty odpowiedzi
-
A
komiwojażera
-
B
najkrótszej trasy
-
C
dziel i zwyciężaj
-
D
heurystycznej
Wyjaśnienie
Kiedy dostajesz w pracy ogromny projekt, który wydaje się nie do ogarnięcia, najlepszą strategią jest rozbicie go na kilka mniejszych, łatwiejszych modułów.
Dokładnie tę samą ideę stosujemy w programowaniu pod nazwą dziel i zwyciężaj (ang. divide and conquer).
Algorytm najpierw dzieli duży problem na mniejsze podproblemy tego samego typu. Dzielenie następuje tak długo, aż kawałki staną się na tyle proste, że można je bezpośrednio rozwiązać.
Na koniec wyniki tych małych zadań są łączone w jedno kompletne rozwiązanie. Ta technika stoi u podstaw m.in. sortowania szybkiego (Quicksort) czy sortowania przez scalanie (Merge sort).