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


Сочетания


Пусть M - конечное (не обязательно упорядоченное) множество, состоящее из n элементов.

Определение. Сочетанием из n элементов по k называется любое подмножество множества

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

Другими словами, в сочетаниях не важен порядок элементов, а важен лишь их состав. Так, например, из множества M = {1, 2, 3, 4} можно составить четыре различных сочетания из 4 по 3: {1, 2, 3}, {1,2,4}, {2, 3, 4}, {1, 3, 4}.

Число различных сочетаний из n элементов по k равно:

  Если k = 0, тогда

Учитывая, что число размещений из n элементов по k равно, но

,

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

.

Пример 9. Дано 10 точек, из которых никакие три не лежат на одной прямой и никакие четыре точки не лежат в одной плоскости. Сколько различных плоскостей можно провести через эти точки?

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

Поскольку это так, тогда, если плоскость проходит через три точки A, B, C, то через точки B, A, C или C, B, A и т.п., проходит та же плоскость, т. е.

порядок расположения трех точек, через которые проходит плоскость не имеет значения. А значит число различных плоскостей, проведенных через каждые три точки из 10 равно числу сочетаний из 10 элементов по 3.

Составим процедуру вычисления числа сочетаний из n элементов по k.

Для этого удобней воспользоваться второй формулой, в которой вычисляется только один факториал числа k. В формуле

 их надо вычислять целых три (n!, (n - k)! и k!) и может возникнуть ситуация, когда будут получаться очень большие числа, которые могут выходить за пределы указанного целого типа. 

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

Итак, пользуемся формулой:  

В процедуре, в качестве входных формальных переменных будут две переменные n и k, для числа всех элементов и числа выбираемых элементов.


- Начало -  - Назад -  - Вперед -



Книжный магазин