Rekursion anhand von Aufgabe lernen

Wyatt

Erfahrenes Mitglied
Hallo!

Ich versuche die Denkweise von Rekursion zu verstehen... Nun hab ich im Internet eine Aufgabe gefunden, die mit Rekursion gelöst werden kann.
Da bin ich nun bei... leider fehlt mir der Ansatz, ich weiss nicht, wie ich an das Problem heran gehen soll!

Die Programmieraufgabe:
Ein 100g-Gewicht soll aus Euro-Münzen gebaut werden.
Die Münzgewichte (g) liegen vor: 2,30; 3,06; 3,92; 4,10; 5,74; 7,80; 7,50; 8,50

Wie viele Kombinationen gibt es, die exat 100g ausmachen?
Kombinationen, die sich nur in der Reihenfolge der Münzen unterscheiden, werden nicht doppelt gezählt!

Ich möchte keine Lösung haben, nur Denkanstöße & Hilfestellungen, wie man an so ein Problem herangeht und es rekursiv löst

Gruß
Felix
 
Hi,

ich würde mir an deiner Stelle erst einmal überlegen, wie dieses Problem ohne Computer zu berechnen ist. Dann würde ich mir zwei bis drei Ergebnisse notieren und daraus ein Baumdiagramm aufzeichnen, das die Rekursion darstellt. Bei der Gelegenheit hast du auch gleich schon einen groben Überblick, wie sich die Funktion nachher verhält.

Grüße, D.

Nachtrag:
Ich würde als erstes mit dem Zielgewicht (100 g) anfangen und dann rekursiv subtrahieren, bis ein Restgewicht übrig bleibt, das entweder 0 ist oder kleiner als das Gewicht der kleinsten Münze. In jeder Rekursionsebene verzweigst du dann weiter in alle sechs Münzgewichte.

Das wird aber wahrscheinlich noch keine doppelten Kombinationen berücksichtigen (müsstest du nachträglich rausfiltern) und ist sicher auch noch nicht optimal was die Laufzeit angeht (mit jeder Ebene rufst du sechs weitere Funktionen auf).

Nachtrag 2:
Ansonsten schließe ich mich Tom an. Es ist besser zum Verständnis, wenn du dir erstmal ein einfacheres Beispiel raus suchst.
 
Hallo,

ich glaube das gewählte Beispiel ist etwas komplex...
Normalerweise erklärt man Rekursion anfangs mit Methoden zur Berechnung der Fakultät:

n! = 1*2*3*4*....*n
0! = 1

Java:
/**
 * 
 */
package de.tutorials;

/**
 * @author Thomas.Darimont
 *
 */
public class RecursionExample {

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }

    private static int factorial(int n) {
        
        if(n == 0){ //Abbruchbedingung
            return 1;
        }
        
        return n * factorial(n-1); //Rekursiver Aufruf
    }
}

Gruß Tom
 
Hallo Jungs,

erstmal danke für eure Ideen und Hilfestellungen...
Ich habe schon kleine Beispiele (wie das von Tom) ausprobiert und auch verstanden.
Eine Methode um den größten gemeinsamen Teiler zweier Zahlen zu finden, oder eine Methode erkennt, ob ein String ein Palindrom ist...

Die Methode um rekursiv den größten geimeinsamen Teiler zweier Zahlen zu finden
Java:
private int calcHighestCommonFactor(int i, int x, int n) {
	if(i>1)
		if((x%i) == 0 && (n%i) == 0)
			return i;
	return calcHighestCommonFactor(i-1, x, n);
}

Die Methode für Potenzrechnung z.B. 2^4
Java:
public static int PotenzRecursiv(int base, int exponent, int result) {
	if(exponent >= 1)
		return PotenzRecursiv(base, exponent-1, result * base);
	return result;
}

Ob die Methoden nun optimal aufgebaut sind, weiss ich nicht!

Solche Aufgabe krieg ich auch eigentlich hin, aber bei der Münz-Aufgabe hab ich viel mehr Möglichkeiten zu verzweigen, damit komme ich noch nicht zurecht!

Dario, was meinst du mit Baumdiagramm?! Subtrahieren ergibt Sinn, die Idee ist wirklich gut, aber da muss ich ja auch alle möglichen Kombinationen erstellen!
Das Filtern im nachhinein ist kein Problem, das krieg ich hin.

Über weitere Hilfestellungen und Erklärungen freue ich mich natürlich! :)

Gruß
Felix
 
Zuletzt bearbeitet von einem Moderator:
Zurück