Скільки? (Розбір)

Щоб обчислити біноміальний коефіцієнт, можна використати наступне співвідношення:

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k}

C_n^{k} = {n! \over k! \cdot (n - k)!} = {n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k}

Оголосимо змінну $r es$ і ініціалізуємо її значенням $1$ . Потім помножимо $r es$ на $n$ і поділимо результат на $1$ . Після цього помножимо $r es$ на $n -1$ і поділимо на $2$ . Процес множень та ділення будемо продовжувати $k$ разів (чисельник і знаменник $C_{n}^{k}$ C_n^{k} після скорочення на $(n - k)!$ містить $k$ множників).

Для рекурсивної реалізації біноміального коефіцієнта можна скористатися співвідношенням:

C_{n}^{k} = {C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 1, k = n або k = 0

C_n^{k} = \begin{cases} C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 \\ 1, k = n~або~k = 0 \end{cases}

Реалізація алгоритму

Функція Cnk обчислює значення біноміального коефіцієнта ітеративним методом.

int Cnk(int n, int k)
{
  int res = 1;
  for(int i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Функція Cnk обчислює значення біноміального коефіцієнта рекурсивним методом.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  return Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Функція Cnk обчислює значення біноміального коефіцієнта ітеративним методом.

int Cnk(int n, int k)
{
  int res = 1;
  for(int i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Функція Cnk обчислює значення біноміального коефіцієнта ітеративним методом.

int Cnk(int n, int k)
{
  int res = 1;
  for(int i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Реалізація алгоритму – рекурсія

Функція Cnk обчислює значення біноміального коефіцієнта рекурсивним методом.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  return Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Реалізація алгоритму – рекурсія з запам'ятовуванням

Оголосимо масив $d p$ для запам'ятовування значень біноміального коефіцієнта: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

int dp[35][35];

Функція Cnk обчислює значення біноміального коефіцієнта рекурсивним методом. Використовуємо техніку мемоізації.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&k);

Ініціалізуємо масив $d p$ .

memset(dp,-1,sizeof(dp));

Обчислюємо і виводимо відповідь.

res = Cnk(n,k);
printf("%d\n",res);

Java реалізація – рекурсія

import java.util.*;

public class Main
{
  static int Cnk(int n, int k)
  {
    if (n == k) return 1;
    if (k == 0) return 1;
    return Cnk(n - 1, k - 1) + Cnk(n - 1, k);
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    
    int res = Cnk(n,k);
    System.out.println(res);
    con.close();
  }
}

Java

Java реалізація – рекурсія з запам'ятовуванням

import java.util.*;

public class Main
{
  static int dp[][];
  
  static int Cnk(int n, int k)
  {
    if (n == k) return 1;
    if (k == 0) return 1;
    if (dp[n][k] != -1) return dp[n][k];	
    return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    dp = new int[n+1][k+1];
    for(int i = 0; i <= n; i++)
      Arrays.fill(dp[i],-1);
    
    int res = Cnk(n,k);
    System.out.println(res);
    con.close();
  }
}

Java

Python реалізація – comb

Для обчислення біноміального коефіцієнта скористаємось вбудованою функцією $co mb (n, k) = C_{n}^{k}$ comb(n, k) = C_n^{k}.

import math;

Читаємо вхідні дані.

n, k = map(int, input().split())

Обчислюємо і виводимо відповідь.

res = math.comb(n, k)
print(res)

Python реалізація – факторіал

Функція $f a c t (x)$ fact(x) обчислює факторіал числа $x$ .

def fact(x):
  if x:
    return fact(x - 1) * x
  else:
    return 1

Основна частина програми. Читаємо вхідні дані.

n, k = map(int, input().split())

Обчислюємо і виводимо відповідь.

res = fact(n) // (fact(k) * fact(n - k))
print(res)

Python реалізація – рекурсія з запам'ятовуванням

def Cnk(n, k, dp):
  if n == k: return 1
  if k == 0: return 1
  if dp[n][k] != -1: return dp[n][k]
  dp[n][k] = Cnk(n - 1, k - 1, dp) + Cnk(n - 1, k, dp)
  return dp[n][k]

Основна частина програми. Читаємо вхідні дані.

n, k = map(int, input().split())

Оголосимо список $d p$ для запам'ятовування значень біноміального коефіцієнта: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

dp = [[-1] * 35 for _ in range(35)]

Обчислюємо і виводимо відповідь.

res = Cnk(n, k, dp)
print(res)