Consider a network of streets laid out in a rectangular grid, for example In a n

Question

Consider a network of streets laid out in a rectangular grid, for example

In a northeast path from one point in the grid to another, one may walk only to the north (up) and to the east (right). For example, there are four northeast paths from A to B in the preceding grid:

Write a program that must use a recursive function to count the number of northeast paths from one point to another in a rectangular grid. Your program should prompt user to input the numbers of points to north and to east respectively, and then output the total number of paths.

Notes:

1.Here is a file (timer.h) which should be included in your program to measure time in Window or Unix (includes Mac OS and Linux) systems (use start() for beginning of the algorithm, stop() for the ending, and show() for printing).

2. The computing times of this algorithm is very high, and the number of paths may be overflow, don't try input numbers even over 16.

3. Please paste your output as comments at the bottom of your file.

Sample Run

How many points north of A is B? 2

How many points east of A is B? 3

There are 10 northeast paths between A and B.

Process Timer
-------------------------------
Elapsed Time : 0.01s

Enter y or Y to continue next example or any other letter to exit: y

How many points north of A is B? 12

How many points east of A is B? 14

There are 9657700 northeast paths between A and B.

Process Timer
-------------------------------
Elapsed Time : 1.081s

Enter y or Y to continue next example or any other letter to exit: y

How many points north of A is B? 16

How many points east of A is B? 16

There are 601080390 northeast paths between A and B.

Process Timer
-------------------------------
Elapsed Time : 62.79s

Enter y or Y to continue next example or any other letter to exit:

Explanation / Answer

#include <iostream>
#include <timer.h>
using namespace std;

int pathCount(int x, int y, int EndX, int EndY){
    int total = 0;
    if(x == EndX && y == EndY){
         return 1;
    }
    if(x != EndX){
         total += pathCount(x+1,y,EndX,EndY);
    }
    if(y != EndY){
         total += pathCount(x,y+1,EndX,EndY);
    }
    return total;
}  

int main()
{
    int N, E;
    char userInput = 'y';
    while(userInput == 'Y' || userInput == 'y'){
      cout << "How many points North of A is B? ";
      cin >> N;
      cout << "How many points East of A is B? ";
      cin >> E;
      cout << "There are ";
      start();
      cout << pathCount(0,0,N,E);
      stop();
      cout << " Northeast paths between A and B." << endl;
      cout << "Process Timer" << endl;
      cout << "----------------------------" << endl;
      cout << "Elapsed Time: ";
      show();
      cout << endl << "Enter y or Y to continue next example or any other letter to exit: ";
      cin >> userInput;
    }
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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