برنامه محاسبه ضریب دو جمله ای — راهنمای کاربردی

1// A naive recursive C++ implementation 
2#include <bits/stdc++.h> 
3using namespace std;  
4  
5// Returns value of Binomial Coefficient C(n, k)  
6int binomialCoeff(int n, int k)  
7{  
8    // Base Cases  
9    if (k == 0 || k == n)  
10        return 1;  
11  
12    // Recur  
13    return binomialCoeff(n - 1, k - 1) +  
14                binomialCoeff(n - 1, k);  
15}  
16  
17/* Driver code*/
18int main()  
19{  
20    int n = 5, k = 2;  
21    cout << "Value of C("<<n<<", "<<k<<") is " << binomialCoeff(n, k);  
22    return 0;  
23}  
24  
25// This is code is contributed by rathbhupendra 

1// A Naive Recursive Implementation 
2#include<stdio.h> 
3  
4// Returns value of Binomial Coefficient C(n, k) 
5int binomialCoeff(int n, int k) 
6{ 
7  // Base Cases 
8  if (k==0 || k==n) 
9    return 1; 
10  
11  // Recur 
12  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k); 
13} 
14  
15/* Driver program to test above function*/
16int main() 
17{ 
18    int n = 5, k = 2; 
19    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)); 
20    return 0; 
21}

1// JAVA Code for Dynamic Programming | 
2// Set 9 (Binomial Coefficient) 
3import java.util.*; 
4  
5class GFG { 
6      
7    // Returns value of Binomial  
8    // Coefficient C(n, k) 
9    static int binomialCoeff(int n, int k)  
10    { 
11      
12        // Base Cases 
13        if (k == 0 || k == n) 
14            return 1; 
15          
16        // Recur 
17        return binomialCoeff(n - 1, k - 1) +  
18                    binomialCoeff(n - 1, k); 
19    } 
20      
21    /* Driver program to test above function */
22    public static void main(String[] args)  
23   { 
24        int n = 5, k = 2; 
25        System.out.printf("Value of C(%d, %d) is %d ", 
26                        n, k, binomialCoeff(n, k)); 
27    } 
28} 
29  
30// This code is contributed by Arnav Kr. Mandal. 

1# A naive recursive Python implementation 
2  
3def binomialCoeff(n , k): 
4  
5    if k==0 or k ==n : 
6        return 1
7  
8    # Recursive Call 
9    return binomialCoeff(n-1 , k-1) + binomialCoeff(n-1 , k) 
10  
11# Driver Program to test ht above function 
12n = 5
13k = 2
14print "Value of C(%d,%d) is (%d)" %(n , k , binomialCoeff(n , k)) 
15  
16# This code is contributed by Nikhil Kumar Singh (nickzuck_007) 
17

1// C# Code for Dynamic Programming | 
2// Set 9 (Binomial Coefficient) 
3using System; 
4  
5class GFG { 
6      
7    // Returns value of Binomial  
8    // Coefficient C(n, k) 
9    static int binomialCoeff(int n, int k)  
10    { 
11          
12        // Base Cases 
13        if (k == 0 || k == n) 
14            return 1; 
15          
16        // Recur 
17        return binomialCoeff(n - 1, k - 1) +  
18                    binomialCoeff(n - 1, k); 
19    } 
20      
21    /* Driver program to test above function */
22    public static void Main()  
23    { 
24        int n = 5, k = 2; 
25        Console.Write("Value of C(" + n + "," 
26                            + k + ") is " + 
27                        binomialCoeff(n, k)); 
28    } 
29} 
30  
31// This code is contributed by Sam007.

1<?php 
2// PHP Code for Dynamic Programming | 
3// Set 9 (Binomial Coefficient) 
4  
5// Returns value of  
6// Binomial Coefficient C(n, k) 
7function binomialCoeff($n, $k) 
8{ 
9    // Base Cases 
10    if ($k==0 || $k==$n) 
11        return 1; 
12      
13    // Recur 
14    return binomialCoeff($n - 1, $k - 1) +  
15               binomialCoeff($n - 1, $k); 
16} 
17  
18    // Driver Code 
19    $n = 5;  
20    $k = 2; 
21    echo "Value of C","(",$n ,$k,") is "
22               , binomialCoeff($n, $k); 
23  
24// This code is contributed by aj_36 
25?>

