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

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

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

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

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

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

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

) разделить задачу на подзадачи;
2) найти верхние и нижние границы каждой подзадачи;
3) сравнить границы подзадач всех ветвей;
4) выбрать самую многообещающую задачу и вернуться к шагу 1

• Клейнберг Дж., Традос Е. Алгоритмы: разработка и применение. СПб.: Питер, 2017.
• Выбор стратегии проектирования алгоритмов (Choosing Algorithm Design Strategy, Shailendra Nigam, см. https://code.energy/nigam).
• Динамическое программирование (Dynamic programming, by Umesh V. Vazirani, см. https://code.energy/vazirani)

Примитивные типы данных — это типы данных со встроенной поддержкой в языке

Такая обработка данных известна под названием LIFO (Last-In, First-Out, «последним пришел, первым вышел»); мы можем удалить только верхний элемент, который был добавлен последним

Очередь работает по принципу организации данных FIFO (First-In, FirstOut, «первый пришел, первый вышел»), потому что первый помещенный в очередь элемент всегда покидает ее первым

insert(n, e) — вставить элемент e в позицию n;
• remove(n) — удалить элемент, находящийся в позиции n;
• get(n) — получить элемент, находящийся в позиции n;
• sort() — отсортировать элементы;
• slice(start, end) — вернуть фрагмент списка, начинающийся с позиции start и заканчивающийся в позиции end;
• reverse() — изменить порядок следования элементов на обратный