Ответы пользователя по тегу Дискретная математика
  • Правильноли решена данная задача?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Неправильно. Правильный ответ 36212176000.

    Почему у вас в ответе перемешаны C и A? Какой физический смысл?

    Ответ C(2,20)*C(3,18)*c(3,15)*c(3,12)*...*C(3,3)/6!

    Смысл - берем 2 любых вопроса, которые не попадают в 18 из билетов. Потом берем три из 18, которые идут в первый билет, потом 3 из оставшихся 15, которые идут во второй билет... и так далее. В конце делим на 6!, потому что порядок билетов, похоже, не имеет значения.
    Ответ написан
  • Как объяснит задачу по комбинаторике?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вы сначала выбираете ту тему, которую выучат 2 студента. Она ото всех остальных явно отличается же. Это 11 вариантов. Это первый множитель 11 в ответе.

    Потом, все варианты различаются тем, какие 2 студента эту тему выучат. Это множитель С(2,6).

    Далее, эти 2 студента должны выучить еще по одной теме. Это выбрать 2 темы из оставшихся 10-ти. Но тут порядок важен, ведь это разные темы у разных студентов. Это множитель A(10,2).

    Что осталось? 8 не выученных тем и 4 студента. Тут есть известная формула обобщенных сочетаний или сочетаний из нескольких цветов (не помню точное название). Всего таких комбинаций будет 8!/(2!*2!*2!*2!). Эту же формулу можно получить если последовательно выбирать по 2 темы для каждого из четырех студентов. Первый может взять темы C(2,8) вариантами. Второй из оставшихся 6-ти тем C(2,6) вариантами и аналогично для третьего и четвертого студентов (C(2,4) и C(2,2)).
    Ответ написан
  • Сколько чисел в шестеричной системе счисления, которые не имеют одинаковых цифр?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Ответ:
    sum(i=0..15) 15!*15/i!

    Очевидно, длина не может быть больше 16 символов.

    Дальше, переберем длину числа. Пусть это L. Должны быть L разных цифр. Но есть проблема - первая цифра не может быть 0. Подсчитаем отдельно варианты, где 0 вообще нет, и где 0 есть. В первом случае есть 15!/(15-L)!/L! вариантов выбрать L цифр из 1-15. И надо домножить на L!, ведь их можно перемешивать как угодно. Во втором варианте мы берем 0 и L-1 цифр из 1-15 - это 15!/(15-(L-1))!/(L-1)! вариантов. Надо домножить на (L-1) возможных позиций 0 и (L-1)! возможных перестановок всех остальных цифр. Поскольку без 0 можно получить, только если длина меньше 16, случай с L=16 выделим отдельно.

    Итого - ответ:
    sum(L=1..15) {15!/(15-L)! + 15!/(16-L)!*(L-1)} + 15!*15

    Немного посокращав можно упростить того, что я привел в начале:
    sum(i=0..15) 15!*15/i!

    В общем виде для N-чной системы счисления надо вместо 15 записать N-1.

    Можете проверить, что формула работает для N=2: 1!*1(1/0!+1/1!) = 1*2 = 2 ("10" и "1").
    И N=3: 2!*2*(1/0!+1/1!+1/2!) = 4*(1+1+1/2) = 10 ("1", "2", "10", "20", "12", "21", "120", "210", "102", "201")
    Ответ написан
  • В каком месте программисту реально понадобиться знания дискретной математике?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если пишите что-то посложнее формочек, то может и пригодится.

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

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

    Конечные автоматы - это очень удобный инструмент для организации нетривиальной логики, а поиск кратчайшего пути - довольно частая задача в игростроении. Вообще, игродел требует математики.

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

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

    А уж если вы разработчик компилятора или какого-нибудь медиа кодека, то там дискретка лезет из всех щелей (теория языков, формальные парсеры, дискретное преобразование Фурье).
    Ответ написан