Коэффисиенти иҷозат


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад BankBazaar Xome
Барномарезии динамикӣ Матем Иҷозат

Изҳороти мушкилот

Дар ин масъалаи "Коэффитсиенти Пермутатсия", мо бояд онро вақте ки ба мо арзиши n & k дода мешавад, ёбем.

мисол

n = 5, k = 2
20

Шарҳ: Ин арзиши Радиои Умуми Миллӣ бо истифода аз формулаи коэффитсиенти ҷойивазкунӣ ёфт мешавад. nPr = n! / (nr)!

Равиш барои дарёфти коэффитсиенти "Пермутатсия"

Барои шиносоӣ бо коэффитсиенти "Пермутатсия". Мо бояд огоҳ бошем Иҷозат, он чизе нест, ҷуз пайдарпайи тасодуфии рақамҳои аз 1 то n. Ҳамин тавр, ҳоло мо медонем, ки Пермутатсия чист. Аммо коэффитсиенти ҷойивазкунӣ чист?

Ин чизе нест, ҷуз шумораи роҳҳои фармоиш r чизҳои аз чизҳои гуногун. Пас, барои содда кардани ин чӣ маъно дорад? Ин маънои онро дорад, ки мо каме доштем унсурҳои гуногун ва он гоҳ мо баъзе интихоб унсурҳо аз он ва акнун ба мо лозим аст, ки роҳҳои азнавташкилдиҳии онҳоро пайдо кунем. nPr тамоми роҳҳои корро нишон медиҳад. Масалан, 3P2 роҳҳои ҷобаҷогузории 2 унсури аз маҷмӯи 3 унсури гуногун интихобшударо нишон медиҳад.

Коэффисиенти иҷозат

Коэффитсиенти муқарраршударо низ ба осонӣ фаҳмидан мумкин аст, зеро аввал мо аз n унсур r интихоб мекунем. Ҳамин тавр аст nCr пас мо r унсурҳоро аз нав ҷобаҷо мекунем, ҳамин тавр nPr = nCr * r! .

Формулаи рекурсивӣ барои тавлиди коэффитсиенти Пермутатсия

P(n, k) = P(n-1, k) + k*P(n-1, k-1)

Мо метавонем ҷавоби заруриро бо истифода аз он пайдо кунем Барномарезии динамикӣ барои формулаи рекурсивӣ самаранок ҳисоб кардани он.

рамз

Коди C ++ барои ба даст овардани коэффитсиенти Permutation

#include<bits/stdc++.h>
using namespace std;

int P[51][51];

//precomputePermutationCoefficient
void precomputePermutationCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0)
        P[i][j] = 1;
      else
        P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
    }
  }
}

int main()
{
  // precomputations being done for n = 50, you can change the value of n
  precomputePermutationCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the properties of permutation coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<P[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
1
5 2
20

Рамзи Java барои ба даст овардани Коэффитсиенти Permutation

import java.util.*;

class Main{
  static int P[][];

  // precompute permutation coefficient
  static void precomputePermutationCoefficients() 
  {

    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0) 
          P[i][j] = 1; 
        else
          P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    P = new int[51][51];
    // precomputations being done for n = 50, you can change the value of n
    precomputePermutationCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the properties of permutation coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(P[n][k]);		
      else
        System.out.println(0);
    }
  }
}
1
5 2
20

Таҳлили мураккабӣ

Мураккабии вақт

O (N ^ 2 + Q), зеро барои дарёфти коэффитсиенти ҷойивазкунии мо аввал бояд ҳамаи коэффитсиентҳои ҷойивазкуниро, ки барои ҳисоб кардани ҷавоби зарурӣ заруранд, пешакӣ ҳисоб кунем. Ҳамин тавр мураккабии вақт полиномия мебошад. Дар ин ҷо ҳамаи саволҳоро дар O (1) ҷавоб додан мумкин аст.

Мураккабии фазо

O (N ^ 2), зеро мо барои нигоҳ доштани натиҷаи пешакӣ массиви 2D -ро истифода кардем.

Равиши беҳтарин барои коэффитсиенти муқарраршуда

Азбаски коэффитсиенти ҷойивазкунӣ ҷуз зарб кардани рақамҳо аз n то n-k + 1 чизи дигаре нест. Мо танҳо метавонем nPk -ро ҳисоб кунем Фазои O (1) ва Сари вақт.

рамз

Рамзи C ++ барои муносибати оптималӣ
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,k;cin>>n>>k;
  int P = 1;
  for(int i=n;i>=(n-k+1);i--)
    P*=i;
  cout<<P<<endl;
}
5 2
20
Рамзи Java барои муносибати оптималӣ
import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int P = 1;
    for(int i=n;i>=(n-k+1);i--)
      P*=i;
    System.out.println(P);
  }
}
5 2
20