Данный раздел содержит набор тем для самостоятельного изучения основ курса олимпиадного программирования. Каждая тема включает теоритическую часть и набор задач, сложность которых растет от темы к теме. Для многих рассматриваемых задач приведен словесный разбор их решений. Но все же мы рекомендуем Вам сначала попытаться их решить самостоятельно, и лишь в том случае, когда это сделать не получается, прибегать к просмотру их решения.
Этот курс предназначен для школьников, имеющих некоторые знания в области программирования на уровне понимания синтаксиса языка и простейших алгоритмов.
Список тем
Тема 01:
При решении олимпиадных задач необходимо уметь работать с текстовыми файлами, т.к. от участника олимпиады, как правило, требуется написать программу, которая считывает некоторые данные из одного файла, производит определенные вычисления, а результат выводит в другой файл.
Для работы с файлами как в языке Паскаль, так и в языке Си можно обойтись без использования файловых переменных. Добавив две строчки кода в программу, можно перенаправить ввод данных с консоли на ввод из файла, а вывод на экран заменить на вывод в файл. Следующие фрагменты кода реализуют данную возможность:
// Язык Си freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
Перед выполнением заданий данного раздела рекомендуем ознакомиться с разделом "Новичкам", в котором дана классификация олимпиадных задач, разобрана структура олимпиадной задачи и приведены примеры работы с файлами на языках Паскаль и Си. С особенностями работы автоматизированной системы проверки и видами возможных ошибок можно ознакомиться в разделе "Работа в системе".
В этой теме мы предлагаем решить простейшие задачи, которые помогут ознакомиться с вводом-выводом данных. Подобные задачи обычно используются на пробных турах олимпиад по программированию.
Тема 02:
Тема 03:
Сложно представить серьезную программу без циклов. Мы полагаем, что вы уже знакомы с циклами. В этом разделе будет рассмотрен ряд задач, для решения которых необходимо использовать циклы.
Напомним, что существуют три вида циклов:
Оператор цикла с параметром
for i=1..n{ Операторы; }
Оператор цикла с предусловием
while(Условие){ Операторы; }
Оператор цикла с постусловием
do{ Операторы; }while(Условие);
Тема 04:
Тема 05:
Сортировка - преобразование последовательности элементов в неубывающую (или невозрастающую) последовательность. Последовательность элементов {Ai} называют неубывающей, если для любых i и j, таких что i < j выполняется неравенство Ai <= Aj. Для строго возрастающей последовательности неравенство принимает вид Ai < Aj. Аналогичным образом определяется невозрастающая и убывающая последовательности.
При решении олимпиадных задач часто необходима сортировка данных. Обычно данные представлены в виде массива из N элементов, где элементы - это чаще всего числа или строки. Для этого существует множество алгоритмов, которые с помощью замены значений элементов исходного массива приводят его к отсортированному виду.
Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элеменов массива N. Сложность задачи может быть логарифмической, линейной, квадратичной, экспонициальной и т.д., где для решения задачи необходимо выполнение O(ln(N)), O(N), O(N2) и O(eN) операций соответственно. Например, квадратичный порядок сложности O(N2) означает, что задача может использовать N2 операций, а может и 100*N2, здесь коэффициент перед N2 не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше.
Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n*ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N = 300 000 (приблизительно). В качестве примера подобных алгоритмов можно привести следующие сортировки: быстрая, пирамидальная, слиянием, бинарным деревом.
Простейшие алгоритмы сортировки имеют порядок O(N2), что позволяет решать задачу с сортировкой только для N <= 5000 (так же примерно). Несмотря на то, что квадратичные алгоритмы дают меньший эффект, их разумно использовать, когда скоростью сортировки данных можно принебречь, повысив скорость реализации программы. Примеры подобных сортировок: выбором, пузырьком, вставками.
В частных случаях отсортировать данные возможно с линейным порядком сложности, когда есть некоторые ограничения на данные (например, массив уже частично отсортирован или диапазон элементов массива ограничен). С таким порядком сложности возможна сортировка массива, состоящего из 107 элементов! Например, следующие алгоритмы дают такой результат: цифровая и пораздрядная сортировки.
Многие считают, что достаточно знания двух сотрировок (например, "пузырьком" и "быстрой"), чтобы решать любые олимпиадные задачи. Но на самом деле это далеко не так. Далее, рассмотрим алгоритмы сортировки, наиболее часто используемые программистами. Во всех примерах будем сортировать по неубыванию полагая, что a[i] - целочисленный массив, состоящий из n элементов, с индексами от 1 до n.
Сортировка выбором
Пожалуй, это самый легкий для реализации алгоритм среди существующих, идея которого сводится к последовательному позицированию нужных элементов с 1-го по n-й. Вначале среди всех элементов определяется наименьший и меняется с 1-м, далее среди всех оставшихся снова находится наименьший и меняется со 2-м. Далее, среди элементов, начиная с 3-го так же находится наименьший и меняется с 3-м и т.д. до (n-1)-го элемента. Квадратичная сложность алгоритма очевидна, а алгоритм решения может выглядеть следующим образом:
for i=1..n-1{ for j=i+1..n{ if(a[i] > a[j]) a[i] <---> a[j]; } }
Подробнее о сортировке выбором Вы можете прочитать здесь.
Сортировка пузырьком
Это, наверное, самый полулярный алгоритм сортировки, идея которого чем то похожа на предыдущий алгоритм: так же реализация сводится к позицированию нужных элементов с 1-го по последний. Сама процедура установки текущего элемента в нужную позицию чем то напоминает всплытие пузырька. Для того, чтобы первый элемент (наименьший) встал на свое место необходимо справа налево пройтись по массиву, попарно сравнивая соседние элементы и в том случае, когда левый больше правого менять их местами. Для позицирования второго элемента, нужно пройтись еще раз по массиву, но не до 1-го а уже до 2-го элемента и т.д. Данный алгоритм, который как и предыдущий имеет квадратичную сложность, можно представить следующим образом:
for i=1..n-1{ for j=n-1..i{ if(a[j] > a[j+1]) a[j] <---> a[j+1]; } } 5
Быстрая сортировка
Этот алгоритм является одним из самых популярных и наиболее часто используемым среди алгортимов, имеющих порядок сложности O(n*ln(n)). Сам алгоритм является рекурсивным и его идея заключается в следующем: для сортировки массива достаточно разбить его на две части так, чтобы все элементы левой части были меньше либо равны всех элементов правой части, далее следует выполнить подобную операцию с левой и правой частью, рассматривая их как отдельные массивы. Алгоритмическое представление процедуры, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:
Сортировка - преобразование последовательности элементов в неубывающую (или невозрастающую) последовательность. Последовательность элементов {Ai} называют неубывающей, если для любых i и j, таких что i < j выполняется неравенство Ai <= Aj. Для строго возрастающей последовательности неравенство принимает вид Ai < Aj. Аналогичным образом определяется невозрастающая и убывающая последовательности.
При решении олимпиадных задач часто необходима сортировка данных. Обычно данные представлены в виде массива из N элементов, где элементы - это чаще всего числа или строки. Для этого существует множество алгоритмов, которые с помощью замены значений элементов исходного массива приводят его к отсортированному виду.
Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элеменов массива N. Сложность задачи может быть логарифмической, линейной, квадратичной, экспонициальной и т.д., где для решения задачи необходимо выполнение O(ln(N)), O(N), O(N2) и O(eN) операций соответственно. Например, квадратичный порядок сложности O(N2) означает, что задача может использовать N2 операций, а может и 100*N2, здесь коэффициент перед N2 не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше.
Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n*ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N = 300 000 (приблизительно). В качестве примера подобных алгоритмов можно привести следующие сортировки: быстрая, пирамидальная, слиянием, бинарным деревом.
Простейшие алгоритмы сортировки имеют порядок O(N2), что позволяет решать задачу с сортировкой только для N <= 5000 (так же примерно). Несмотря на то, что квадратичные алгоритмы дают меньший эффект, их разумно использовать, когда скоростью сортировки данных можно принебречь, повысив скорость реализации программы. Примеры подобных сортировок: выбором, пузырьком, вставками.
В частных случаях отсортировать данные возможно с линейным порядком сложности, когда есть некоторые ограничения на данные (например, массив уже частично отсортирован или диапазон элементов массива ограничен). С таким порядком сложности возможна сортировка массива, состоящего из 107 элементов! Например, следующие алгоритмы дают такой результат: цифровая и пораздрядная сортировки.
Многие считают, что достаточно знания двух сотрировок (например, "пузырьком" и "быстрой"), чтобы решать любые олимпиадные задачи. Но на самом деле это далеко не так. Далее, рассмотрим алгоритмы сортировки, наиболее часто используемые программистами. Во всех примерах будем сортировать по неубыванию полагая, что a[i] - целочисленный массив, состоящий из n элементов, с индексами от 1 до n.
Сортировка выбором
Пожалуй, это самый легкий для реализации алгоритм среди существующих, идея которого сводится к последовательному позицированию нужных элементов с 1-го по n-й. Вначале среди всех элементов определяется наименьший и меняется с 1-м, далее среди всех оставшихся снова находится наименьший и меняется со 2-м. Далее, среди элементов, начиная с 3-го так же находится наименьший и меняется с 3-м и т.д. до (n-1)-го элемента. Квадратичная сложность алгоритма очевидна, а алгоритм решения может выглядеть следующим образом:
for i=1..n-1{ for j=i+1..n{ if(a[i] > a[j]) a[i] <---> a[j]; } }
Сортировка пузырьком
Это, наверное, самый полулярный алгоритм сортировки, идея которого чем то похожа на предыдущий алгоритм: так же реализация сводится к позицированию нужных элементов с 1-го по последний. Сама процедура установки текущего элемента в нужную позицию чем то напоминает всплытие пузырька. Для того, чтобы первый элемент (наименьший) встал на свое место необходимо справа налево пройтись по массиву, попарно сравнивая соседние элементы и в том случае, когда левый больше правого менять их местами. Для позицирования второго элемента, нужно пройтись еще раз по массиву, но не до 1-го а уже до 2-го элемента и т.д. Данный алгоритм, который как и предыдущий имеет квадратичную сложность, можно представить следующим образом:
for i=1..n-1{ for j=n-1..i{ if(a[j] > a[j+1]) a[j] <---> a[j+1]; } }
Быстрая сортировка
Этот алгоритм является одним из самых популярных и наиболее часто используемым среди алгортимов, имеющих порядок сложности O(n*ln(n)). Сам алгоритм является рекурсивным и его идея заключается в следующем: для сортировки массива достаточно разбить его на две части так, чтобы все элементы левой части были меньше либо равны всех элементов правой части, далее следует выполнить подобную операцию с левой и правой частью, рассматривая их как отдельные массивы. Алгоритмическое представление процедуры, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:
Обычно мы имеем дело с десятичной системой счисления, в которой используется ровно 10 цифр: 0..9, и мы все к этому сильно привыкли. Но для обозначения чисел возможно использование других систем, отличных от десятичной. Особенностью таких систем является, отличное от 10 количество используемых цифр. Например, в двоичной системе используется только две цифры - 0 и 1; и любое число может быть представлено в такой системе. Если система имеет порядок, больший чем 10, то в качестве следующих цифр используются латинские буквы; например, в шестнадцатеричной системе присутствуют следующие цифры: 0..9,A,B,C,D,E и F.
Для того, чтобы представить какое либо число в десятичной системе счисления, следует вычислить сумму всех цифр данного числа, умноженных на порядок системы счисления, возведенной в степень, равную номеру разряда данной цифры. Следующие примеры демонстрируют суть данного метода:
Для перевода из десятичной системы счисления в систему с основанием k необходимо производить деление исходного числа на k, запоминая остатки от деления и продолжая данную операцию с целочисленным значением деления до тех пор, пока результатом деления не будет ноль. Искомым представлением числа будет запись, составленная из полученных остатков от деления, записанных в обратном порядке. Ниже представлены примеры перевода:
При решении олимпиадных задач обычно рассматривают системы счисления с основаниями от 2 до 36. Это связано с тем, что в латинском алфавите 26 букв (10 цифр + 26 букв = 36 символов). Для хранения цифр числа можно использовать как целочисленный массив, так и строку. Пусть S - число, записанное в K-ой системе счисления, а X - число в десятичной системе. Тогда алгоритм перевода из любой системы в десятичную можно записать следующим образом:
read(S); X=0; for i = 1..len(S){ X = X*K+S[i]; } write(X);
Алгоритм перевода из десятичной системы числа X в систему с основанием К и записи его в S может быть представлен так:
read(X); l=0; do{ l=l+1; S[l] = X mod K; X = X div K; }while(X>0); write(reverse(S));
Для того, чтобы перевести из k-ой системы счисления в систему с основанием m, можно воспользоваться "принципом чайника" и перевести сначала из k-ой системы в 10-ую, а затем из 10-ой в m-ую. Однако, иногда этой двойной операции можно избежать. Речь идет о случае, когда мы имеем дело с кратными системами счисления. Например, несложно переводить из 2-ой в 4-ую, 8-ую, 16-ную и обратно; аналогично можно сказать о 3-ой и 27-ой системах или о 5-ой и 25-ой. В подобных случаях каждая цифра числа в системе с большим основанием представляется в виде нескольких цифр системы с меньшим основанием. Так, в 4-ой системе каждая цифра представляется 2-мя цифрами 2-ой системы, в 8-ой - 3мя цифрами 2-ой, а в 16-ой каждая цифра есть ничто иное как 4 цифры 2-ой системы. Например, для перевода двоичного числа 101100101010011011 в 16-ую систему достаточно разбить число на 4ки: 0010 1100 1010 1001 1011 и записать каждую из них в 16-ом формате: 2CA9B, т.к. 0010 = 2, 1100 = B, 1010 = A, 1001 = 9 и 1011 = B. Несложно догадаться, что обратное преобразование из 16-ой в 2-ую систему происходит аналогичным образом.
Тема 08:
Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Достаточно сложно дать полное определение теории чисел, т.к. точного определения и не существует вовсе. Мы же будем рассматривать только ту ее часть, которая используется при решении олимпиадных задач. В большей степени будем уделять внимание целым числам. Для этого определим некоторые разновидности чисел ...
Множество всех целых чисел обычно обозначают буквой Z и понимают под ним набор всех действительных чисел без дробной части: {... , -3, -2, -1, 0, 1, 2, 3, ...}. Натуральные числа являются подмножетством целых чисел и образуют множество N: {1, 2, 3, ...}.
Простым числом называют натуральное число, большее единицы, которое делится только на 1 и на само себя. Все остальные числа называют составными. Первые 10 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Перечислим несколько свойств простых чисел:
любое составное число представляется уникальным образом в виде произведения простых чисел; иначе еще говорят, что разложение числа на простые множители однозначно.
простых чисел бесконечно много, причем существует примерно n/ln(n) простых чисел, меньших числа n.
наименьший простой делитель составного числа n не превышает sqrt(n), поэтому для проверки простоты числа достаточно проверить его делимость на 2 и все нечетные (а еще лучше простые) числа, не превосходящие sqrt(n).
любое четное число, большее двух представимо в виде суммы двух простых чисел; а любое нечетное, большее чем 5 представимо в виде суммы трех простых чисел
для любого натурального n, большего единицы существует хотя бы одно простое число на интервале (n, 2*n)
Числа Мерсена - это числа, представимые в виде 2n-1. Особый интерес представляют простые числа Мерсена, которые получаются при n=2, 3, 5, 7, 13, 17, 19, 41, 47, 61, 89, 10, 127, ... На сегодняшний день известно 44 простых числа Мерсена и самое большое из них получается при n=32582657 и содержит в себе почти 10 миллионов цифр, оно же является самым большим из найденных на сегодняшний день. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена.
Числа Ферма - это числа, представимые в виде 22n+1. Простыми среди чисел вида 2n+1 могут быть только числа Ферма. На данный момент известно всего 5 простых чисел Ферма: 3, 5, 17, 257, 65537; так же известно, что для 5<=n<=32 все числа Ферма - составные.
Совершенное число - это натуральное число, равное сумме всех своих делителей, не включая самого себя. Например число 28 - совершенное число, т.к. 28=1+2+4+7+14. Вот первые 10 совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216. Известно, что любое четное совершенное число может быть представлено в виде 2p-1(2p-1), где число 2p-1 является простым числом Мерсена. На сегодняшний день не известно: конечно ли количество совершенных чисел и существуют ли нечетные совершенные числа.
Дружественные числа - два натуральных числа, для которых сумма всех делителей первого числа (кроме него самого) равна второму числу и сумма всех делителей второго числа (кроме него самого) равна первому числу. Иногда частным случаем дружественных чисел считаются совершенные числа: каждое совершенное число дружественно себе. Обычно же, говоря о дружественных числах, имеют в виду пары из двух разных чисел. Первые 8 пар таких чисел: 220 и 284, 1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368, 10744 и 10856, 12285 и 14595, 17296 и 18416.
Число Армстронга - натуральное число, которое равно сумме своих цифр, возведённых в степень, равную количеству его цифр. Например, 1634 = 14 + 64 + 34 + 44. Последовательность чисел Армстронга начинается так: 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651 ... С одним из алгоритмов поиска таких чисел
m-самовлюбленное число - натуральное число, которое равно сумме своих цифр, возведённых в степень m, где m - некоторое натуральное число. Числа Армстронга - частный случай таких чисел.
Число Смита — такое составное число, сумма цифр которого (в данной системе счисления) равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита может служить 202, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4 (202 = 2 * 101). У. Л. МакДэниел доказал, что существует бесконечно много чисел Смита. Насчитывается 29 928 чисел Смита в пределах до 1 000 000. Первые 50 чисел Смита: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086.
Тема 09:
Длинная арифметика - раздел олимпиадного программирования, в котором рассматривается реализация действий с большими числами, не умещающихся в стандартных типах данных. На сегодняшний день единственным языком, используемым для решения олимпиадных задач и поддерживающим длинную арифметику, является Java, где все необходимые функции для работы с длинными числами встроены и можно обойтись без трудоемких реализаций.
В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1м элементе массива будем хранить последнюю цифру числа, во 2м - предпоследнюю и т.д. до последней цифры. В 0м элементе можно хранить общее количество цифр в числе. В простейшем случае, для хранения числа 154 достаточно будет использовать следующую запись:
const maxsize=100; int a[maxsize]; a[0]=3; a[1]=4; a[2]=5; a[3]=1;
Элементом массива может быть не одна цифра, возможно использовать один элемент для хранения 4х цифр, т.к. мы понимаем, что на современных ЭВМ все операции как минимум 32-разрядные, поэтому время на сложение двух цифр такое же как и на сложение чисел, состоящих из 4х цифр. Поэтому часто используют порядок системы счисления base=10000 и фактически длинные числа хранятся как бы в 10000-й системе счисления, это позволяет увеличить скорость выполнения операций над ними в 3-4 раза.
Идея реализации всех необходимых операций (сложение, вычитание, умножение, деление и т.д.) основана на тех принципах, которыми мы пользуемся при расчетах на бумаге. Даже когда мы реализуем деление "в столбик", фактически мы работаем с небольшими числами, сводя более сложную задачу к набору из более простых подзадач.
Задачи, которые рассматриваются в данном разделе представляют собой базовый набор, достаточный для формирования первоначальных навыков овладения принципами длинной арифметики. Практически все задачи на длинную арифметику требуют чтения из файла и запись в файл длинных чисел, поэтому приведем реализацию этих функций в данном разделе, а в разборе задач будем их использовать:
void readlong(int *a){ int i; string s; read(s); a[0]=len(s); for i=1..a[0]{ a[a[0]-i+1]=ord(s[i])-48; } }
void writelong(int *a){ for i=a[0]..1{ write(a[i]); } }
Так же часто возникает необходимость сравнивать длинные числа. Опишем следующую функцию, которая будет возвращать 0 в случае равенства чисел, -1 когда первое число меньше второго и 1 когда первое больше:
int complong(int *a, int *b){ if (a[0] < b[0]) return -1; if (a[0] > b[0]) return 1; for i=a[0]..1{ if(a[i] < b[i]) return -1; if(a[i] > b[i]) return 1; } return 0; }
Тема 10:
Комбинаторика - раздел олимпиадного программирования (а так же и раздел математики), где ставится вопрос о подсчтете числа вариантов выбора элементов из некоторого, как правило, конечного множества согласно заданным правилам.
В качестве примеров комбинаторных задач могут быть следующие:
Сколько различных слов возможно составить из заданного набора букв: "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 вариантов.
