Easter Egg rekursive Funktion auf Java

Question

Ich bekam eine Aufgabe für eine Aufgabe in Java, es beinhaltet ein Osterei Spiel, das beginnt, wenn ich dir n Eier gebe, und es endet, wenn Sie genau m Eier übrig haben. In jedem Stadium des Spiels, lassen Sie uns sagen, Sie haben noch n Eier, dann können Sie einige Eier zurückgeben, aber Sie müssen die folgenden Regeln befolgen:

• Wenn n gerade ist, dann können Sie genau n/2 zurückgeben Eier.

• Wenn n durch 3 oder 4 teilbar ist, dann können Sie die letzten beiden Ziffern von n multiplizieren und diese viele Eier zurückgeben.

• Wenn n durch 5 teilbar ist, können Sie genau m Eier zurückgeben.

• Wenn n eine Primzahl ist, können Sie genau ein Ei zurückgeben.

Ich muss eine Funktion namens Picknick schreiben, die wahr zurückgibt, wenn durch die Anwendung der Regeln in einer bestimmten Reihenfolge haben wir genau m Eier übrig; andernfalls false:

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

mit diesen meinen Aufgaben sind:

a) die Rekurrenzrelationen für Picknick (int n, int m) Geben Sie

b) eine rekursive Funktion in Java implementieren die Wiederholung mit Entwickeln Beziehungen

c) die vollständige rekursive Aufrufstruktur für Picknick (250, 42)

d) Was ist das Muster der Rekursion hier? (Tail rekursiv oder nicht? tree oder linear rekursiv?)

e) Erinnert diese Funktion an irgendeine Algorithmus-Design-Strategie? Wenn ja, welcher?

Ich habe bereits getan Frage a) mit dieser als die Antwort ein:

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

Und ich bin nicht sicher, wie die rekursive Funktion zu implementieren. Ich habe einige Male versucht, aber immer noch nichts.

Frage b und c sind meine größten Probleme atm, und ich "bin sicher, dass ich d und e ausrechnen kann. Könnte jemand bitte mir dabei helfen? Und mögliche zeigen mir, wie kann es umgesetzt werden?

Answer 1

Sie müssen:

Erstellen Sie eine Aufzählung, die Ihre verschiedenen Regeln (es gibt 4 von ihnen: p).Lets zugeben Sie Ihre Aufzählung ERule

erstellen eine rekursive Funktion mit args Namen

• restlichen Eier (zunächst == n)
• m

Die Ausgangsbedingungen für die rekursive Funktion beeing:

• n = m (true)
• n < m (false)
• keine Regel n gelten kann (false)

, wenn die Ausgangsbedingungen nicht erfüllt sind, dann einfach die rekursive Funktion für jede Regel aufrufen, die den aktuellen n aplied werden kann (Rufen Sie es auf dem modifizierten n-Wert auf, abhängig von der Bedingung, die Sie testen). Und das Ergebnis ist eine ODER-Anweisung für alle Ergebnisse.

Answer 2

In Recurrence Relation müssen wir nicht Klasse und Methoden definieren, wie Sie in Ihrer Frage erwähnt haben. Dies ist eine Baumrekursion und keine Tail-Rekursion. Und diese Funktion erinnert uns an Backtracking-Design-Strategie.

für Teil b) meine Lösung ist einfach und rohe Gewalt.

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