За полвека программисты обнаружили, что многие алгоритмы основаны на схожих концептах, хотя и используются для решения разных проблем. Получается, основных методов проектирования алгоритмов относительно немного. Некоторые из них мы охватим в задачах, а пока расскажем о наиболее распространённых. Последующие примеры можно будет категоризировать по методологии проектирования.
Для демонстрации мы рассмотрим очень простую ситуацию, с которой может столкнуться едва ли не каждый обладатель беспроводного домашнего телефона.
Метод полного перебора
Алгоритм, использующий полный перебор (также этот метод называют исчерпывающий поиск или метод «грубой силы»), рассматривает все возможные варианты и находит определенное решение. Если бы вы искали телефон по такому алгоритму, то игнорировали бы звонок и проверяли бы каждый квадратный сантиметр вашего дома. Вряд ли вы бы успели взять трубку, — иначе вашей удаче можно позавидовать, — но исчерпывающий поиск гарантирует, что рано или поздно вы найдете телефон, где бы он ни был.
BruteForceChange — это алгоритм «грубой силы». Наши задачи включают несколько дополнительных примеров таких алгоритмов. Они самые легкие с точки зрения проектирования, но слишком медленные для решения более серьёзных задач, нежели самых маленьких. Мы советуем или избегать алгоритмов «грубой силы» или находить решения, которые ускоряют их работу.
Метод ветвей и границ
Если рассмотреть варианты, предложенные алгоритмом «грубой силы», мы увидим, что многие из них можно опустить. Эта техника называется методом ветвей и границ.
Представьте, что вы прочёсываете первый этаж и слышите, как над вами звонит телефон. Значит, на первом этаже и в подвале можно больше не искать — и вы сэкономили себе время.
Хотя алгоритмы полного перебора и не подходят для построения эффективных алгоритмов, мы рекомендуем использовать их для стресс-тестирования — техники поиска ошибок в алгоритмах, подробнее о которой мы поговорим в параграфе 4.3.
Итак, параграф позади! Впереди вас ждут первые задачи. Но прежде чем приступить к ним, советуем сперва взглянуть на небольшой гайд о том, как пользоваться системой проверки заданий.