در این مطلب، روش نوشتن برنامه محاسبه ضریب دو جمله ای یا در واقع، تابعی که دو پارامتر n و k را از ورودی بگیرد و مقدار ضریب دو جمله‌ای C(n, k) را بازگرداند، بیان شده است. همچنین، پیاده‌سازی روش مذکور در زبان‌های برنامه‌نویسی ++C و C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و PHP انجام شده است. در ادامه، تعاریف متداول ضریب دو جمله ای آمده است:
- ضریب دو جمله ای C(n, k) را می‌توان به عنوان ضریب X^k در بسط$$(1 + X)^n$$ تعریف کرد.
- یک ضریب دو جمله‌ای C(n, k)، تعداد راه‌هایی که k شی را می‌توان از بین n شی، صرف‌نظر از ترتیب آن‌ها، انتخاب کرد به دست می‌دهد. به بیان رسمی، تعداد زیرمجموعه‌های k-عنصر (یا k ترکیب) از یک مجموعه n عنصری را به دست می‌دهد.
اکنون، هدف نوشتن تابعی است که دو پارامتر n و k را از ورودی بگیرد و مقدار ضریب دو جمله‌ای C(n, k) را بازگرداند. برای مثال، تابع باید 6 را برای n = 4 و k = 2 و ۱۰ را برای n = 5 و k = 2 بازگرداند.
محاسبه ضریب دو جمله ای با روش بازگشتی
مقدار C(n, k) را می‌توان به صورت بازگشتی، با استفاده از رابطه استانداردی که در ادامه آمده است برای ضریب دو جمله‌ای محاسبه کرد.
C(n, k) = C(n-1, k-1) + C(n-1, k) C(n, 0) = C(n, n) = 1
در ادامه، پیاده‌سازی بازگشتی ساده (Naive Recursive) که به سادگی ساختار بازگشتی بیان شده در بالا را اعمال کند، ارائه شده است.
پیاده‌سازی روش ساده در ++C
// A naive recursive C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{ // Base Cases if (k == 0 || k == n) return 1; // Recur return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
}
/* Driver code*/
int main()
{ int n = 5, k = 2; cout << "Value of C("<<n<<", "<<k<<") is " << binomialCoeff(n, k); return 0;
}
// This is code is contributed by rathbhupendraپیاده‌سازی روش بازگشتی در C
// A Naive Recursive Implementation
#include<stdio.h>
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{ // Base Cases if (k==0 || k==n) return 1; // Recur return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
/* Driver program to test above function*/
int main()
{ int n = 5, k = 2; printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)); return 0;
}پیاده‌سازی روش بازگشتی در جاوا
// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;
class GFG { // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff(int n, int k) { // Base Cases if (k == 0 || k == n) return 1; // Recur return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } /* Driver program to test above function */ public static void main(String[] args) { int n = 5, k = 2; System.out.printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)); }
}
// This code is contributed by Arnav Kr. Mandal.پیاده‌سازی روش بازگشتی در پایتون
# A naive recursive Python implementation def binomialCoeff(n , k): if k==0 or k ==n : return 1 # Recursive Call return binomialCoeff(n-1 , k-1) + binomialCoeff(n-1 , k) # Driver Program to test ht above function n = 5 k = 2 print "Value of C(%d,%d) is (%d)" %(n , k , binomialCoeff(n , k)) # This code is contributed by Nikhil Kumar Singh (nickzuck_007)
پیاده‌سازی روش بازگشتی در #C
// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using System;
class GFG { // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff(int n, int k) { // Base Cases if (k == 0 || k == n) return 1; // Recur return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } /* Driver program to test above function */ public static void Main() { int n = 5, k = 2; Console.Write("Value of C(" + n + "," + k + ") is " + binomialCoeff(n, k)); }
}
// This code is contributed by Sam007.پیاده‌سازی روش بازگشتی در PHP
<?php
// PHP Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
// Returns value of
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{ // Base Cases if ($k==0 || $k==$n) return 1; // Recur return binomialCoeff($n - 1, $k - 1) + binomialCoeff($n - 1, $k);
} // Driver Code $n = 5; $k = 2; echo "Value of C","(",$n ,$k,") is " , binomialCoeff($n, $k);
// This code is contributed by aj_36
?>خروجی قطعه کدهای بالا، به صورت زیر است.Value of C(52) is 10
محاسبه ضریب دو جمله ای با برنامه‌نویسی پویا
لازم به ذکر است که تابع بالا، زیرمسائل مشابهی را دوباره و دوباره محاسبه می‌کند. درخت بازگشتی زیر با n = 5 و k = 2 در این راستا قابل توجه است. تابع C(3, 1) دو بار فراخوانی می‌شود. برای مقادیر n بزرگ، فراخوانی‌های تکراری زیادی برای زیرمسائل مشابه متعددی وجود خواهد داشت.
C(5, 2) / C(4, 1) C(4, 2) / / C(3, 0) C(3, 1) C(3, 1) C(3, 2) / / / C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2) / / / C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)
از آنجا که زیرمسائل تکراری مجددا فراخوانی می‌شوند، این مساله دارای خصوصیت هم‌پوشانی است. بنابراین، مسئله ضریب چند جمله‌ای دارای هر دو خصوصیت مسائل برنامه‌نویسی پویا است. (همچون دیگر مسائل برنامه‌نویسی پویا، محاسبه مجدد زیرمسائل مشابه با ساخت یک آرایه موقت C[][] در حالت پایین به بالا است). در ادامه، پیاده‌سازی راهکار این مسئله با استفاده از برنامه‌نویسی پویا، در زبان‌های برنامه‌نویسی گوناگون انجام شده است.
پیاده‌سازی روش برنامه‌نویسی پویا در ++C
// A Dynamic Programming based solution that uses
// table C[][] to calculate the Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;
// Prototype of a utility function that
// returns minimum of two integers
int min(int a, int b);
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{ int C[n + 1][k + 1]; int i, j; // Caculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } return C[n][k];
}
// A utility function to return
// minimum of two integers
int min(int a, int b)
{ return (a < b) ? a : b;
}
// Driver Code
int main()
{ int n = 5, k = 2; cout << "Value of C[" << n << "][" << k << "] is " << binomialCoeff(n, k);
}
// This code is contributed by Shivi_Aggarwalپیاده‌سازی روش برنامه‌نویسی پویا در C
// A Dynamic Programming based solution that uses table C[][] to
// calculate the Binomial Coefficient
#include<stdio.h>
// Prototype of a utility function that returns minimum of two integers
int min(int a, int b);
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{ int C[n+1][k+1]; int i, j; // Caculate value of Binomial Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously stored values else C[i][j] = C[i-1][j-1] + C[i-1][j]; } } return C[n][k];
}
// A utility function to return minimum of two integers
int min(int a, int b)
{ return (a<b)? a: b;
}
/* Drier program to test above function*/
int main()
{ int n = 5, k = 2; printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) ); return 0;
}پیاده‌سازی روش برنامه‌نویسی پویا در جاوا
// A Dynamic Programming based solution that uses table C[][] to
// calculate the Binomial Coefficient
class BinomialCoefficient
{ // Returns value of Binomial Coefficient C(n, k) static int binomialCoeff(int n, int k) { int C[][] = new int[n+1][k+1]; int i, j; // Calculate value of Binomial Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously stored values else C[i][j] = C[i-1][j-1] + C[i-1][j]; } } return C[n][k]; } // A utility function to return minimum of two integers static int min(int a, int b) { return (a<b)? a: b; } /* Driver program to test above function*/ public static void main(String args[]) { int n = 5, k = 2; System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k)); }
}
/*This code is contributed by Rajat Mishra*/پیاده‌سازی روش برنامه‌نویسی پویا در پایتون
# A Dynamic Programming based Python Program that uses table C[][]
# to calculate the Binomial Coefficient
# Returns value of Binomial Coefficient C(n, k)
def binomialCoef(n, k): C = [[0 for x in range(k+1)] for x in range(n+1)] # Calculate value of Binomial Coefficient in bottom up manner for i in range(n+1): for j in range(min(i, k)+1): # Base Cases if j == 0 or j == i: C[i][j] = 1 # Calculate value using previously stored values else: C[i][j] = C[i-1][j-1] + C[i-1][j] return C[n][k]
# Driver program to test above function
n = 5
k = 2
print("Value of C[" + str(n) + "][" + str(k) + "] is " + str(binomialCoef(n,k)))
# This code is contributed by Bhavya Jainپیاده‌سازی روش برنامه‌نویسی پویا در #C
// A Dynamic Programming based solution that
// uses table C[][] to calculate the Binomial
// Coefficient
using System;
class GFG { // Returns value of Binomial Coefficient // C(n, k) static int binomialCoeff(int n, int k) { int [,]C = new int[n+1,k+1]; int i, j; // Calculate value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.Min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i,j] = 1; // Calculate value using previously // stored values else C[i,j] = C[i-1,j-1] + C[i-1,j]; } } return C[n,k]; } // A utility function to return minimum // of two integers static int min(int a, int b) { return (a < b) ? a : b; } /* Driver program to test above function*/ public static void Main() { int n = 5, k = 2; Console.WriteLine("Value of C(" + n + "," + k + ") is " + binomialCoeff(n, k)); }
}
// This code is contributed by anuj_67.پیاده‌سازی روش برنامه‌نویسی پویا در PHP
<?php
// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff( $n, $k)
{ $C = array(array()); $i; $j; // Caculate value of Binomial // Coefficient in bottom up manner for ($i = 0; $i <= $n; $i++) { for ($j = 0; $j <= min($i, $k); $j++) { // Base Cases if ($j == 0 || $j == $i) $C[$i][$j] = 1; // Calculate value using // previously stored values else $C[$i][$j] = $C[$i - 1][$j - 1] + $C[$i - 1][$j]; } } return $C[$n][$k];
} // Driver Code $n = 5; $k = 2; echo "Value of C(" ,$n," ",$k, ") is"," " , binomialCoeff($n, $k) ;
// This code is contributed by anuj_67.
?>خروجی قطعه کدهای بالا، به صورت زیر است.Value of C[5][2] is 10
پیچیدگی زمانی از درجه O(n*k) و فضای کمکی از درجه O(n*k) است. در ادامه، نسخه بهینه شده فضایی از رویکرد بالا، پیاده‌سازی شده است.
پیاده‌سازی نسخه بهینه در C و ++C
// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;
int binomialCoeff(int n, int k)
{ int C[k+1]; memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal triangle using // the previous row for (int j = min(i, k); j > 0; j--) C[j] = C[j] + C[j-1]; } return C[k];
}
/* Drier program to test above function*/
int main()
{ int n = 5, k = 2; printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) ); return 0;
}پیاده‌سازی نسخه بهینه در جاوا
// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;
class GFG { static int binomialCoeff(int n, int k) { int C[] = new int[k + 1]; // nC0 is 1 C[0] = 1; for (int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous row for (int j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j-1]; } return C[k]; } /* Driver program */ public static void main(String[] args) { int n = 5, k = 2; System.out.printf("Value of C(%d, %d) is %d " , n, k, binomialCoeff(n, k)); }
}پیاده‌سازی نسخه بهینه در پایتون
# Python program for Optimized Dynamic Programming solution to # Binomail Coefficient. This one uses the concept of pascal # Triangle and less memory def binomialCoeff(n , k): # Declaring an empty array C = [0 for i in xrange(k+1)] C[0] = 1 #since nC0 is 1 for i in range(1,n+1): # Compute next row of pascal triangle using # the previous row j = min(i ,k) while (j>0): C[j] = C[j] + C[j-1] j -= 1 return C[k] # Driver Program to test the above function n = 5 k = 2 print "Value of C(%d,%d) is %d" %(n,k,binomialCoeff(n,k)) # This code is contribtued by Nikhil Kumar Singh(nickzuck_007)
پیاده‌سازی نسخه بهینه در #C
// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using System;
class GFG { static int binomialCoeff(int n, int k) { int[] C = new int[k + 1]; // nC0 is 1 C[0] = 1; for (int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for (int j = Math.Min(i, k); j > 0; j--) C[j] = C[j] + C[j-1]; } return C[k]; } /* Driver program */ public static void Main() { int n = 5, k = 2; Console.WriteLine("Value of C(" + n + " " + k + ") is " + binomialCoeff(n, k)); }
}
// This code is contribtued by anuj_67.پیاده‌سازی نسخه بهینه در PHP
<?php
// PHP program for space optimized
// Dynamic Programming Solution of
// Binomial Coefficient
function binomialCoeff($n, $k)
{ $C = array_fill(0, $k + 1, 0); $C[0] = 1; // nC0 is 1 for ($i = 1; $i <= $n; $i++) { // Compute next row of pascal // triangle using the previous row for ($j = min($i, $k); $j > 0; $j--) $C[$j] = $C[$j] + $C[$j - 1]; } return $C[$k];
}
// Driver Code
$n = 5; $k = 2;
echo "Value of C[$n, $k] is ". binomialCoeff($n, $k);
// This code is contributed by mits.
?>خروجی قطعه کدهای بالا، به صورت زیر است.Value of C[5][2] is 10
پیچیدگی زمانی این روش از درجه O(n*k) و پیچیدگی فضایی آن از درجه O(k) است. در ادامه، توصیف دقیق‌تری از آنچه در حال وقوع است را مشاهده می‌کنید.
1==========>> n = 0, C(0,0) = 1 1–1========>> n = 1, C(1,0) = 1, C(1,1) = 1 1–2–1======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1 1–3–3–1====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1 1–4–6–4–1==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1
بنابراین، در اینجا هر حلقه‌ای روی i، در واقع iاُمین سطر از مثلث خیام پاسکال را با استفاده از سطر (i-1)اُم می‌سازد.
در هر زمان، هر عنصری از آرایه C مقداری خواهد داشت (صفر یا بیشتر) و در تکرار بعدی، مقدار برای آن عناصر بر اساس تکرار قبلی به دست می‌آید. در عبارت C[j] = C[j] + C[j-1]، قسمت سمت راست معادله مقداری را نشان می‌دهد که از تکرار پیشین به دست می‌آید (یک سطر از مثلث خیام پاسکال، به سطرهای پیشین بستگی دارد). سمت راست، نشانگر مقدار تکرار کنونی است که به وسیله این عبارت به دست می‌آید. فرض می‌شود که هدف، محاسبه C(4, 3) است. این یعنی: n=4 و k=3. در همین راستا، داریم: همه عناصر آرایه C با اندازه ۴ (k+1) با صفر مقداردهی اولیه می‌شوند. یعنی:
C[0] = C[1] = C[2] = C[3] = C[4] = 0 Then C[0] is set to 1 For i = 1: C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1 For i = 2: C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1 C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2 For i=3: C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1 C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3 C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3 For i=4: C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1 C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4 C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6 C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4
C(4,3) = 4، پاسخ مثال بیان شده در بالا است. اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^
منبع GeeksforGeeks