StackOverflowError für den Münzwechsel in Scala?

8

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?

    
J L 07.04.2013, 06:03
quelle

5 Antworten

17

Hier ist die richtige Lösung basierend auf Ihren Codes:

%Vor%

Wie auch immer, es gibt eine kurze Lösung (aber nicht effizient, Sie können das mittlere Ergebnis zwischenspeichern, um es effizient zu machen.)

%Vor%     
Eastsun 07.04.2013, 13:14
quelle
16

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.

    
Dan Abramov 27.12.2013 00:25
quelle
1

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%     
Ivan Guardado 20.09.2013 17:27
quelle
1

Man kann den cnt-Parameter weglassen, der tatsächlich niemals akkumuliert wurde. Die rekursive Funktion gibt immer entweder 0 oder 1 zurück, also wäre der optimierte Algorithmus:

%Vor%     
paaro 27.09.2013 23:15
quelle
1

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

    
Leonmax 27.04.2015 16:14
quelle

Tags und Links