ГДЗ по информатике 11 класс Босова, номер §9 № 12

§ №

Число сочетаний через факториал

Напишите программу вычисления $C_n^k=\dfrac{n!}{(n-k)!\cdot k!}$ . Используйте подпрограмму.

Решение

Вынесем вычисление факториала в функцию Factorial. По примеру этого параграфа , а для положительного верно . Это даёт граничное условие и рекурсивный вызов. Главная программа вызывает функцию трижды: для , и , затем подставляет результаты в формулу из условия. Поскольку факториал быстро растёт, для целочисленного типа int ограничим ввод значениями .

program Combinations;
var
  n, k: integer;
  resultValue: int;

function Factorial(m: integer): int;
begin
  if m =  then
    Factorial := 
  else
    Factorial := m * Factorial(m - );
end;

begin
  readln(n, k);
  if (n < ) or (n > ) or (k < ) or (k > n) then
    writeln('Требуется  <= k <= n <= ')
  else
  begin
    resultValue := Factorial(n) div
                   (Factorial(n - k) * Factorial(k));
    writeln('C = ', resultValue);
  end;
end.

Проверим на , . Функция последовательно даёт , и . Подставляем: . Операция div в основной программе выполняет целочисленное деление; число сочетаний всегда целое.

Ответ

Число сочетаний вычисляется вызовами функции Factorial по формуле при .

Помогло?

Номер §9 № 12