Nə qədər?#3260

Nə qədər? (Həll təhlili)

Binomial əmsalını hesablamaq üçün aşağıdakı münasibətdən istifadə edə bilərsiniz:

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}

Bir $r es$ dəyişəni elan edib onu $1$ dəyəri ilə işarələyək. Sonra $r es$ -i $n$ -ə vururuq və nəticəni $1$ -ə bölürük. Daha sonra $r es$ -i $n -1$ -ə vurub $2$ -yə bölürük. Vurulma və bölmə prosesini $k$ dəfə ( $(n - k)!$ -ə bölündükdən sonra $C_{n}^{k}$ C_n^{k}-nin pay və məxrəci $k$ vuruqçular daxil edir) davam etdiririk.

Rekursiv binomial əmsalını hesablamaq üçün aşağıdakı münasibətdən istifadə edə bilərsiniz:

C_{n}^{k} = {C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 1, k = n v ə y a k = 0

C_n^{k} = \begin{cases} C_{n - 1}^{k - 1} + C_{n - 1}^{k}, n > 0 \\ 1, k = n~və ya~k = 0 \end{cases}

Alqoritmin həyata keçirilməsi

Cnk funksiyası binomial əmsalının iterativ üsulla dəyərini hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Cnk funksiyası binomial əmsalının rekursiv üsulla dəyərini hesablayır.

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);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Cnk funksiyası binomial əmsalının iterativ üsulla dəyərini hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Cnk funksiyası binomial əmsalının iterativ üsulla dəyərini hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Alqoritmin həyata keçirilməsi – rekursiya

Cnk funksiyası binomial əmsalının rekursiv üsulla dəyərini hesablayır.

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);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Alqoritmin həyata keçirilməsi – rekursiya və yaddaş

Binomial əmsalının dəyərlərini yadda saxlamaq üçün $d p$ massivini elan edək: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

int dp[35][35];

Cnk funksiyası binomial əmsalının rekursiv üsulla dəyərini hesablayır. Ehtiyat texnikasından istifadə edirik.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$d p$ massivini işarələyirik.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Java həyata keçirilməsi – rekursiya

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 həyata keçirilməsi – rekursiya və yaddaş

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 həyata keçirilməsi – comb

Binomial əmsalını hesablamaq üçün daxili $co mb (n, k) = C_{n}^{k}$ comb(n, k) = C_n^{k} funksiyasından istifadə edəcəyik.

import math;

Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Python həyata keçirilməsi – faktorial

$f a c t (x)$ fact(x) funksiyası $x$ ədədinin faktorialını hesablayır.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayıb ekrana çıxarırıq.

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

Python həyata keçirilməsi – yaddaşa görə rekursiya

Cnk funksiyası binomial əmsalının rekursiv üsulla dəyərini hesablayır. Məmorayz texnikasından istifadə edirik.

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]

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Binomial əmsalının dəyərlərini yadda saxlamaq üçün $d p$ siyahısını elan edək: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^{k}.

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

Cavabı hesablayıb ekrana çıxarırıq.

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