در این مطلب، روش نوشتن برنامه محاسبه ضریب دو جمله ای یا در واقع، تابعی که دو پارامتر 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;
// Retus value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
// Base Cases
if (k == 0 || k == n)
retu 1;
// Recur
retu 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);
retu 0;
}
// This is code is contributed by rathbhupendra
پیادهسازی روش بازگشتی در C
// A Naive Recursive Implementation
#include<stdio.h>
// Retus value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
retu 1;
// Recur
retu 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));
retu 0;
}پیادهسازی روش بازگشتی در جاوا
// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;
class GFG {
// Retus value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
// Base Cases
if (k == 0 || k == n)
retu 1;
// Recur
retu 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 Aav Kr. Mandal.
پیادهسازی روش بازگشتی در پایتون
# A naive recursive Python implementation
def binomialCoeff(n , k):
if k==0 or k ==n :
retu 1
# Recursive Call
retu 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 {
// Retus value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
// Base Cases
if (k == 0 || k == n)
retu 1;
// Recur
retu 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)
// Retus value of
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
// Base Cases
if ($k==0 || $k==$n)
retu 1;
// Recur
retu 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
// retus minimum of two integers
int min(int a, int b);
// Retus 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];
}
}
retu C[n][k];
}
// A utility function to retu
// minimum of two integers
int min(int a, int b)
{
retu (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 retus minimum of two integers
int min(int a, int b);
// Retus 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];
}
}
retu C[n][k];
}
// A utility function to retu minimum of two integers
int min(int a, int b)
{
retu (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) );
retu 0;
}
پیادهسازی روش برنامهنویسی پویا در جاوا
// A Dynamic Programming based solution that uses table C[][] to
// calculate the Binomial Coefficient
class BinomialCoefficient
{
// Retus 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];
}
}
retu C[n][k];
}
// A utility function to retu minimum of two integers
static int min(int a, int b)
{
retu (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
# Retus 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]
retu 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 {
// Retus 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];
}
}
retu C[n,k];
}
// A utility function to retu minimum
// of two integers
static int min(int a, int b)
{
retu (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
// Retus 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];
}
}
retu $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];
}
retu 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) );
retu 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];
}
retu 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
retu 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];
}
retu 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];
}
retu $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