1// A Dynamic Programming based solution that uses  
2// table C[][] to calculate the Binomial Coefficient 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6// Prototype of a utility function that 
7// returns minimum of two integers 
8int min(int a, int b); 
9  
10// Returns value of Binomial Coefficient C(n, k) 
11int binomialCoeff(int n, int k) 
12{ 
13    int C[n + 1][k + 1]; 
14    int i, j; 
15  
16    // Caculate value of Binomial Coefficient 
17    // in bottom up manner 
18    for (i = 0; i <= n; i++) 
19    { 
20        for (j = 0; j <= min(i, k); j++) 
21        { 
22            // Base Cases 
23            if (j == 0 || j == i) 
24                C[i][j] = 1; 
25  
26            // Calculate value using previously 
27            // stored values 
28            else
29                C[i][j] = C[i - 1][j - 1] + 
30                          C[i - 1][j]; 
31        } 
32    } 
33  
34    return C[n][k]; 
35} 
36  
37// A utility function to return  
38// minimum of two integers 
39int min(int a, int b) 
40{ 
41    return (a < b) ? a : b; 
42} 
43  
44// Driver Code 
45int main() 
46{ 
47    int n = 5, k = 2; 
48    cout << "Value of C[" << n << "][" 
49         << k << "] is " << binomialCoeff(n, k); 
50} 
51  
52// This code is contributed by Shivi_Aggarwal  

1// A Dynamic Programming based solution that uses table C[][] to 
2// calculate the Binomial Coefficient 
3#include<stdio.h> 
4  
5// Prototype of a utility function that returns minimum of two integers 
6int min(int a, int b); 
7  
8// Returns value of Binomial Coefficient C(n, k) 
9int binomialCoeff(int n, int k) 
10{ 
11    int C[n+1][k+1]; 
12    int i, j; 
13  
14    // Caculate value of Binomial Coefficient in bottom up manner 
15    for (i = 0; i <= n; i++) 
16    { 
17        for (j = 0; j <= min(i, k); j++) 
18        { 
19            // Base Cases 
20            if (j == 0 || j == i) 
21                C[i][j] = 1; 
22  
23            // Calculate value using previously stored values 
24            else
25                C[i][j] = C[i-1][j-1] + C[i-1][j]; 
26        } 
27    } 
28  
29    return C[n][k]; 
30} 
31  
32// A utility function to return minimum of two integers 
33int min(int a, int b) 
34{ 
35    return (a<b)? a: b; 
36} 
37  
38/* Drier program to test above function*/
39int main() 
40{ 
41    int n = 5, k = 2; 
42    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) ); 
43    return 0; 
44}

1// A Dynamic Programming based solution that uses table C[][] to  
2// calculate the Binomial Coefficient  
3  
4class BinomialCoefficient 
5{ 
6    // Returns value of Binomial Coefficient C(n, k) 
7    static int binomialCoeff(int n, int k) 
8    { 
9    int C[][] = new int[n+1][k+1]; 
10    int i, j; 
11      
12        // Calculate  value of Binomial Coefficient in bottom up manner 
13    for (i = 0; i <= n; i++) 
14    { 
15        for (j = 0; j <= min(i, k); j++) 
16        { 
17            // Base Cases 
18            if (j == 0 || j == i) 
19                C[i][j] = 1; 
20       
21            // Calculate value using previously stored values 
22            else
23                C[i][j] = C[i-1][j-1] + C[i-1][j]; 
24          } 
25     } 
26       
27    return C[n][k]; 
28    } 
29  
30    // A utility function to return minimum of two integers 
31    static int min(int a, int b) 
32    { 
33    return (a<b)? a: b;  
34    } 
35  
36    /* Driver program to test above function*/
37    public static void main(String args[]) 
38    { 
39    int n = 5, k = 2; 
40    System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k)); 
41    } 
42} 
43/*This code is contributed by Rajat Mishra*/

