Простые комбинаторные задачи
Представляем вашему вниманию три задачи, которые можно решить, имея всего лишь знания на уровне 7 класса.
Не секрет, что один из важнейших навыков современного программиста – математическое мышление. Именно строгое и формальное мышление позволяет быстро и четко реализовать алгоритм. При этом важен именно аналитический тип мышления, который совершенно не требует глубоких познаний в математике. В действительности вам совсем не обязательно знать и помнить страшные формулы и теоремы, достаточно баловать себя несложными задачами. Вроде таких:
1. Дети в очереди за шоколадом
Маша, ее младший брат и еще пятеро друзей должны выстроиться в очередь за шоколадом. Вопрос: сколько вариантов различных очередей возможно?
Всего детей в очереди 7. Количество свободных мест для первого ребенка 7, так что первый ребенок может стоять, где угодно. Второму ребенку доступно уже 6 мест, т. к. одно место занято. Третьему ребенку доступно 5 мест и так далее. В итоге получаем 7 * 6 * 5 * 4 * 3 * 2 * 1 = 7! = 5040.
2. Сеньор и мидл
Сколькими способами из 12 молодых программистов можно выбрать сеньора и мидла.
На позицию сеньора можно выбрать любого человека из 12, и выберем одного из 11 оставшихся в мидлы. Получится 12 * 11 = 132.
3. Количество разных слов из букв
Сколько различных слов можно составить из букв proglib? А из proglibio?
Первый вопрос очень похож на первую задачу, только вместо детей буквы. Заметим что в слове proglib 7 букв, так что количество перестановок будет 7! = 5040. В слове proglibio 9 букв, так что ответ очевидно 9!, не так ли? Не совсем. в слове proglibio буквы i и o повторяются дважды. То есть мы берем в расчет еще и случаи, когда одинаковые буквы меняются местами, но слово то от этого не меняется. Каждая перестановка двух одинаковых букв увеличивает количество комбинации в два раза. Поэтому за каждый такой случай нам нужно поделить итоговый ответ на два. В итоге получится 9!/2 * 2 = 9! / 4 = 90720.
Напишите в комментариях, какие задачи вы бы хотели увидеть на сайте. Из какой области математики и какой сложности.