Question

note: USE C++ WITH USER DEFINED FUNCTIONS AND RECURSIVE FUNCTION ONLY. No C++ library function is allowed.

The game of “Jump It” consists of a board with n positive integers in a row, except for the first
column, which always contains zero. These numbers represent the cost to enter each column.
Here is a sample game board where n is 6:
0 3 80 6 57 10
The object of the game is to move from the first column to the last column with the lowest total
cost.
The number in each column represents the cost to enter that column. You always start the game
in the first column and have two types of moves. You can either move to the adjacent column or
jump over the adjacent column to land two columns over. The cost of a game is the sum of the
costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the first column,
our cost so far is 0. We could jump to 80, then jump to 57, and then move to 10 for a total cost
of 80 + 57 + 10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to
10, for a total cost of 3 + 6 + 10 = 19.

Write a recursive function that solves this problem and returns the lowest cost of a game board
represented and passed as an array.

Note: your function shouldn’t output the actual sequence of jumps, only the lowest cost of this
sequence.

IMPORTANT: Use only user defined functions. No C++ library function is allowed. Please write it in a simple and elementary way.

Answer 1

// you have to pass size because we are not using STL LIBRARAY HERE
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int lowestCost(int board[],int current,int total,int size,int size2) {
total+=board[current];
if(current == size -1)
return total;
else if(current == size -2)
return lowestCost(board,current+1,total,size, size2);
else
{
int path1 = lowestCost(board,current+1,total,size,size2);
int path2 = lowestCost(board,current+2,total,size,size2);
// Use math library to return minimum of the paths
if(path1> path2){
return path2;
}
else {
return path1;
}

}
}
int main()
{
int size=6;
int *board= new int[size];
// SETTING VALUES FOR RUNNING CODE YOU CAN USE LOOP TO INPUT
board[0]=0;
board[1]=3;
board[2]=80;
board[3]=6;
board[4]=59;
board[5]=10;
int size2=8;
int cost = 0;
cost = lowestCost(board,0,cost,size,size2);
// For smaller board
for(int i=0;i < 6;i++)
cout<<board[i]<<" ";
cout<<endl;
cout<<"Least steps: " <<cost;
cout<<endl;

int *board2= new int[size2];
board2[0]=0;
board2[1]=5;
board2[2]=17;
board2[3]=29;
board2[4]=61;
board2[5]=53;
board2[6]=100;
board2[7]=2;
int cost2 = 0;
cost2 = lowestCost(board2,0,cost2,size,size2);
for(int i=0;i < 8;i++)
cout<<board2[i]<<" ";
cout<<endl;
cout<<"Least steps: " <<cost2;
}

OUTPUT:

IF YOU HAVE ANY QUERY PLEASE COMMENT DOWN BELOW

PLEASE GIVE A THUMBS UP