Книга Теоретический минимум по Computer Science. Все что нужно программисту и разработчику, страница 8. Автор книги Владстон Феррейра Фило

Онлайн книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

Страница

Например, суммирование первых пяти нечетных чисел записывается так:

.

Обратите внимание: чтобы получить слагаемые 1, 3, 5, 7 и 9, вместо i последовательно используются числа от 0 до 4 включительно. Следовательно, сумма первых n натуральных чисел составляет:

Когда гениальному математику Гауссу было 10 лет, он устал от суммирования натуральных чисел одного за другим по порядку и нашел такой ловкий прием:

Догадаетесь, каким образом Гаусс это обнаружил? Объяснение приема приведено в приложении II. Давайте посмотрим, как можно его использовать для решения следующей задачи.

Любая пара дней между сегодняшним (день 1) и последним (день 30) допустима при условии, что возвращение будет в тот же день или позже, чем отъезд. Следовательно, 30 пар начинаются с 1-го дня, 29 пар начинаются со 2-го дня, 28 — с 3-го и т. д. И есть всего одна пара, приходящаяся на последний день. Таким образом, 30 + 29 + … + 2 + 1 — общее количество пар, которое нужно рассмотреть. Мы можем записать это как  и использовать удобную формулу Гаусса:

пар.

Кроме того, мы можем решить эту задачу при помощи комбинаций, выбрав 2 дня из 30. Порядок не имеет значения: на более ранний день придется отъезд, на более поздний — возвращение. Таким образом, мы получим . Что-то не то… Дело в том, что мы должны учесть еще и случаи, когда прибытие и отъезд приходятся на одну дату. Так как дней всего 30, следовательно, .

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

Рис. 1.8. Случайное число ^[20]

Сейчас мы применим наши навыки решения комбинаторных задач к вычислению вероятностей. Затем мы узнаем, каким образом различные типы событий используются для решения задач. Наконец, мы увидим, почему азартные игроки проигрываются в пух и прах.

Бросок кубика имеет шесть возможных результатов: 1, 2, 3, 4, 5 и 6. Шансы получить 4, следовательно, составляют . А какова вероятность выпадения нечетного числа? Это может произойти в трех случаях (когда на кубике будет 1, 3 или 5), потому шансы составляют . Вероятность того, что некое событие произойдет, выражается такой формулой:

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

Мы уже убедились, что существует 2²³ = 8 388 608 возможных вариантов состава команды. Вам придется рассчитывать только на себя в одном-единственном случае: если в результате подбрасывания монеты выпадут 23 «решки» подряд. Вероятность такого события равна P(никто) = . Если посмотреть на это с высоты птичьего полета, то вероятность того, что конкретный рейс коммерческой авиакомпании потерпит крушение, составляет порядка 1 из 5 млн.

Страница