1. Member Join Date
Apr 2008
Posts
42
Rep Power
0

## Please help with recursion

Hey guys ... This is basically what im trying to do .

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:

The object of the game is to move from the first column to the last column in 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, 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 solution to this problem that computes the cheapest cost of the game and outputs this value for an arbitrarily large game board represented as an array. Your program doesnt have to output the actual sequence of jumps, only the cheapest cost of this sequence. After making sure that your solution works on small arrays, test your solution on boards of larger and larger values of n to get a feel for how efficient and scalable your solution is.

and here is where I got in the recursive phase

public static int Calc(int[] a,int i){
if(i==a.length-1){
return a[i];
}

else{
//System.out.print(Math.min(a[i],a[i+1])+"+");
return Math.min(a[i],a[i+1])+Calc(a,i+1);

}

I just dont know what im doing wrong !!!?? it keeps adding the same element  Reply With Quote

2. ## Can you explain your question much simpler way. Reading such a long post get board on me lol.  Reply With Quote

3. ## What board...

In the board shown above, ...
What board? Don't see any board.

CJSL  Reply With Quote

4. Member Join Date
Apr 2008
Posts
42
Rep Power
0

## Sorry ,, it didnt get copied :P .. the board is just an array of 6 blocks with the number zero as the first number and the other numbers are at random. Anyway, I can only jump one or two blocks and I have to find the smallest values and add them .. for example .. 0 , 1 ,4 ,2 6 ,76 :
I can only move either from 0 to 1 or from 0 to 4 and then lets say from 1 to 4 or 1 to 2.. until i reach the last number and add it. in this case i am supposed to add 1+2+76 because i need to get the least sum as possible. << this is the simplest way i can explain it :(  Reply With Quote

5. ## Can you write down all possible scenarios according to your number sequence.  Reply With Quote

6. Member Join Date
Apr 2008
Posts
42
Rep Power
0

## The program HAS to find the minimum numbers to add with he final number. So there is supposed to be only one way.

0 1 5 3 6 8 << this is the board. The program HAS to calculate it this way 1+3+8 .. because it is less than 1+3+6+8 The rules are that the program can only jump one block or 2 blocks. so it can go to 1 or 5 when we start from 0. but since 1 is less than 5 it will go to 1. Then when we r at 1 it can either go to 5 or 3, but since 3 is less than 5 it will add 1+3 and now we are at block containing the number 3. since it can move to 6 or 8 but because 8 is the last block then it will add 1+3+8 and we skip 6. even thought 6 is less than 8 because we want the minimum sum. so 1+3+8 is less than 1+3+6+8 did u get it now :) ?  Reply With Quote

7. ## Java Code:
```public static int Calc(int[] a,int i){
if(i==a.length-1){
return a[i];
}```
This will return the last array element when you reach the end of the array.
What you want is to add the cost (last element) to the ongoing/total cost and return the totalCost.
To do this you will need to pass the totalCost along as a method parameter.  Reply With Quote

8. Member Join Date
Apr 2008
Posts
42
Rep Power
0

## Thanx, but I already did that, but I couldnt figure out how to add the cheapest cost.  Reply With Quote

9. ## Java Code:
```int getCost(int[] array, int index, int totalCost) {
if index == last array index

if we can advance one more index in the array
cost = array element at index +1

if we can advance two more indices in the array
next cost = array element at index +2
// Since we're here we have two options to
// choose from so:
pick the lower cost
and the index of the lower cost

print lower cost and its index in the array

// In recursion you add values on the fly:
return getCost(array, new index, totalCost + new cost);
}```  Reply With Quote

10. Member Join Date
Apr 2008
Posts
42
Rep Power
0

## Thanx a lot  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•