1# A Dynamic Programming based Python Program that uses table C[][] 
2# to calculate the Binomial Coefficient 
3  
4# Returns value of Binomial Coefficient C(n, k) 
5def binomialCoef(n, k): 
6    C = [[0 for x in range(k+1)] for x in range(n+1)] 
7  
8    # Calculate value of Binomial Coefficient in bottom up manner 
9    for i in range(n+1): 
10        for j in range(min(i, k)+1): 
11            # Base Cases 
12            if j == 0 or j == i: 
13                C[i][j] = 1
14  
15            # Calculate value using previously stored values 
16            else: 
17                C[i][j] = C[i-1][j-1] + C[i-1][j] 
18  
19    return C[n][k] 
20  
21# Driver program to test above function 
22n = 5
23k = 2
24print("Value of C[" + str(n) + "][" + str(k) + "] is "
25      + str(binomialCoef(n,k))) 
26  
27# This code is contributed by Bhavya Jain 

1// A Dynamic Programming based solution that 
2// uses table C[][] to calculate the Binomial 
3// Coefficient  
4using System; 
5  
6class GFG { 
7      
8    // Returns value of Binomial Coefficient 
9    // C(n, k) 
10    static int binomialCoeff(int n, int k) 
11    { 
12        int [,]C = new int[n+1,k+1]; 
13        int i, j; 
14          
15        // Calculate value of Binomial  
16        // Coefficient in bottom up manner 
17        for (i = 0; i <= n; i++) 
18        { 
19            for (j = 0; j <= Math.Min(i, k); j++) 
20            { 
21                // Base Cases 
22                if (j == 0 || j == i) 
23                    C[i,j] = 1; 
24          
25                // Calculate value using previously 
26                // stored values 
27                else
28                    C[i,j] = C[i-1,j-1] + C[i-1,j]; 
29            } 
30        } 
31          
32        return C[n,k]; 
33    } 
34  
35    // A utility function to return minimum 
36    // of two integers 
37    static int min(int a, int b) 
38    { 
39        return (a < b) ? a : b;  
40    } 
41  
42    /* Driver program to test above function*/
43    public static void Main() 
44    { 
45        int n = 5, k = 2; 
46        Console.WriteLine("Value of C(" + n 
47                        + "," + k + ") is "
48                    + binomialCoeff(n, k)); 
49    } 
50} 
51  
52// This code is contributed by anuj_67. 

1<?php 
2// A Dynamic Programming based  
3// solution that uses table C[][] to 
4// calculate the Binomial Coefficient 
5  
6// Returns value of Binomial  
7// Coefficient C(n, k) 
8function binomialCoeff( $n, $k) 
9{ 
10    $C = array(array()); 
11    $i; $j; 
12  
13    // Caculate value of Binomial 
14    // Coefficient in bottom up manner 
15    for ($i = 0; $i <= $n; $i++) 
16    { 
17        for ($j = 0; $j <= min($i, $k); $j++) 
18        { 
19              
20            // Base Cases 
21            if ($j == 0 || $j == $i) 
22                $C[$i][$j] = 1; 
23  
24            // Calculate value using  
25            // previously stored values 
26            else
27                $C[$i][$j] = $C[$i - 1][$j - 1] +  
28                                 $C[$i - 1][$j]; 
29        } 
30    } 
31  
32    return $C[$n][$k]; 
33} 
34  
35    // Driver Code 
36    $n = 5;  
37    $k = 2; 
38    echo "Value of C(" ,$n," ",$k, ") is"," "
39                 , binomialCoeff($n, $k) ; 
40  
41// This code is contributed by anuj_67. 
42?>

