Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Комбинаторика - раздел олимпиадного программирования (а так же и раздел математики), где ставится вопрос о подсчете числа вариантов выбора элементов из некоторого, как правило, конечного множества согласно заданным правилам.

В качестве примеров комбинаторных задач могут быть следующие:

  • Сколько различных слов возможно составить из заданного набора букв: "ATBTATBZA"?
  • Сколько вариантов команд из 3х мальчиков и 2х девочек можно составить при наличии 10 мальчиков и 12 девочек?
  • Сколько существует различных счастливых 6-значных билетов с суммой цифр, равной 30?

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

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

Число перестановок N!

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно N! = 1*2*3 ... * (N-1) * N. Заметим, что 0!=1. Для факториала справедлива следующая рекурентная запись: N! = (N-1)!*N.

Например, для N=3 существует всего 6 таких перестановок: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2) и (3 2 1). Число N! называют факториалом и произносят как "Н факториал". В нашем случае как раз получилось 3! = 1*2*3 = 6 различных перестановок.

Число размещений ANK

Под числом размещений понимают количество вариантов, которыми можно записать в ряд подпоследовательность из K элементов некоторой перестановки из N элементов. При этом последовательности из одинаковых элементов, но с различным их порядком следования считаются различными. Количество таких комбинаций расчитывается по формуле: ANK = N!/(N-K)!.

Например, для N=4 и K=2 из перестановки (1 2 3 4) можно составить следующие последовательности из 2х элементов: (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (2 1), (3 1), (4 1), (3 2), (4 2), (4 3). Всего получилось A42 = 4!/(4-2)! = 12 вариантов.

Число сочетаний CNK

Под числом сочетаний понимают количество вариантов, которыми можно выбрать K элементов из некоторого множества, состоящего из N элементов. При этом последовательности из одинаковых элементов, но с различным их порядком следования считаются равными. Количество таких комбинаций расчитывается по формуле: CNK = ANK/K! = N!/(K!*(N-K)!).

Например, для N=4 и K=2 из перестановки (1 2 3 4) можно составить следующие последовательности из 2х элементов: (1 2), (1 3), (1 4), (2 3), (2 4), (3 4). Всего получилось С42 = 4!/(2!*(4-2)!) = 6 вариантов.

Число сочетаний очень часто используется при решении комбинаторных задач. Например, при игре в "спортлото 5 из 36" с помощью данной формулы можно расчитать вероятность угадывания 5 номеров, т.к. общее число возможных вариантов выбора 5 из 36 равно С365.

Формулы, использующие число сочетаний:

  • CNK = CN-1K-1 + CN-1K
  • CN0 + CN1 + ... + CNN = 2N
  • (x+y)N=CN0*x0*yN+ ...+CNK*xK*yN-K+...+CNN*xN*y0

Список задач

Задача 1: Точки на костях
Задача 2: Игра с монеткой
Задача 3: Шахматы - 2
Задача 4: Великий комбинатор
Задача 5: Волейбол

Вернуться

 
     
Югорский НИИ ИТ, Югорский ФМЛ


Корпоративные провайдеры на http://complat.ru.