בינאָמיאַל קאָואַפישאַנט


שוועריקייט לעוועל מיטל
אָפט געבעטן אין דירעקטי עקספּעדיאַ HackerRank Xome
דינאַמיש פּראָגראַממינג LeetCode מאַט

פּראָבלעם סטאַטעמענט

געפֿינען די בינאָמיאַל קאָואַפישאַנט פֿאַר אַ געגעבן ווערט פון n און k.

"אין מאטעמאטיק, די בינאָמיאַל קאָואַפישאַנץ זענען די positive ינטאַדזשערז אַז פּאַסירן ווי קאָואַפישאַנץ אין די בינאָמיאַל טעאָרעם. געוויינטלעך, אַ בינאָמיאַל קאָואַפישאַנט איז ינדעקסט דורך אַ פּאָר פון ינטאַדזשערז n ≥ k ≥ קסנומקס און איז געשריבן ווי ”- ציטירט פֿון וויקיפעדיע.

בייַשפּיל

n = 5, k = 2
10

דערקלערונג: מיט די פאָרמולע פֿאַר די כעזשבן פון די ביינעריאַל קאָואַפישאַנט, מיר געפֿינען 5 C 3 וואָס איז גלייַך צו 10.

וואָס איז בינאָמיאַל קאָואַפישאַנט?

איידער איר וויסן ווי צו געפֿינען אַ בינאָמיאַל קאָואַפישאַנט. זאל ס דיסקוטירן בעקיצער וואָס איז בינאָמיאַל קאָואַפישאַנט? און וואָס איז עס אפילו פארלאנגט?

ווייַל בינאָמיאַל קאָואַפישאַנט איז שווער צו סאָלווע קאָמבינאַטאָריקס פּראָבלעמס. זאל ס זאָגן איר האָבן עטלעכע פאַרשידענע עלעמענטן און איר דאַרפֿן צו קלייַבן עלעמענטן. אַזוי, אויב איר ווילן צו סאָלווע דעם פּראָבלעם, איר קענען לייכט שרייַבן אַלע די קאַסעס פון טשוזינג ק עלעמענטן פֿון N עלעמענטן. אָבער דאָס איז אַ זייער צייט-קאַנסומינג פּראָצעס ווען n ינקריסיז. דעם פּראָבלעם קענען זיין לייכט סאַלווד מיט בינאָמיאַל קאָואַפישאַנט. מער ווי אַז, דעם פּראָבלעם פון טשוזינג ק עלעמענטן פֿון n פאַרשידענע עלעמענטן איז איינער פון די וועג צו דעפינירן בינאָמיאַל קאָואַפישאַנט N C ק. בינאָמיאַל קאָואַפישאַנט קענען זיין לייכט קאַלקיאַלייטיד מיט די פאָרמולע:

זינט מיר זענען גוט מיט די באַסיקס, מיר זאָל געפֿינען וועגן צו רעכענען דעם יפישאַנטלי.

נאַיוו צוגאַנג צו געפֿינען בינאָמיאַל קאָואַפישאַנט

דעם צוגאַנג איז נישט צו נאַיוו אין אַלע. באַטראַכטן אַז איר זענט געבעטן צו געפֿינען די נומער פון וועגן צו קלייַבן 3 עלעמענטן פֿון 5 עלעמענטן. אַזוי איר קענען לייכט געפֿינען n !, k! און (נק)! און שטעלן די וואַלועס אין די געגעבן פאָרמולע. די לייזונג נעמט בלויז באצייטנס און אָ (1) פּלאַץ. אָבער מאל דיין פאַקטאָריאַל וואַלועס קען לויפן, אַזוי מיר דאַרפֿן צו נעמען קעיר פון דעם. דער צוגאַנג איז פייַן אויב מיר וועלן רעכענען אַ איין בינאָמיאַל קאָואַפישאַנט. אָבער פילע מאָל מיר דאַרפֿן צו רעכענען פילע בינאָמיאַל קאָואַפישאַנץ. אַזוי, עס איז בעסער צו האָבן זיי פּרעקאָמפּוטעד. מיר וועלן געפֿינען זיך ווי אַזוי צו געפֿינען די בינאָמיאַל קאָואַפישאַנץ יפישאַנטלי.

