Zitat von
-lx-:
Zum programmieren:
Mir ist klar, dass man immer einen Wert zum anderen bzw zur bereits vorhandene Menge hinzu addieren muss und dann überprüft man, ob man unterhalb, gleich oder oberhalb der 13 liegt.
aber was nun ?
Das muss ja via Backtracking und Rekursion gelöst werden. Ich komm nur nicht ganz dahinter wie ich weiter machen muss.
Hi,
natürlich merkt man recht schnell, dass das eine Aufgabe ist. Allerdings fehlt ein wenig die Erklärung was du schon über Backtracking weißt?
Zitat von
-lx-:
Wäre dies nicht eig. eine Art der Permutation ?
Backtracking ist nur eine bestimmte Art alle Permutationen zu bilden. Du gehst dabei einfach systematisch vor und kannst aufhören, sobald du eine Permutation gefunden hast, die gut genug ist. Häufig möchtest du gar nicht die einzigste Optimale Lösung berechnen (einfach nur weil das viel zu lange dauern würde), dann kannst du mit ein paar geschickten Opitmierungen und Überlegungen und ggf. etwas Backtracking eine für dich ausreichend gute Lösung finden.
Backtracking geht dabei den Weg, dass du etwas versuchst und schaust ob es passt. Du merkst dir praktisch, wo du gerade bist und versuchst alle Möglichkeiten, die von diesem Punkt aus möglich sind. Findest du einen nächsten Schritt, bist aber noch nicht fertig, so gehst du in diesem Schritt genauso vor. Jetzt gibt es zwei Möglichkeiten: Eine Lösung führt zu dem Ergebnis -> Du bist fertig. Die Lösung führt nicht zum Ergebnis -> Du gehst einen Schritt zurück und machst mit der nächsten Möglichkeit weiter.
Das ganze ist rekursiv einfach nur sehr einfach zu programmieren. Hier liegen dann klar die Vorteile der Rekursion.
An sich ist die Idee nicht, dass du etwas zu addierst und wieder abziehst, sondern dass du die erste Zahl nimmst und nun schaust, was hier möglich ist. Du merkst dir also die erste Zahl und hast jetzt die Möglichkeit eine der anderen Zahlen zu addieren.
Stell dir einfach vor, dass du die Aufrufe benennst. Im ersten Schritt (Aufruf A) geht es darum eine Zahl zur 5 zu addieren. In Frage kommt die 9, 1, 3 und 8. Hast du eine Zahl addiert, gibt es drei Möglichkeiten:
- Die Summe ist 13, du bist fertig
- Die Summe ist kleiner 13, du machst rekursiv weiter (neuer Aufruf)
- Die Summe ist > 13, du gehst springst zum letzten Aufruf zurück
Für Aufruf A gibt es 4 Zahlen, die du betrachten kannst. Du fängst also mit der 9 an und nun ja, es klappt nicht. Also bleibst du in Zustand A und machst mit der 1 weiter. Wie du ja gesagt hast ist 5 + 1 < 13. Damit rufst du (rekursiv) die gleiche Funktion auf (Aufruf B). Aufruf B besteht jetzt aus der Zahl 6 und es kann noch die 3 oder 8 addiert werden.
Addierst du die 3, ist der Wert < 13 -> Rekursiver Aufruf (Aufruf C). In C hast du den Wert 9 und kannst noch die 8 addieren. Ja, 8 addieren bringt dich zu größer 13. Da es keine andere Zahl mehr gibt, die du addieren kannst, ist C kein Weg der zum Ziel führt. Also gehst du zurück in Zustand B.
B hatte die Zahl 6 und die Möglichkeit 3 oder 8 zu addieren. Das Addieren von 3 hast du gerade betrachtet, folgt also das Addieren von 8, geht natürlich auch nicht. Also zurück zu A. Hier hattest du die 5 und schon versucht die 9 und die 1 zu addieren, also machst du jetzt mit der 3 weiter...
Ich hoffe du hast das System grob verstanden. Das ganze kann man wirklich einfach in einer Rekursion verpacken. Da hast du gerade den Vorteil, dass so ein rekursiver Aufruf aut. dazu führt, dass der alte Zustand behalten wird. Versuch es einfach mal und frag nochmal nach, wenn etwas unklar ist.
Gruß Der Unwissende
PS: Nach einer einfachen Lösung für genau das Problem zu suchen hilft dir nicht viel, in der Klausur (aber auch in vielen Programmen) kannst du schnell auf eine andere Form von Backtracking treffen. Einmal verstanden ist das System immer gleich und gehört und wirklich nicht schwer!