Паскаль. Основы программирования


              

Размещения - часть 2


1, 2, 3, 4, 5, ..., 10, 11, 12.

По условию задачи, нам необходимо из этих 12 чисел выбирать по 5 чисел. Причем эти наборы из пяти чисел могут отличаться не только числами, но и расположением чисел, например, один из наборов будет: {1, 2, 3, 4, 5}; набор, который получается при перестановке этих же чисел {2, 1, 3, 4, 5}, также будет удовлетворять условию задачи.

В самом деле, пусть первый набор будет состоять из следующих предметов: {алгебра, физика, химия, история, литература}; тогда набор, полученный при перестановке хотя бы двух предметов уже даст новое расписание: {физика, алгебра, химия, история, литература}.

Таким образом, наборы из 5 чисел могут отличаться не только самими числами, но и порядком их расположения.

Такие подмножества называются в комбинаторике размещениями.

Определение. Размещением из n

элементов по k называется всякое упорядоченное подмножество данного множества, содержащее k элементов.

О размещениях можно сказать несколько иначе, правда менее строго с математической точки зрения, но более понятно для нас.

Размещением из n

элементов по k называется всякое подмножество данного множества, состоящее из k элементов, которое может отличаться не только элементами, но и порядком их расположения.

Например, из множества M = {1, 2, 3, 4} можно образовать 12 различных размещений, из 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}

Число размещений, взятых из n элементов по k, мы будем обозначать символом

 и определять по формуле:
 =
.

Значит,

=
 =
 =
  = 12.

Возвращаемся к примеру 1. В нем, как теперь уже стало ясно, надо найти число размещений

из 12 по 5.

По формуле находим:

 =
 =
  

Вычислить число размещений можно другим способом:

 =
=

Итак,

  

Словами можно сказать, что число размещений из n элементов по k равно произведению k элементов

 

Например,

 

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




Содержание  Назад  Вперед