Write one Java Programming that calculates the binomial coefficients (nCk) using

Question

Write one Java Programming that calculates the binomial coefficients (nCk) using the recursive formula

(nCk)=((n-1)Ck)+((n-1)C(k-1)) with boundary values (nC0)=1 and (nCn)=1. Note that (nCk) is defined for any n>=k>=0.

Some Requirements

1. Part (a), which is not required: Use a loop to compute nCk

2.. In Part (b), you should use pure recursive calls completely and count the number of calls the program makes. You should count how many times recursive calls were made.

3. Part (c) is considered to be an improved version of Part (b). You may use an array (2-dimessional) to store some values that has been computed during the run so that when making recursive calls the program does not compute certain values over and over again.

4. Prompt user to enter two integers as n and k. Report the values of nCk together with the number of recursive calls in each way. Here is a sample output:

Explanation / Answer

import java.util.*;
public class bionomial
{
public static int pure_rec_calls = 0;
public static int array_rec_calls = 0;
private static int[][] array = new int[100][100];
public static int recursion_pure(int n,int k)
{
pure_rec_calls++;
if(k==0 || n==k) return 1;
else return recursion_pure(n-1,k) + recursion_pure(n-1,k-1);
}
public static int recursion_array(int n,int k)
{
array_rec_calls++;
if(array[n][k]!=0)
return array[n][k];
if(k==0 || n==k) return 1;
else
{
array[n][k] = recursion_array(n-1,k)+ recursion_array(n-1,k-1);
return array[n][k];
}
}
public static void main(String[] args)
{
int n,k;
Scanner in = new Scanner(System.in);
System.out.println("Enter two integers as n and k to compute C(n,k): ");
n = in.nextInt();
k = in.nextInt();
System.out.println("use complete recursion: C("+n+","+k+")="+recursion_pure(n,k));
System.out.println("        The number of calls is "+(pure_rec_calls-1));
System.out.println("use array to store some values: C("+n+","+k+")="+recursion_array(n,k));
System.out.println("        The number of calls is "+(array_rec_calls-1));
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.