אָפּטימיזעד צוגאַנג צו געפֿינען בינאָמיאַל קאָואַפישאַנט

נו, נאַיוו צוגאַנג איז נישט נאַיוו אויב מיר געוואלט צו געפֿינען אַ איין בינאָמיאַל קאָואַפישאַנט. אָבער ווען מיר דאַרפֿן צו געפֿינען פילע באַנמאָיאַל קאָואַפישאַנץ. דער פּראָבלעם איז שווער צו פאַרענדיקן אין צייט שיעור. ווייַל נאַיוו צוגאַנג איז נאָך צייט קאַנסומינג. דאָ מיר האָבן עטלעכע פֿראגן וואָס מיר זענען געבעטן צו רעכענען נק פֿאַר געגעבן n און ק. עס קען זיין פילע פֿראגן. צו סאָלווע דעם מיר זאָל זיין באַקאַנט מיט Pascal ס טריאַנגלע. סיבה וואָס וועט מאַכן אונדז פֿאַרשטיין פיל קלאר וואָס מיר וועלן טאָן וואָס מיר וועלן טאָן.

בינאָמיאַל קאָואַפישאַנט

קיין צעל אין פּאַסקאַל טריאַנגלע איז ביינעריאַל קאָואַפישאַנץ. מיר דאַרפֿן צו וויסן עטלעכע טינגז וועגן די פּאַסקאַל ס דרייַעק.

  1. עס סטאַרץ מיט רודערן 0.
  2. קיין נומער אין די Pascal 'ס דרייַעק איז די ביינעריאַל קאָואַפישאַנט.
  3. קיין בינאָמיאַל קאָואַפישאַנט וואָס איז נישט ביי די באַונדריז פון די רודערן איז געמאכט פון די סומע פון ​​עלעמענטן וואָס זענען פּונקט אויבן עס אין לינקס און רעכט ריכטונג.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {for all integers}} n , k: 1 \ leq k \ leq n-1,

איצט מיר וויסן אַז יעדער בינאָמיאַל קאָואַפישאַנט איז אָפענגיק אויף צוויי בינאָמיאַל קאָואַפישאַנץ. אַזוי אויב מיר קענען עפעס סאָלווע זיי, מיר קענען לייכט נעמען זייער סומע צו געפֿינען אונדזער פארלאנגט בינאָמיאַל קאָואַפישאַנט. אַזוי דאָס גיט אונדז אַן ינטוישאַן פון ניצן דינאַמיש פּראָגראַממינג. דאָ די באַסעס זענען אויך לייכט ספּעציפיצירט דפּ [0] [0] = 1, דפּ [איך] [0] = דפּ [איך] [[איך] = 1.

קאָדעקס

C ++ קאָד פֿאַר דערגייונג בינאָמיאַל קאָואַפישאַנט

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

int C[51][51];

// this function just makes our pascal triangle
void precomputeBinomialCoefficients()
{

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

int main()
{
  // precomputationis being done for n = 50, you can change the value of n
  precomputeBinomialCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the propertoes of binomial coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<C[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
3
5 3
5 2
6 4
10
10
15

Java קאוד צו געפֿינען בינאָמיאַל קאָואַפישאַנט

import java.util.*;

class Main{
  static int C[][];

  // this function just makes our pascal triangle
  static void precomputeBinomialCoefficients() 
  {
    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0 || j == i) 
          C[i][j] = 1; 
        else
          C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    C = new int[51][51];
    // precomputationis being done for n = 50, you can change the value of n
    precomputeBinomialCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(C[n][k]);		
      else
        System.out.println(0);
    }
  }
}
3
5 2
5 3
6 3
10
10
15

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי 

אָ (N ^ 2 + Q),  ווייַל מיר זענען פּרעקאָמפּוטינג די בינאָמיאַל קאָואַפישאַנץ אַרויף צו נקן. די אָפּעראַציע נעמט אָ (N ^ 2) צייט און דאַן אָ (1) צייט צו ענטפֿערן יעדער אָנפֿרעג.

ספעיס קאַמפּלעקסיטי

אָ (N ^ 2),  פֿאַר סטאָרינג די פּרעקאָמפּוטעד רעזולטאַטן פון בינאָמיאַל קאָואַפישאַנץ.