{Как-то раз, придя домой со школы, Света обнаружила записку от мамы, в которой она просила сделать салат. Света знала, что салат – это смесь двух или более ингредиентов, поэтому ей не составило труда выполнить мамину просьбу.

Но Света хочет стать математиком, поэтому, для тренировки, решила посчитать, сколько различных салатов она сможет сделать из имеющихся продуктов (майонез, огурцы, помидоры). После небольших расчетов она получила ответ: 4.

Зная, что вы любите интересные задачки, и хотите стать программистами, Света попросила вас написать программу, которая определяет количество различных салатов для произвольного числа ингредиентов.}Подскажите формулу

Количество различных салатов R, которые можно приготовить, имея n продуктов и беря для приготовления k из них (k=2,3,… n-1), в математике определяется, как число размещений из n по k и определяется по следующей формуле:
\displaystyle C_n^k= \frac{n!}{k!(n-k)!}
Формула красивая, короткая, но неудобная для вычисления. В самом деле, надо найти три факториала, каждый из которых может оказаться достаточно большим числом. Но можно сделать небольшое преобразование и упростить вычисление.
\displaystyle R=C_n^k= \frac{n!}{k!(n-k)!} = \frac{k!(k+1)(k+2)...(n-1)n}{k!(n-k)!}= \\ 
 \frac{(k+1)(k+2)...(n-1)n}{1\cdot2\cdot...\cdot(n-k)}=\prod_{i=1}^{n-k} \frac{k+i}{i}

Но это было вычисление R только для конкретного k при заданном n.
Нам же нужно найти сумму R для всех k от 2 до n. И да, для k=n формула не предназначена, но зато мы и так понимаем, что для такого случая R=1.

Задача свелась к нахождению обычной суммы
\displaystyle S=C_2^n+C_3^n+...+C_{n-1}^n+1=1+\sum_{i=2}^{n-1}C_i^n

// PascalABC.NET 3.2, сборка 1370 от 24.12.2016
// Внимание! Если программа не работает, обновите версию!

function C(n,k:integer):integer;
begin
  if n=k then Result:=1
  else begin
    var p:=1.0;
    for var i:=1 to n-k do p:=p*(k+i)/i;
    Result:=Round(p);
    end;
end;

begin
  var n:=ReadInteger('Кол-во продуктов: ');
  var s:=1;
  for var i:=2 to n-1 do s:=s+C(n,i);
  Writeln('Кол-во салатов: ',s)
end.

Примеры:
Кол-во продуктов:  3
Кол-во салатов: 4

Кол-во продуктов:  5
Кол-во салатов: 26

Кол-во продуктов:  10
Кол-во салатов: 1013

Оцени ответ
Не нашёл ответ?

Если тебя не устраивает ответ или его нет, то попробуй воспользоваться поиском на сайте и найти похожие ответы по предмету Информатика.

Найти другие ответы

Загрузить картинку
© Задачки.net