პერმუტაციის კოეფიციენტი


Რთული ტური საშუალო
ხშირად ეკითხებიან ბანკიბაზარი Xome
დინამიური პროგრამირება მათემატიკის პერმუტაცია

პრობლემის განცხადება

ამ პრობლემის "პერმუტაციის კოეფიციენტი" ჩვენ უნდა ვიპოვოთ, როდესაც n და k მნიშვნელობებს მოგვცემენ.

მაგალითი

n = 5, k = 2
20

განმარტება: ეს მნიშვნელობა არის n P r გვხვდება პერმუტაციის კოეფიციენტის ფორმულის გამოყენებით. 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 ++ კოდი პერმუტაციის კოეფიციენტის მისაღებად

#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 კოდი პერმუტაციის კოეფიციენტის მისაღებად

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
ჯავის კოდი ოპტიმიზირებული მიდგომისთვის
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