Results 1 to 10 of 10
Thread: Please help with recursion
 12242008, 02:58 PM #1Member
 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.length1){
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
please help.
 12242008, 06:06 PM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,371
 Blog Entries
 1
 Rep Power
 20
Can you explain your question much simpler way. Reading such a long post get board on me lol.
 12242008, 06:11 PM #3
What board...
In the board shown above, ...
CJSLChris S.
Difficult? This is Mission Impossible, not Mission Difficult. Difficult should be easy.
 12252008, 12:12 PM #4Member
 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 :(
 12252008, 03:06 PM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,371
 Blog Entries
 1
 Rep Power
 20
Can you write down all possible scenarios according to your number sequence.
 12252008, 05:00 PM #6Member
 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 :) ?
 12262008, 01:02 AM #7Java Code:
public static int Calc(int[] a,int i){ if(i==a.length1){ return a[i]; }
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.
 12262008, 11:12 AM #8Member
 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.
 12262008, 10:01 PM #9Java Code:
int getCost(int[] array, int index, int totalCost) { if index == last array index return totalCost + last array element; 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); }
 12272008, 12:41 PM #10Member
 Join Date
 Apr 2008
 Posts
 42
 Rep Power
 0
Similar Threads

help with recursion
By Nari in forum New To JavaReplies: 15Last Post: 04242008, 09:13 AM 
recursion
By kdeighan in forum New To JavaReplies: 3Last Post: 01252008, 10:48 PM 
Recursion
By bozovilla in forum Advanced JavaReplies: 3Last Post: 01072008, 05:53 PM 
recursion
By ravian in forum New To JavaReplies: 2Last Post: 12032007, 06:15 PM 
Help with recursion
By scts102 in forum New To JavaReplies: 1Last Post: 11192007, 11:07 PM
Bookmarks