Write a java program that, , in three different ways, calculates the binomial co

Question

Write a java program that, , in three different ways, calculates the binomial coefficients (n,k) using the recursive formula (n , k) = ( (n - 1) , k ) + ( n-1 , k-1 ) with boundary values ( n , 0 ) = 1 and (n , n) = 1 Note that (n , k) is definied for any n >= k >= 0.

Specific requirements:
1. Part (a) which is not required: Use a loop to compute (n , k).

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 (n , k) together with the number of recursive calls in each way.

Here is a sample output:

(a) Enter two integers as n and k to compute C(n,k): 10 5
(b) use complete recursion: C(10,5)=252.
The number of calls is 502.
(c) use array to store some values: C(10,5)=252.
The number of calls is 50.

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.