Συντελεστής μετάθεσης


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις BankBazaar Xome
Δυναμικός προγραμματισμός μαθηματικά Μετάθεση

Δήλωση προβλήματος

Σε αυτό το πρόβλημα «Συντελεστής Διαμόρφωσης», πρέπει να το βρούμε όταν μας δίνονται οι τιμές του n & k.

Παράδειγμα

n = 5, k = 2
20

Επεξήγηση: Αυτή η τιμή είναι n Ρρ βρίσκεται χρησιμοποιώντας τον τύπο του συντελεστή μετάθεσης. nPr = n! / (nr)!

Προσέγγιση εύρεσης Συντελεστή Παραλλαγής

Για να μάθετε για τον Συντελεστή Παραλλαγής. Πρέπει να γνωρίζουμε Μετάθεση, δεν είναι παρά τυχαία ακολουθία αριθμών από 1 έως n. Έτσι, τώρα ξέρουμε τι είναι η παραλλαγή. Αλλά τι είναι ο συντελεστής μετάθεσης;

Δεν είναι παρά ένας αριθμός τρόπων παραγγελίας r τα πράγματα από διαφορετικά πράγματα. Λοιπόν, για να απλοποιηθεί αυτό σημαίνει; Αυτό σημαίνει ότι είχαμε κάποια διαφορετικά στοιχεία και μετά επιλέγουμε μερικά στοιχεία από αυτό και τώρα πρέπει να βρούμε τους τρόπους αναδιάταξής τους. Το nPr δηλώνει όλους τους τρόπους. Για παράδειγμα, το 3P2 υποδηλώνει τρόπους αναδιάταξης 2 στοιχείων που επιλέγονται από ένα σύνολο 3 διαφορετικών στοιχείων.

Συντελεστής μετάθεσης

Ο συντελεστής παραλλαγής μπορεί επίσης να γίνει εύκολα κατανοητός καθώς επιλέγουμε πρώτα στοιχεία r από n στοιχεία. Αυτό είναι 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 in 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