Einzelnen Beitrag anzeigen

Hawkeye219

Registriert seit: 18. Feb 2006
Ort: Stolberg
2.227 Beiträge
 
Delphi 2010 Professional
 
#12

Re: Problem der Erbteilung ?

  Alt 18. Nov 2006, 22:16
Zitat von Cöster:
Würde sich das nicht bei einer größeren Anzahl von Münzen negativ auf die Rechenzeit auswirken? Denn wenn ich dich richtig verstehe, willst du alles ausprobieren.
Sicher, ich habe einen einfachen Brute-Force-Algorithmus für eine vergleichsweise kleine Menge von Münzen skizziert. Mit den von von Delphi bereitgestellten Integertypen wäre spätestens bei 32 Münzen (FOR) bzw. 64 Münzen (WHILE oder REPEAT) Schluß. Auch ein Backtracking-Verfahren probiert üblicherweise alle Möglichkeiten aus, allerdings kann man durch geeignete Abbruchkriterien ganze Teilbäume von der Verarbeitung ausschließen. Bei der Lösung mit einer (WHILE-/REPEAT-)Schleife ist dies aber prinzipiell ebenfalls möglich. Somit sind beide Verfahren wieder sehr ähnlich - nur die Rekursion fehlt bei dem von mir vorgestellten Lösungsweg.

@Alex
Dein Versuch mit einer FOR-Schleife wird wohl nicht zu einer Lösung führen. Wie erkennst du, ob eine Münze bereits verwendet wurde? Ohne diese Prüfung testest du zahlreiche unzulässige Kombinationen.

Die FOR-Schleife steckt bereits in der Rekursion. In jeder Rekursionstiefe mußt du in deiner Prozedur eine Münze aus dem Vorrat betrachten. Es gibt nun zwei Möglichkeiten:
  • Die Münze wird ignoriert. Dann kann direkt der rekursive Aufruf der Prozedur zum Betrachten der nächsten Münze erfolgen. Natürlich nur, sofern noch nicht alle Münzen betrachtet wurden.
  • Die Münze wird dem Anteil hinzugefügt. Falls damit eine Lösung ermittelt wurde, kannst du sie ausgeben. Sonst erfolgt ein rekursiver Aufruf, falls noch nicht alle Münzen betrachtet wurden UND überhaupt noch Lösungen mit diesem Anteil möglich sind.
Die aktuelle Rekursionstiefe hast du bereits bei deinem Versuch als Parameter vorgesehen. Als zweiten Parameter würde ich den aktuellen Anteil am Erbe übergeben, d.h. die Summe, die sich aus dem Wert der übernommenen Münzen ergibt.

Gruß Hawkeye
  Mit Zitat antworten Zitat