Recursion & Backtrack
В тази секция ще разгледаме как да решаваме задачи с изчерпване, ползвайки рекурсия и търсене с връщане (backtrack). За някои от задачите ще ви се наложи да измислите оптимизации, за да бъде достатъчно бързо решението ви - например в какъв ред да извиквате под-задачите, кои клони на рекурсията нямат смисъл да бъдат обходени и могат да бъдат "изрязани" (наричано на Английски "pruning"), както и други.Подходяща тема, която можете да прочетете е Рекурсия и търсене с връщане.
Упражняват се лесни до средно-трудни задачи, в които трябва да се имплементира рекурсивно решение. Задачата Schedule с дадените ограничения може да се реши с бектрек, макар че има доста по-добро (полиномиално) решение, което ще разгледаме в секцията Greedy. Задачата Ruler е относително сложна (нужни са няколко оптимизации, за да върви достатъчно бързо дори само да изчислим отговорите локално), като, за съжаление, отговорите могат много лесно да бъдат намерени в интернет.
Unique
36
|
27
Company
45
|
35
Closest Number
27
|
33
Sudoku
5
|
4
Schedule
24
|
9
Orderings
84
|
36
Product
22
|
11
Ruler
6
|
40
Persistence
13
|
29