The Problem You must write a program that will compute the minimum cost path thr
ID: 3724903 • Letter: T
Question
The Problem You must write a program that will compute the minimum cost path through a matrix of integers. For this assignment, you must make use of recursion for all of your repetition. i.e.you may not use any for, while, or do-while loops in your program Background A matrix of integers is represented in a computer as a 2-D array of integers. The path will start in column 0 (the first column) and consists of a sequence of steps terminating in column x(the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. Legal steps are illustrated below. The cost of a path is the sum of the integers in each of the n cells of the matrix that are visited. For example in the matrix shown below the path with minimum cost is 15 and is show: 3 4 1 2 8 6Explanation / Answer
This is the logic i have used:-
The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1). So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n].I have only printed the minimum cost as printing the paths was slightly complex in this logic.
-----------------program in c----------
#include<stdio.h>
#include<limits.h>
#define R 3
#define C 3
int min(int x, int y, int z);
/* Returns cost of minimum cost path from (0,0) to (m, n) in mat[R][C]*/
int minCost(int cost[R][C], int m, int n)
{
if (n < 0 || m < 0)
return INT_MAX;
else if (m == 0 && n == 0)
return cost[m][n];
else
return cost[m][n] + min( minCost(cost, m-1, n-1),
minCost(cost, m-1, n),
minCost(cost, m, n-1) );
}
/* A utility function that returns minimum of 3 integers */
int min(int x, int y, int z)
{
if (x < y)
return (x < z)? x : z;
else
return (y < z)? y : z;
}
/* Driver program to test above functions */
int main()
{
int cost[R][C] = { {1, 2, 3},
{4, 8, 2},
{1, 5, 3} };
printf(" %d ", minCost(cost, 2, 2));
return 0;
}
Output--8
------------------program in python---------------
R = 3
C = 3
import sys
# Returns cost of minimum cost path from (0,0) to (m, n) in mat[R][C]
def minCost(cost, m, n):
if (n < 0 or m < 0):
return sys.maxsize
elif (m == 0 and n == 0):
return cost[m][n]
else:
return cost[m][n] + min( minCost(cost, m-1, n-1),
minCost(cost, m-1, n),
minCost(cost, m, n-1) )
#A utility function that returns minimum of 3 integers */
def min(x, y, z):
if (x < y):
return x if (x < z) else z
else:
return y if (y < z) else z
# Driver program to test above functions
cost= [ [1, 2, 3],
[4, 8, 2],
[1, 5, 3] ]
print(minCost(cost, 2, 2))
R = 3
C = 3
import sys
# Returns cost of minimum cost path from (0,0) to (m, n) in mat[R][C]
def minCost(cost, m, n):
if (n < 0 or m < 0):
return sys.maxsize
elif (m == 0 and n == 0):
return cost[m][n]
else:
return cost[m][n] + min( minCost(cost, m-1, n-1),
minCost(cost, m-1, n),
minCost(cost, m, n-1) )
#A utility function that returns minimum of 3 integers */
def min(x, y, z):
if (x < y):
return x if (x < z) else z
else:
return y if (y < z) else z
# Driver program to test above functions
cost= [ [1, 2, 3],
[4, 8, 2],
[1, 5, 3] ]
print(minCost(cost, 2, 2))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.