Results 1 to 10 of 10
  1. #1
    pheonix is offline Member
    Join Date
    Apr 2008
    Posts
    42
    Rep Power
    0

    Default 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

    please help.

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  3. #3
    CJSLMAN's Avatar
    CJSLMAN is offline Moderator
    Join Date
    Oct 2008
    Location
    Mexico
    Posts
    1,159
    Rep Power
    7

    Default What board...

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

    CJSL
    Chris S.
    Difficult? This is Mission Impossible, not Mission Difficult. Difficult should be easy.

  4. #4
    pheonix is offline Member
    Join Date
    Apr 2008
    Posts
    42
    Rep Power
    0

    Default

    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 :(

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  6. #6
    pheonix is offline Member
    Join Date
    Apr 2008
    Posts
    42
    Rep Power
    0

    Default

    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 :) ?

  7. #7
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    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.

  8. #8
    pheonix is offline Member
    Join Date
    Apr 2008
    Posts
    42
    Rep Power
    0

    Default

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

  9. #9
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java 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);
    }

  10. #10
    pheonix is offline Member
    Join Date
    Apr 2008
    Posts
    42
    Rep Power
    0

Similar Threads

  1. help with recursion
    By Nari in forum New To Java
    Replies: 15
    Last Post: 04-24-2008, 09:13 AM
  2. recursion
    By kdeighan in forum New To Java
    Replies: 3
    Last Post: 01-25-2008, 09:48 PM
  3. Recursion
    By bozovilla in forum Advanced Java
    Replies: 3
    Last Post: 01-07-2008, 04:53 PM
  4. recursion
    By ravian in forum New To Java
    Replies: 2
    Last Post: 12-03-2007, 05:15 PM
  5. Help with recursion
    By scts102 in forum New To Java
    Replies: 1
    Last Post: 11-19-2007, 10:07 PM

Posting Permissions

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