Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

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
 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Формулы
 Динамика
 Перебор
 A. Хоккей
 B. Салаты
 C. Шахматы - 2
 D. Карточки
 E. Обмен
 F. Волейбол
 G. Волейбол - 2
 H. Великий комбинатор
 I. День рождения
 J. Нолики
 K. Салаты

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru