We want to count the number of possible paths to move from row 1, column 1 to ro

Question

We want to count the number of possible paths to move from row 1, column 1 to row N, column N in a two-dimensional grid. Steps are restricted to going up
or to the right, but not diagonally. The illustration shows three of many paths, if N = 10:

a) The following method, numPaths , is supposed to count the number of paths,
but it has some problems. Debug the method.
int numPaths(int row, int col, int n)
{
if (row == n)
return 1;
else
if (col == n)
return (numPaths + 1);
else
return (numPaths(row + 1, col) * numPaths(row, col + 1))
}

Explanation / Answer

The primary issue with this code is that we don't realize what it does. That is, the thing that does row and col need to do with a number of paths ? It appears this figures ``the number of ways from point (row,col) to (n,n)''.

There are some reasonable syntactic issues in this code.

The main call to numPaths has no parameters.

The 2nd and 3rd calls don't have n.

Be that as it may, there are additionally some semantic issues with the code.

In case you're as of now in the nth line or section, there's just a single way to (n,n), so the second return is off base. (That implies we can adjust two mistakes without a moment's delay.)
The no. of ways from (row,col) to (n,n) is ``the number of ways on the off chance that you go up first'' in addition to ``the number of ways in the event that you go right first''. The code utilizes times.

Assembling it all,

public class PathsNUM {
/**
* The no. of recursive calls.
*/
protected int calls = 0;

/**
* calculate the no. of paths from (row,col) to (n,n).
* (row,col) will not be (n,n).
*/
public int numPaths(int row, int col, int n)
{
calls++;
if (row == n)
return 1;
else if (col == n)
return 1;
else
return numPaths(row+1, col, n) + numPaths(row, col+1, n);
}

public static void main(String[] args) {
SimpleOutput out = new SimpleOutput();
int n = Integer.parseInt(args[0]);
NumPaths helper = new NumPaths();
int count = helper.numPaths(1,1,n);
out.println("There are " + count + " paths to (" + n + "," + n + ")");
out.println(" That took " + helper.calls + " calls.");
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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