Hosted by uCoz

Задача № 29. Вычислить число сочетаний из n по k

Формулировка. Даны натуральные числа n и k (k не превышает n). Вычислить число сочетаний из n по k.

Примечание: в комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов; при этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми. Обозначение числа сочетаний из n по k элементов: . При этом считается, что ,  и  для любого натурального n.

Например, найдем все 2-элементные сочетания 3-элементного множества {1, 2, 3}. Таковыми являются {1, 2}, {1, 3} и {2, 3}. То есть, таковых сочетаний 3. При этом, например, {1, 2} и {2, 1} – одинаковые сочетания, так как они отличаются только порядком следования элементов.

Решение. Из комбинаторики известна формула:

Не интересуясь вопросом ее вывода и корректности, мы будем использовать тот ее вариант, который написан после второго знака равенства (если смотреть слева направо), так как он наиболее оптимален для вычислений и позволит обойтись двумя циклами (для числителя for с downto, для знаменателя – просто for). Для числителя и знаменателя предусмотрим соответственно переменные num (от англ. numerator – «числитель») и denom (от англ. denominator – «знаменатель»), которым нужно поначалу присвоить значения 1, чтобы осуществить контроль частных случаев (этот вопрос упомянут в задаче 29):

1) При k = 0 переменная num останется неизменной и будет равна 1, так как невозможен вход в цикл с уменьшением от n до (n + 1), переменная denom будет равна 1 как 0!;

2) При n = k num и denom будут вычислены и при делении дадут единицу;

3) При n = k = 0 переменная denom будет вычислена как 0!, а переменная num не изменится по невозможности входа в цикл с уменьшением от 0 до 1.

Код:

  1. program NumOfCombinations;
  2. var
  3. i, n, k: byte;
  4. num, denom: integer;
  5. begin
  6. readln(n, k);
  7. num := 1;
  8. for i := n downto n - k + 1 do begin
  9. num := num * i
  10. end;
  11. denom := 1;
  12. for i := 1 to k do begin
  13. denom := denom * i
  14. end;
  15. writeln(num div denom)
  16. end.