ID: 2048
Algorytmika
Łatwe
Źródło: Arkusze CKE
Metoda projektowania algorytmów, polegająca na podziale problemu na dwa lub więcej mniejszych podproblemów, tak długo aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania, to
Warianty odpowiedzi
-
A
A. dziel i zwyciężaj
-
B
B. sito Eratostenesa
-
C
C. słowa Fibonacciego
-
D
D. sortowanie przez wybór
Wyjaśnienie
Zasada dziel i zwyciężaj to jedna z absolutnych podstaw w algorytmice. W praktyce chodzi o to, że zamiast męczyć się z jednym ogromnym i skomplikowanym zadaniem, rozbijasz je na mniejsze, identyczne podproblemy.
Robi się to tak długo, aż te małe kawałki staną się banalnie proste do rozwiązania. Gdy już poradzisz sobie z każdym małym elementem, po prostu łączysz ich wyniki w całość i otrzymujesz rozwiązanie głównego problemu.
Dokładnie tak działa na przykład popularne sortowanie przez scalanie (Merge Sort) czy wyszukiwanie binarne. To podejście niezwykle przyspiesza działanie wielu algorytmów.