CODEWITHSUNDEEP
javaalgorithmrecursiontail-recursionrecurrence
LearningToProgram
LearningToProgram

Reputation: 13

Easter egg recursive function on java

I was given a task for an assignment in java, it involves a Easter Egg game that starts when I give you n eggs, and it ends when you have exactly m eggs left. At any stage of the game, let’s say you have n eggs left, then you can give back some eggs, but you must follow the rules below:

• If n is even, then you may give back exactly n/2 eggs.

• If n is divisible by 3 or 4, then you may multiply the last two digits of n and give back this many eggs.

• If n is divisible by 5, then you may give back exactly m eggs.

• If n is a prime number, then you may give back exactly one egg.

I have to write a function called picnic which will return true if by applying the rules in some order we have exactly m eggs left; false otherwise:

public static boolean picnic(int n, int m) { … }

with this my tasks are:

a) Provide the recurrence relations for picnic(int n, int m)

b) Implement a recursive function in Java using the recurrence relations

c) Develop the full recursive call tree for picnic(250, 42)

d) What is the pattern of recursion here? (tail recursive or not? tree or linear recursive?)

e) Does this function remind of any algorithm design strategy? If so, which one?

I have already done question a) with this as the answer:

public class EasterEggs {   
    public static boolean picnic (int n, int m) {
        if (n == m)
        return true;
        else return (picnic(n,m));
    }
}

And I'm not sure how to implement the recursive function. I attempted few times but still nothing.

Question b and c are my biggest issues atm, and I"m sure I can figure out d and e. Could anyone please help me with this? and possible show me how it can be implemented?

Upvotes: 1

Views: 1006

Answers (3)

Addisu Dessalegn
Addisu Dessalegn

Reputation: 3

It's the best function to return the given array is divisible or not

/* sample data

  • {3, 3, 6, 36} 3
  • {4} 2
  • {3, 4, 3, 6, 36} 3
  • {6, 12, 24, 36} 12
  • {} */

public class IsDivisible {

public static void main(String[] args) {

    int[] sampleData = { 3, 3, 6, 36 };
    int divisible = 3;

    int result = isDivisible(sampleData, divisible);
    System.out.println(result);

}

static int isDivisible(int[] givenArray, int isDivisible) {

    for (int i = 0; i < givenArray.length; i++) {

        if ((givenArray[i] % isDivisible) != 0) {

            return 0;

        }
    }

    return 1;
}

}

Upvotes: 0

nishant10
nishant10

Reputation: 46

In Recurrence Relation we do not have to define class and methods as you mentioned in your question. This is an tree recursion and not an tail recursion. And this function reminds us of Backtracking design strategy.

for part b) my solution is simple and brute force. 

public class EasterEggs {   
    public static boolean picnic (int n, int m) {
      if (n == m)
        return true;
      if(n < m)
        return false;

      boolean result = false;

      if(n%2 == 0)
         result = picnic(n-n/2,m);
      if((n%3 == 0 || n%4 == 0) && (result == false))
         result = picnic(n-lastTwoDigitMultiply(n),m);
      if(n%5 == 0 && (result == false))
         result = picnic(n-m,m);
      if(isPrime(n) && (result == false))
         result = picnic(n-1,m);

      return result;  
    }
}

Upvotes: 1

Ji aSH
Ji aSH

Reputation: 3457

You have to:

Create an enumeration representing your different rules (there are 4 of them :p). Lets admit you name your enumeration ERule

create a recursive function with args

  • remaining eggs (initially == n)
  • m

The exit conditions for the recursive function beeing:

  • n = m (true)
  • n < m (false)
  • no rule can apply to n (false)

if the exit conditions are not met, then simply call the recursive function for each rule that can be aplied to current n (call it on the modified n value, depending on the condition you test). And the result is an OR statement on all the results.

Upvotes: 0

Related Questions