Ich schreibe eine rekursive Funktion für das Coin (Change) -Problem in Scala.
Meine Implementierung bricht mit StackOverflowError und ich kann nicht herausfinden, warum das passiert.
%Vor%das ist mein Ruf:
%Vor%das ist meine Definition:
%Vor%Bearbeiten: Ich habe gerade die else if-Anweisung im Mix hinzugefügt:
%Vor%es wurde der Fehler los, aber meine Ausgabe ist 1500 etwas :( Was ist los mit meiner Logik?
Die erste Lösung in der akzeptierten Antwort hat einen redundanten letzten Parameter wie von Paaro erwähnt , also wollte ich es loswerden. Die zweite Lösung verwendet map , was ich vermeiden wollte, da es in der Woche 1 oder im Scala-Kurs, den ich vermute, noch nicht behandelt wurde. Auch wäre die zweite Lösung, wie vom Autor richtig bemerkt, viel langsamer, wenn sie nicht etwas Memoisierung benutzt. Schließlich scheint Paaros Lösung eine unnötige verschachtelte Funktion zu haben.
Also hier ist, was ich endete:
%Vor%Wie Sie sehen können, brauchen Sie hier keine Zahnspange.
Ich frage mich, ob es weiter vereinfacht werden könnte.
Die @Eastsun-Lösung ist gut, aber sie schlägt fehl, wenn Geld = 0 ist, weil sie 1 anstelle von 0 zurückgibt, aber Sie können es leicht beheben:
%Vor%Hier ist ein DP-Ansatz, um eine Menge von Neuberechnungen im rekursiven Ansatz zu reduzieren
%Vor%Siehe DP vom Anfänger bis zum Fortgeschrittenen für Algorithmus
Tags und Links scala