C++

Function with polymorphic input

You are given the following function, which uses a polymorphic abstract class Base.

 class Base { public: 

 virtual int calc(int m, int n) = 0; 

 virtual void print(int k) {} }; 

 void poly_calc(Base &b, int m, int n) { 

 int num = b.calc(m, n); 

 for (int i = 0; i < num; ++i) { b.print(i); 

}

cout<<"number=" << m << " " << n << " " << num << endl;

 cout << endl; } 

Derived classes will be specified below.

A main program will instantiate objects and call poly calc.

-----------------------------

1.2 Class Binom

Write a class Binom which derives from Base.

The class Binom overrides the virtual method calc.

The class Binom does not override the virtual method print.

The method calc calculates the value of the binomial coefficient:

(m/n) = ( ( m! ) / (n! (m-n))!) EQUATION (1.1)

1. Return 0 if m<0. 2. Return 0 if n>m. 3. Return 1 if n = 0 or n=m. 4. Else calculate the binomial coefficient given in eq. (1.1). 5. Do not worry about problems of overflow. 6. You may assume the input values of m and n will not cause the result to overflow.

--------------------------------

1.3 Class DyckPath

A Dyck path is a path on an integer grid (i,j) with the following properties.

1. The path passes through points with integer coordinates (i,j) only. 2. The path begins at the origin (0, 0). 3. The path ends at the point (m, n), where m 0 and n 0 are both nonnegative integers.

4. At every step, the path moves one unit to the right (i i+1) or one unit up (j j+1).

5. Diagonal steps or backward steps or downward steps are not allowed.

6. The path can touch but cannot cross above the line y = nx/m, i.e. my nx or mj ni.

7. Therefore the allowed values of i and j are i 0, j 0, i m, j n and mj ni.

A graph of all Dyck paths for m = 2 and n = 4 is displayed in Fig. 1. There are three paths.

A graph of a sample (not all) Dyck paths for m = 4 and n = 4 is displayed in Fig.2.

Write a class DyckPath which derives from Base.

The class DyckPath overrides both the virtual methods calc and print.

The method calc calculates the number of Dyck paths for the inputs m and n. Return 0 if m 0 or n 0.

The method print displays the Dyck path indexed by k as follows.

If k < 0 or k c, where c = num(m,n) is the number of Dyck paths, then do nothing.

Else suppose the coordinates of the points in the path k are (ik,0,jk,0),...,(ik,m+n,jk,m+n). Clearly a Dyck path has m+n+1 points (m horizontal steps and n vertical steps, hence m + n total steps, plus the origin). Print the output on a line in the following format.

(ik,0,jk,0) (ik,1,jk,1) (ik,2,jk,2) ... (ik,m+n,jk,m+n)

The class DyckPath must therefore store the paths calculated in the method calc.

Declare suitable data members (as private data) in the class DyckPath to store the relevant data.

Write any additional class methods you require to perform the necessary calculations.

Any additional methods you write must be private.

You may also write additional helper classes to assist in your calculations.

For large values of m and n the total number of Dyck paths is large. Do not worry about overflow. You may assume your code will be called with input values that do not cause overflow.