1// C++ program for space optimized Dynamic Programming 
2// Solution of Binomial Coefficient 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6int binomialCoeff(int n, int k) 
7{ 
8    int C[k+1]; 
9    memset(C, 0, sizeof(C)); 
10  
11    C[0] = 1;  // nC0 is 1 
12  
13    for (int i = 1; i <= n; i++) 
14    { 
15        // Compute next row of pascal triangle using 
16        // the previous row 
17        for (int j = min(i, k); j > 0; j--) 
18            C[j] = C[j] + C[j-1]; 
19    } 
20    return C[k]; 
21} 
22  
23/* Drier program to test above function*/
24int main() 
25{ 
26    int n = 5, k = 2; 
27    printf ("Value of C(%d, %d) is %d ", 
28            n, k, binomialCoeff(n, k) ); 
29    return 0; 
30}

1// JAVA Code for Dynamic Programming |  
2// Set 9 (Binomial Coefficient) 
3import java.util.*; 
4  
5class GFG { 
6      
7    static int binomialCoeff(int n, int k) 
8    { 
9        int C[] = new int[k + 1]; 
10         
11        // nC0 is 1 
12        C[0] = 1;   
13       
14        for (int i = 1; i <= n; i++) 
15        { 
16            // Compute next row of pascal  
17            // triangle using the previous row 
18            for (int j = Math.min(i, k); j > 0; j--) 
19                C[j] = C[j] + C[j-1]; 
20        } 
21        return C[k]; 
22    } 
23      
24    /* Driver program  */
25    public static void main(String[] args)  
26    { 
27         int n = 5, k = 2; 
28            System.out.printf("Value of C(%d, %d) is %d "
29                                , n, k, binomialCoeff(n, k)); 
30    } 
31}

1# Python program for Optimized Dynamic Programming solution to 
2# Binomail Coefficient. This one uses the concept of pascal 
3# Triangle and less memory 
4  
5def binomialCoeff(n , k): 
6  
7    # Declaring an empty array 
8    C = [0 for i in xrange(k+1)] 
9    C[0] = 1 #since nC0 is 1 
10  
11    for i in range(1,n+1): 
12  
13        # Compute next row of pascal triangle using 
14        # the previous row 
15        j = min(i ,k) 
16        while (j>0): 
17            C[j] = C[j] + C[j-1] 
18            j -= 1
19  
20    return C[k] 
21  
22# Driver Program to test the above function 
23n = 5
24k = 2
25print "Value of C(%d,%d) is %d" %(n,k,binomialCoeff(n,k)) 
26  
27# This code is contribtued by Nikhil Kumar Singh(nickzuck_007) 

1// C# Code for Dynamic Programming |  
2// Set 9 (Binomial Coefficient) 
3using System; 
4  
5class GFG { 
6      
7    static int binomialCoeff(int n, int k) 
8    { 
9        int[] C = new int[k + 1]; 
10          
11        // nC0 is 1 
12        C[0] = 1;  
13      
14        for (int i = 1; i <= n; i++) 
15        { 
16            // Compute next row of pascal  
17            // triangle using the previous 
18            // row 
19            for (int j = Math.Min(i, k); 
20                              j > 0; j--) 
21                C[j] = C[j] + C[j-1]; 
22        } 
23        return C[k]; 
24    } 
25      
26    /* Driver program */
27    public static void Main()  
28    { 
29        int n = 5, k = 2; 
30        Console.WriteLine("Value of C(" 
31                + n + " " + k + ") is " 
32                + binomialCoeff(n, k)); 
33    } 
34} 
35  
36// This code is contribtued by anuj_67.

1<?php 
2// PHP program for space optimized  
3// Dynamic Programming Solution of  
4// Binomial Coefficient 
5function binomialCoeff($n, $k) 
6{ 
7    $C = array_fill(0, $k + 1, 0); 
8  
9    $C[0] = 1; // nC0 is 1 
10  
11    for ($i = 1; $i <= $n; $i++) 
12    { 
13        // Compute next row of pascal  
14        // triangle using the previous row 
15        for ($j = min($i, $k); $j > 0; $j--) 
16            $C[$j] = $C[$j] + $C[$j - 1]; 
17    } 
18    return $C[$k]; 
19} 
20  
21// Driver Code 
22$n = 5; $k = 2; 
23echo "Value of C[$n, $k] is ".  
24        binomialCoeff($n, $k); 
25      
26// This code is contributed by mits. 
27?>