java: //counting the number of possible paths to move from row 1 column 1 to row
ID: 3770379 • Letter: J
Question
java:
//counting the number of possible paths to move from row 1 column 1 to row n column n
//in a two dimension grid.
import java.util.*;
public class Lab4
{
int numPaths (int row, int col, int n)
{
if (row >= n || col >= n)
return 1;
else
return (numPaths(row + 1, col, n) + numPaths(row, col + 1, n));
}
public static void main(String [] args)
{
Scanner input = new Scanner(System.in);
int n;
System.out.print("Please enter a number: ");
n = input.nextInt();
Lab4 paths = new Lab4();
int count = paths.numPaths(1,1,n);
System.out.println("There are " + count + " paths to row " + n + ", column " + n + ".");
System.out.println();
}
}
a) Excecuting n = 4 in the above codeis not efficient . The efficiency of this operation can be improved by keeping intermediate values of numPaths in a two dimension array of interger values. this approach keeps the method from having to recalculate values that it has already done.Design and code a version of numPaths that uses this approach.
b) show an invocation of the version of numPaths in part c, including any array initialization necessary.
c) how do the two versions of numpaths compare in terms of time and space efficiency?
Explanation / Answer
import java.util.*;
public class Lab4
{
int pathsValue[][];
int numPaths (int row, int col, int n)
{
if (row >= n || col >= n)
return 1;
else if(pathsValue[row][col] > 0)
return pathsValue[row][col];
else{
int value = (numPaths(row + 1, col, n) + numPaths(row, col + 1, n));
pathsValue[row][col] = value;
return value;
}
}
public static void main(String [] args)
{
Scanner input = new Scanner(System.in);
int n;
System.out.print("Please enter a number: ");
n = input.nextInt();
Lab4 paths = new Lab4();
int count = paths.numPaths(1,1,n);
System.out.println("There are " + count + " paths to row " + n + ", column " + n + ".");
System.out.println();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.