C++ class
can anyone please give me an idea how to solve this problem? I am asked to write a DyckPath class. I don't need a completed class. I just need an idea to write the calc and print methods. Thanks.
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.
1. If k < 0 or k ≥ c, where c = num(m,n) is the number of Dyck paths, then do nothing.
2. 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)
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.
1. If k < 0 or k ≥ c, where c = num(m,n) is the number of Dyck paths, then do nothing.
2. 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)
Last edited on
Topic archived. No new replies allowed.