Fonction récursive de l'oeuf de Pâques sur java

Question

On m'a confié une tâche pour une tâche en java, il s'agit d'un jeu d'oeuf de Pâques qui commence quand je vous donne n oeufs, et il se termine quand vous avez exactement m oeufs. A n'importe quel stade du jeu, disons qu'il vous reste des œufs, vous pouvez alors en restituer quelques-uns, mais vous devez respecter les règles suivantes:

• Si n est pair, vous pouvez rendre exactement n/2 des œufs.

• Si n est divisible par 3 ou 4, alors vous pouvez multiplier les deux derniers chiffres de n et redonner beaucoup d'oeufs.

• Si n est divisible par 5, alors vous pouvez donner exactement m œufs.

• Si n est un nombre premier, alors vous pouvez donner exactement un oeuf.

Je dois écrire une fonction appelée pique-nique qui retournera vrai si en appliquant les règles dans un certain ordre nous avons exactement m oeufs à gauche; sinon false:

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

avec cette mes tâches sont:

a) Fournir les relations de récurrence pour pique-nique (int n, int m)

b) Mettre en œuvre une fonction récursive en Java en utilisant la récurrence relations

c) Développer l'ensemble arbre d'appel récursif pour pique-nique (250, 42)

d) Quel est le modèle de récursion ici? (queue récursive ou non? tree ou récursive linéaire?)

e) Cette fonction rappelle-t-elle une stratégie de conception d'algorithme? Si oui, lequel?

Je l'ai déjà fait la question a) à ce que la réponse:

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

Et je ne suis pas sûr de savoir comment mettre en œuvre la fonction récursive. J'ai essayé plusieurs fois mais toujours rien.

Question b et c sont mes plus grands problèmes atm, et je «suis sûr que je peux comprendre d et e. Quelqu'un pourrait-il s'il vous plaît me aider? Possible et me montrer comment il peut être mis en œuvre? Vous

Answer 1

avoir à:

Créer une énumération représentant vos différentes règles (il y en a 4: p).Permet admettez que vous nommez votre énumération ERule

créer une fonction récursive avec args

• œufs restants (== initialement n)
• m

Les conditions de sortie de la fonction récursive beeing:

• n = m (true)
• n < m (false)
• aucune règle ne peut appliquer à n (false)

si les conditions de sortie ne sont pas remplies, il suffit d'appeler la fonction récursive pour chaque règle qui peut être aplied à n courant (appelez-le sur la valeur n modifiée, en fonction de la condition que vous testez). Et le résultat est une instruction OR sur tous les résultats.

Answer 2

Dans Récurrence Relation, nous n'avons pas besoin de définir la classe et les méthodes comme vous l'avez mentionné dans votre question. C'est une récursivité d'arbre et non une récursion de queue. Et cette fonction nous rappelle la stratégie de conception de Backtracking.

pour la partie b) ma solution est simple et force brute.

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