Objective: To get practice in designing recursive functions and to gain experien
ID: 666297 • Letter: O
Question
Objective:
To get practice in designing recursive functions and to gain experience in algorithm time efficiency.
Project DescriptionConsider 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:
------------------------------------------------------------------------------------------------------------------------------------------------------
the timer.h file -
Explanation / Answer
Answer:
#include<iostream>
#include<timer.h>
using namespace std;
int pathCount1(int x1, int y1, int EndX1, int EndY1)
{
int total1= 0;
if(x1 == EndX1 && y1 == EndY1)
{
return 1;
}
if(x1 != EndX1)
{
total1 += pathCount1(x1+1,y,EndX1,EndY1);
}
if(y1!= EndY1)
{
total1+= pathCount1(x1,y1+1,EndX1,EndY1);
}
return total1;
}
int main()
{
int North, East;
char userInput = 'y';
while(userInput == 'Y' || userInput == 'y'){
cout << "HOW MANY POINTS NORTH OF A IS B? ";
cin >> North;
cout << "HOW MANY POINTS EAST OF A IS B? ";
cin >> East;
cout<< "THERE ARE ";
start();
cout << pathCount1(0,0,North,East);
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 >> userInput1;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.