dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

Driver.java (3082B)

      1 package lab7;
      2 
      3 import java.util.Scanner;
      4 
      5 public class Driver {
      6 
      7     Scanner in = new Scanner(System.in);
      8 
      9     public static void main (String args[]) {
     10         Driver binomial= new Driver();
     11         int n = 6;
     12         int k = 4;
     13 
     14         System.out.print("Enter n ");
     15         n = binomial.getInput();
     16         System.out.print(n);
     17         System.out.println();
     18 
     19         System.out.print("Enter k ");
     20         k = binomial.getInput();
     21         System.out.print(k);
     22         System.out.println();
     23         System.out.println();
     24 
     25         System.out.println(binomial.recursiveBinomial(n, k));
     26         binomial.displayTriangle(n+1);
     27         System.out.println(binomial.iterativeBinomial(n+1, k+1));
     28         System.out.println(binomial.formulaBinomial(n, k));
     29     }
     30 
     31     public int recursiveBinomial(int n, int k) {
     32         int result;
     33 
     34         if (k == n || k == 0) {
     35             result = 1;
     36         }
     37         else {
     38             result = recursiveBinomial(n - 1, k - 1) + recursiveBinomial(n - 1, k);
     39         }
     40         return result;
     41     }
     42 
     43     public int iterativeBinomial(int n, int k) {
     44         int[][] pascal  = new int[n +1][];
     45         pascal[1] = new int[1 + 3];
     46         pascal[1][1] = 1;
     47         for (int i = 2; i <= n; i++) {
     48             pascal[i] = new int[i + 2];
     49             for (int j = 1; j < pascal[i].length - 1; j++) {
     50                 pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
     51             }
     52         }
     53         // System.out.println(pascal[n][k]);
     54         return pascal[n][k];
     55     }
     56 
     57     public int formulaBinomial(int n, int k) {
     58         int result;
     59         int top = 1;
     60         int bot = 1;
     61         if (n - k > k) {
     62             for (int i = (n-k+1); i <= n; i++) {
     63                 top *= i;
     64             }
     65             //System.out.println(top);
     66             for (int i = 1; i <= k; i++ ) {
     67                 bot *= i;
     68             }
     69             //System.out.println(bot);
     70             result = top/bot;
     71             return result;
     72         }
     73         else {
     74             for (int i = (k+1); i <= n; i++) {
     75                 top *= i;
     76 
     77             }
     78             for (int i = 1; i <= (n-k); i++) {
     79                 bot *= i;
     80             }
     81             result = top/bot;
     82             return result;
     83         }
     84     }
     85 
     86     public void displayTriangle(int n) {
     87         int[][] pascal  = new int[n +1][];
     88         pascal[1] = new int[1 + 2];
     89         pascal[1][1] = 1;
     90         for (int i = 2; i <= n; i++) {
     91             pascal[i] = new int[i + 2];
     92             for (int j = 1; j < pascal[i].length - 1; j++) {
     93                 pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
     94             }
     95         }
     96         for (int i = 1; i <= n; i++) {
     97             for (int j = 1; j < pascal[i].length - 1; j++) {
     98                 System.out.print(pascal[i][j] + " ");
     99             }
    100             System.out.println();
    101         }
    102     }
    103 
    104     public int factorial(int n) {
    105         int result = 1;
    106         for (int i = 1; i <=n; i++) {
    107             result *= i;
    108         }
    109         return result;
    110     }
    111 
    112     public int getInput() {
    113         int userIn = Integer.parseInt(in.nextLine());
    114         return userIn;
    115     }
    116 }