1. Binomial coefficients (n m) = n!/m!(n - m) are defined for all integers n geq
ID: 649492 • Letter: 1
Question
1. Binomial coefficients (n m) = n!/m!(n - m) are defined for all integers n geq 0 and 0 leq m leq n. With the definition b(n, m) = (n m ), the recurrence b(n, m) = b(n - 1, m - 1) + b(n - 1, in), for all integers n geq 1 and 0 leq m leq n - 1 along with base cases b(n,n) = 1 for all n geq 0; b(n,0) = 1 for all n geq 0. define b(n, m). The base cases and recurrence are illustrated in the figure below. (a) Write pseudocode for an iterative algorithm to calculate b(n, m) for arbitrary integers n geq 0 and 0 leq m leq n. A doubly-nested For-Loop is recommended, with indexes i and j for calculating b(I, j). (b) Write pseudocode for a recursive algorithm to calculate b(n, m) for arbitrary integers n geq 0 and 0 geq m leq n.Explanation / Answer
ITERATIVE
int bnm(int n, int n)
{
int a[n+1][m+1];
a[1][1]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(j==0)
a[i][j] = 1;
else if(i==j)
a[i][j]=1;
else if(i<j)
a[i][j]=0;
else
a[i][j] = a[i-1][j-1]+a[i-1][j];
}
}
return a[n][m];
}
reccursive
int bnm(int n, int m)
{
if((n==m) || (m==0))
return 1;
if (m > n )
return 0;
//else
return bnm(n-1,m-1)+bnm(n-1,m)
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.