Владстон Феррейра Фило

Когда два события не могут произойти одновременно, они несовместные, или взаимоисключающие. Если вам нужно подсчитать вероятность любого из нескольких несовместных событий, просто просуммируйте их индивидуальные вероятности.

Ваш замок защищен пятью башнями. Каждая имеет 20 %-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его?

Вероятность поразить врага равна 0,2 + 0,2 + 0,2 + 0,2 + 0,2 = 1, или 100 %, верно? Неверно! Никогда не суммируйте вероятности независимых событий, не совершайте распространенной ошибки. Вместо этого используйте взаимодополняющие события дважды следующим образом.

• 20 %-ный шанс поразить врага — взаимодополняющий для 80 %-го шанса промахнуться. Вероятность того, что не попадут все башни, составляет 0,85 ≈ 0,33

Мы говорим о рекурсии, когда функция делегирует работу своим клонам.

Кнут Д. Искусство программирования. Т. 1 (The Art of Compu­ter Programming

Если видишь хороший ход — ищи ход получше

Если требуется максимальная производительность, то можно избежать этих дополнительных издержек, переписав рекурсивный алгоритм в чисто итеративной форме

Итеративная стратегия состоит в использовании циклов (например, for и while) для повторения процесса до тех пор, пока не окажется соблюдено некое условие

Полный перебор, он же метод «грубой силы», предполагает перебор всех случаев, которые могут быть решением задачи. Эта стратегия также называется исчерпывающим поиском. Она обычно прямолинейна и незамысловата: даже в том случае, когда вариантов миллиарды, она все равно опирается исключительно на силу, то есть на способность компьютера проверить их все

Эта простота имеет свою цену. Рекурсивные алгоритмы при выполнении порождают многочисленные копии самих себя, создавая дополнительные вычислительные издержки

многократного использования промежуточных результатов называется мемоизацией