Question

Objective

To get practice in designing recursive functions and to gain experience in algorithm time efficiency.

Project Description

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 for window and timer.h for unix, MacOS, and repl.it --- change both file names to timer.h if their names are added by 1 after download ) 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.

Timer.h file:

// timer.h for CMPSC122 lab

// Measure time in Window

// Define a Timer object t, use t.start() for beginning of the algorithm, t.stop() for the ending, and t.show() for printing.

#ifndef TIMER_H

#define TIMER_H

#include <ctime>

#include <string>

#include <iostream>

using namespace std;

class Timer

{

public:

Timer();

Timer(const std::string& label);

~Timer();

void start(void);

void stop(void);

void show(void);

private:

void reset(void);

string label;

long tps;

clock_t

start_time,

end_time;

double

usertime,

systemtime,

elapsedtime,

waittime;

};

#endif

// eof timer.h

// timer.cpp

Timer::Timer()

{

label = "Process Timer";

reset();

}

Timer::Timer(const std::string& label)

{

Timer::label = label;

reset();

}

Timer::~Timer()

{

}

void

Timer::reset(void)

{

tps = CLOCKS_PER_SEC;

end_time = 0;

usertime = 0;

systemtime = 0;

elapsedtime = 0;

waittime = 0;

}

void

Timer::start(void)

{

start_time = clock();

}

void

Timer::show(void)

{

cout << " "

<< label << "\n"

<< " -------------------------------\n"

<< " Elapsed Time : "

<< elapsedtime

<< "s" << std::endl;

}

void

Timer::stop(void)

{

end_time = clock();

elapsedtime = ((double)(end_time -

start_time) / (double)tps);

if (elapsedtime < 0.001)

{

elapsedtime = 0.001;

}

if (waittime < 0.00)

{

waittime = 0.00;

}

}

// eof timer.cpp

Answer 1

#include<stdio.h>

#include<stdlib.h>

#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;

}