二項式係數


難度級別
經常問 指令 Expedia的 HackerRank Xome
動態編程 力碼 數學

問題陳述

求出給定值n和k的二項式係數。

“在 數學中, 二項式係數 是積極的 整數 發生為 係數 在 二項式定理。 通常,二項式係數由一對整數索引 n ≥ k ≥0 並寫為 ” –引用自 維基百科。

n = 5, k = 2
10

說明:使用公式計算二項式係數,我們發現 5 C 3 等於10

什麼是二項式係數?

在知道如何找到二項式係數之前。 讓我們簡短地討論 什麼是二項式係數? 為什麼還要這樣做?

因為二項式係數被廣泛用於解決組合問題。 假設您有一些 不同的元素,你需要選擇 元素。 因此,如果要解決此問題,可以輕鬆編寫從n個元素中選擇k個元素的所有情況。 但是,當n增加時,這是一個非常耗時的過程。 使用二項式係數可以輕鬆解決此問題。 不僅如此,從n個不同的元素中選擇k個元素的問題是定義二項式係數的一種方法 n C k 使用給定的公式可以很容易地計算出二項式係數:

由於現在我們精通基礎知識,因此我們應該找到有效計算此方法的方法。

尋找二項式係數的幼稚方法

這種方法不是 太天真了。 考慮要求您找到從3個元素中選擇5個元素的方法數量。 這樣您就可以輕鬆找到 n!,k! 和(nk)! 並將值放在給定的公式中。 該解決方案僅需 準時O(1)空間。 但是有時您的階乘值可能會溢出,因此我們需要注意這一點。 如果我們要計算單個二項式係數,則此方法很好。 但是很多時候我們需要計算許多二項式係數。 因此,最好對它們進行預先計算。 我們將找到如何有效地找到二項式係數。

尋找二項式係數的優化方法

好吧,如果我們想找到一個二項式係數,那麼幼稚的方法不是幼稚的。 但是當我們需要找到許多二項式係數時。 因此,該問題變得難以在時限內完成。 因為幼稚的方法仍然很耗時。 所以,這裡有一些查詢,要求我們計算 克 給定n和k。 可能有很多查詢。 為了解決這個問題,我們應該熟悉Pascal的Triangle。 原因將使我們更加清楚地了解我們為什麼要去做我們要去做的事情。

二項式係數

帕斯卡三角形中的任何像元均表示二項式係數。 我們需要了解有關Pascal三角形的一些知識。

  1. 它從第0行開始。
  2. 帕斯卡三角形中的任何數字表示二項式係數。
  3. 不在行邊界上的任何二項式係數都由在左右方向上恰好位於其上方的元素的總和得出。

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {對於所有整數}} n ,k:1 \ leq k \ leq n-1,

現在我們知道每個二項式係數都取決於兩個二項式係數。 因此,如果我們能夠以某種方式解決它們,那麼我們可以輕鬆地將它們的和求出,以找到所需的二項式係數。 所以這給了我們使用的直覺 動態編程。 在這裡,基本情況也很容易指定 dp [0] [0] = 1,dp [i] [0] = dp [i] [[i] = 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

複雜度分析

時間複雜度 

O(N ^ 2 + Q),  因為我們正在預先計算最高達nCn的二項式係數。 此操作需要O(N ^ 2)時間,然後是O(1)時間來回答每個查詢。

空間複雜度

O(N ^ 2),  用於存儲二項式係數的預計算結果。