Problem der Erbteilung ?

[-lx-]

Hallo.

Ich habe von meiner Tante eine Truhe geerbt, die ich mir mit meinem Bruder teilen muss.
In der truhe befinden sich 5 Geldstücke mit den Werten 5, 9, 1, 3 und 8.

Nun ist es so, dass wir erst dann unser Erbe erhalten, wenn wir den Geldbetrag gerecht unter uns aufteilen. Sollten wir das nicht schaffen, löst es sich in Luft auf.

Rechnerisch kommt man leicht drauf, wieviel jeder von uns bekommen kann:

5 + 9 + 1 + 3 + 8 = 26
26 div 2 = 13

D.h. jeder muss einen betrag von 13 erhalten.


So nun ist aber die Frage, in welchen Kombinationen die einzelnen Geldstücke verteilt werden müssen, um auf den Betrag von 13 zu kommen.

ich denke Ihr habt shcon gemerkt dass es sich um eien Aufgabe handelt und nicht um eine "wirkliches" Erbe ;)


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.
Fangen wir mal an:
5 < 13
5 + 9 > 13
5 + 9 - 9
5 < 13
5 + 1 < 13
5 + 1 + 3 < 13
5 + 1 + 3 + 8 > 13
5 + 1 + 3 + 8 - 8
5 + 1 + 3 < 13


aber was nun ?

Das muss ja via Backtracking und Rekursion gelöst werden. Ich komm nur nicht ganz dahinter wie ich weiter machen muss.


Über Hilfe würde ich mich sehr freuen. Vll. hat dieses Verfahren eine speziellen Namen denn unter "Backtracking Erbproblem" finde ich nichts.

Wäre dies nicht eig. eine Art der Permutation ?




mit freundlichen Grüßen

Alex

[Der_Unwissende]

Zitat:

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:

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:

1. Die Summe ist 13, du bist fertig
2. Die Summe ist kleiner 13, du machst rekursiv weiter (neuer Aufruf)
3. 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!

[Blackheart]

Vieleicht würde es helfen die Zahlen vorher zu sortieren und dann zu vergleichen.

9 + 8 + 5 + 3 + 1 = 26 / 2 = 13
9 + 8 > 13 (8 fliegt raus)
9 + 5 > 13 (5 fliegt)
9 + 3 < 13 (3 bleibt)
9 + 3 + 1 = 13 (richtig)

[Thorben_K]

wie das geht weiss ich leider nichts, aber das ist das sogenannte "[dp]Rucksack probleme"[/dp], da habe ich vor einigen tagen erst ein lösungs ansatz bzw vorschlag gesehen

edit : Webseiten-Titel vll hillft dir das ja


gruss Thorben

Edit2: nach nochmaligen lesen weiss ich net ob das stimmt, was ich geschrieben habe, na ja kannst es dir ja trotzdem mal anschauen :D

[Der_Unwissende]

Zitat:

Zitat von Thorben_K

wie das geht weiss ich leider nichts, aber das ist das sogenannte "[dp]Rucksack probleme"[/dp], da habe ich vor einigen tagen erst ein lösungs ansatz bzw vorschlag gesehen

Das wäre aber eine sehr sehr spezielle Variante des Rucksackproblems. Immerhin soll hier ein exakter Wert erreicht werden. Beim Rucksackproblem handelt es sich vielmehr um ein Optimierungsproblem (einer der Fälle, in dem man nur das Beste sucht).
Selbst im speziellen Fall, dass das Gewicht dem Wert gleicht kann es sein, dass die optimale Lösung nicht das volle Gewicht ausnutzt. Sagen wir man hat ein max. Gewicht von 3 und zwei Teile, die gerade 2 wiegen (und den gleichen Wert haben!).
Natürlich kann man auch das spezielle Rucksack-Problem (bei dem halt Gewicht = Wert) ist verwenden, es lösen und wenn das max. Gewicht hier dem halben Erbe und die Lösung des Rucksackproblems als Wert halt auch dem halben Erbe entspricht, super dann hat man eine Lösung. Wäre allerdings eine vollkommen unnötige Reduktion (auf ein imo nicht gerade leichteres Problem). Durchaus möglich, aber eben mehr arbeit :wink:

[-lx-]

Hallo und herzlichen Dank für eure Antworten !! =)


Wie schon gesagt ist Backtracking eien Verfahren des Ausprobierens. D.h. sollte es nicht mehr weiter gehen, geht man sowiet zurück, bis man wieder eine Möglichkeit zur Auswahl hat, die man noch nicht ausprobiert hat - soweit die Theorie ;)

Beispiele wie das 8-Damen problem oder den Weg aus einem Labyrinth zu finden, sind in der theorie ganz simpel. Nur in der Ausführung hapert es - zumindest bei mir. Ob das normal ist.. weis ich nicht.


Hier mal ein Stück Code, der jedoch noch nicht das gewünschte Ergebnis ausspuckt:

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte: Integer) ;
var j: Integer ;
    begin
      If i < length(Feld) Then
          begin
            Erbe:= Feld[i] ;
            For j:= i To length(Feld) - 1 Do
                begin
                  If (Erbe + Feld[i+1]) < Erbhaelfte Then
                      begin
                        SucheLoesung(i+1, Erbhaelfte) ;
                      end
                  Else if (Erbe + Feld[i+1]) = Erbhaelfte Then
                end;
            Erbe:= Erbe + Feld[i] ;
          end;
      Edit1.Text:= IntToStr(Erbe) ;



    end;

Hier handelt es sich um die Procedure SucheLoesung. Ihr wird der Parameter 1 für i übergeben und Erbhaelfte erhält den Wert des habeln Erbes - soweit es einen gibt.

Meiner Meinung nach muss es mindestens eine For-Schleife geben. Eien weitere Frage ist, ob man erst überprüft ob ein erneuter rekursiver Aufruf sinnvoll ist O D E R ob erst in einem erneuten rekursiven Aufruf geprüft wird, ob dieser sinnvoll war oder nicht. Desweiteren ist mir nie so wirlich klar - bei der Rekursion - wo genau die Werte zum Gesamtergebnis zusammengetragen werden. Also ab welcher Position.

Sorry dass ich frage, aber ich finde Rekursion schon etwas komplex und "verdreht".





Mit freundlichen Grüßen

[Hawkeye219]

Hallo Alex,

es handelt sich hier um ein 2-Personen-Nullsummenspiel, bei dem ein Betrag X vollständig zwischen zwei Personen aufgeteilt wird. Eine Person kann jede der 5 Münzen besitzen oder nicht besitzen - es gibt also 32 Möglichkeiten für die Aufteilung.

Die Lösung kann auch ohne Rekursion mit einer einfachen Schleife ermittelt werden, wobei man den Schleifenzähler als Bitvektor auffaßt. Ein gesetztes Bit bedeutet "Münze erhalten", ein gelöschtes Bit bedeutet "Münze nicht erhalten". Bei jedem Schleifendurchlauf kann auf diese Weise der Anteil einer Person berechnet werden. Entspricht der doppelte Anteil der gesamten Erbsumme, war die Aufteilung gerecht, und es wurde somit eine Lösung gefunden.

Gruß Hawkeye

[-lx-]

Jedoch soll es mitHilfe der Rekursion und des Backtrackings gelöst werden.


Eig. wäre doch eien Funktion viel besser geeignet, oder ?


Wie komme ich denn wieder con Aufruf C zu Aufruf B und A zurück ?

[Cöster]

@ Hawkeye: 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.

Zitat:

Zitat von -lx-

Jedoch soll es mitHilfe der Rekursion und des Backtrackings gelöst werden.


Eig. wäre doch eien Funktion viel besser geeignet, oder ?


Wie komme ich denn wieder con Aufruf C zu Aufruf B und A zurück ?

Widerspricht sich das, Rekursion + Backtracking und Funktion? Von Aufruf B gelangst du automatisch zurück zu Aufruf A: A ruft B auf, sobald B fertig ausgeführt ist, bist du wieder in A.

[-lx-]

Habs gelöst.


Ich weis nur noch nicht recht wieso Oo

Wäre für eine Erklärung seeehr dankbar.


Habs auch mit verschiedenen Werten versuchst.

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte: Integer) ;
var j, tmp: Integer ;
    begin




      For j:= i To length(Feld) Do
          begin
            tmp:= Feld[j] ;
                  If (Erbe + tmp) = Erbhaelfte Then Edit1.Text:= 'Gefunden _ ' + IntToStr(Erbe+tmp)
            Else  If (Erbe + tmp) < Erbhaelfte Then
                      begin
                        Erbe:= Erbe + tmp ;
                        If i < length(Feld) Then SucheLoesung(i+1, Erbhaelfte) ;
                      end;
          end;



    end;

Edit: Der funktioniert doch nocht nicht richtig -.- versucht mit: (17,42,7,4,16) ;


Edit2: Moment. Man kann ja nicht x beliebige Werte in einer x beliebigen Kombination verwenden. Diese müssen sich schon so summieren lassen - also die einzelnen Felder des Arrays, das sie sich in 2 gleich große Gruppen aufsaplten lassen. Achsoooo... mh


Edit3: Nein also richtig funktioniert es noch nicht. Wenn ich 8,3,7,9,1 eingebe, gibt er 14 aus. Schreibe ich jedoch 1,9,7,3,8 - also rückwärts - dann gibt er garnichst aus.


Edit4: Ich habe nun folgende Zeiel hinzugefügt: Erbe:= Erbe - tmp ;
Und zwar habe ich sie nach dem rekursiven Prozeduraufruf, innerhalb der If-Abfrage reingepackt. Meien überlegung ist, sollte er einmal dennoch größer werden, fällt er an den Punkt des prozeduraufrufes zurück. Da die vorherige Addition falsch war, subtarhiert er wieder den letzten Wert vom Gesamtergebnis.


Ist das denn so richtig ? Oder geht es noch einfacher und simpler (dennoch mittels Rekursion und Backtracking) ?

[-lx-]

Hier mal bis dato der aktuelle Code... also ich verstehs net wieso er bei einer identischen Zahlenkette, die jediglich mal verkehrt herum überprüft, nichts ausgibt und das andere mal gibt er was richtiges aus. Jedoch stimmt es eig. auch nicht das 17,42,7,4,16 sich nicht gerecht aufteilen läasst ....

Delphi-Quellcode:

[...]

type
  TFeld = Array[1..5] of Integer ;


[...]

var
  Form1: TForm1;
  Feld: TFeld = (17,42,7,4,16) ;
 // Selectiert: TFeld = (0,0,0,0,0) ;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var Erbe: Integer ;


function ErbeBerechnen(): Integer ;
var i, tmp: Integer ;
    begin
      tmp:= 0 ;
      For i:= 1 To length(Feld) Do
          begin
            tmp:= tmp + Feld[i] ;
          end;
      result:= tmp ;
    end;


procedure SucheLoesung(i, Erbhaelfte: Integer) ;
var j, tmp: Integer ;
    begin
      For j:= i To length(Feld) Do
          begin
            tmp:= Feld[j] ;
            If (Erbe + tmp) = Erbhaelfte Then
                begin
                  Erbe:= Erbe + tmp ;
                  Edit1.Text:= 'Gefunden _ ' + IntToStr(Erbe)
                end
            Else  If (Erbe + tmp) < Erbhaelfte Then
                begin
                  Erbe:= Erbe + tmp ;
                  If i < length(Feld) Then SucheLoesung(i+1, Erbhaelfte) ;
                  If Erbe > ErbHaelfte Then Erbe:= Erbe - tmp ;
                end;
          end;
    end;
begin
Erbe:= 0 ;
If (ErbeBerechnen mod 2) = 0 Then SucheLoesung(1, ErbeBerechnen div 2)
  Else Edit1.Text:= 'Erbe nicht teilbar!' ;

end;

end.

[Hawkeye219]

Zitat:

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

[Cöster]

Ich versuch auch gerade die Aufgabe nach dem Backtracking-Verfahren zu lösen. Die rekursive Prozedur oder Funktion ist wahrscheinlich nicht länger als 20 Zeilen. Die Erklärung des Unwissenden ist auch ziemlich logisch, aber ich krieg es einfach nicht in Code umgesetzt :(

Ich hab bisher noch keine Erfahrung mit Backtracking gemacht. Könnte vielleicht jemand (z.B. der Unwissende oder auch jemand anders) hier mal eine Musterlösung (Code) präsentieren, die per Backtracking das Problem löst?
Dabei lern ich glaub ich am meisten, als wenn ich mir hier stundenlang vergebens den Kopf über etwas zerbreche, was man vll in ein paar Minuten lösen könnte.

[-lx-]

Wir haben dazu einen Arbeitsbaltt bekommen. Dazu ist ein großteil schon vorgefertigt, jedoch eben nicht der Teil um das problem zu lösen. Jedoch ist vorgegeben:

procedure SucheLoesung(i, Erbhaelfte: Integer);


das ist vorgegeben.


Wenn man das ohne For-Schleife lösen kann... wie soll das gehen...


Eien Musterlösung fände ich auch nicht schlecht... auch wenn das Erfolgserlebnis größer ist wenn ma es selber schafft ;)


Also wäre in meienm Fall i nicht die Anzahl der Felder im Array sondern die Anzahl der Möglichkeiten an Kombinationen ?

[Der_Unwissende]

Zitat:

Zitat von Cöster

Ich hab bisher noch keine Erfahrung mit Backtracking gemacht. Könnte vielleicht jemand (z.B. der Unwissende oder auch jemand anders) hier mal eine Musterlösung (Code) präsentieren, die per Backtracking das Problem löst?
Dabei lern ich glaub ich am meisten, als wenn ich mir hier stundenlang vergebens den Kopf über etwas zerbreche, was man vll in ein paar Minuten lösen könnte.

Hi,
klar kann der Unwissende das, hab gerade mal getestet, komme auf wenig Zeilen (was nicht viel heißt!!!), die funktionieren. Das es wenig Zeilen sind heißt in dem Fall aber nur, dass ich schnell was hingeklatscht habe, da wäre der Lerneffekt gleich null (außer ich schreibe rüber "Was man nicht machen sollte!).

Aber das der Lerneffekt dann am größten ist, das zweifel ich doch mal stark an. Vorallem ist eine der Forenregeln (an die ich mich gerne zu halten versuche), dass hier keine HA gelöst werden. Also nicht persönlich nehmen, dass ich (noch?) keine Lösung poste. Immerhin habe ich jetzt eine Idee, was funktionieren sollte und die hab ich auch nicht nur von woanders kopiert. Also gibt es einen Weg, wie man auf die richtige Lösung kommen kann.
Das erste sind immer die Überlegungen, was man alles hat. In dem Fall gibt es ein Feld mit Daten, ich sag hier einfach mal es hat den Typ TIntegerDynArray (Array of Integer, uses Types), also ist ein Array mit variabler Länge, dass Zahlen enthält. Dann gibt es noch die Erbhaelfte, die gesucht wird. Die ist einfach die Haelfte der Summe aller Zahlen im Array (hier kann SumInt verwendet werden).
Ok, mehr hat man erstmal gar nicht, nennen wir also das Array Erbe und den gesuchten Betrag Erbhaelfte. Soweit wart ihr alle eh schon, ich möchte nur das klar ist, was ich wann meine.

So, der nächste Schritt ist dann die Überlegung, wie man rausfinden kann, ob eine der Teilsummen, die sich aus den Elementen des Arrays bilden lässt, der Erbhaelfte entspricht. Jetzt gibt es hier mehrere Möglichkeiten, aber auch die Vorgabe, dass es hier Backtracking sein muss. Also überlegt man sich, wie das Backtracking aussehen soll.
Die Überlegung ist dabei, dass das erste Element fest zur Lösung gehören muss (in einer der beiden Hälften muss die Zahl drin sein). Nun gibt es ja zwei Möglichkeiten:

1. Man ist bereits fertig, das erste Element hat als Summe einfach schon die Erbhaelfte.
   Man ist noch nicht fertig, also untersucht man das restliche Feld rekursiv.

Den ersten Schritt kann man so schon direkt in Delphi umsetzen, zum zweiten muss man sich noch weitere Überlegungen machen.
Im zweiten Fall versucht man nun alle Kombinationen der folgenden Elemente. Man hat also eine aktuelle Teilsumme, die bisher kleiner war als die Erbhaelfte und untersucht nun alle Zahlen die übrig bleiben. Ist eine Teilsumme dabei kleiner als die Erbhaelfte, so betrachtet man diese Teilsumme als neue aktuelle Teilsumme (rekursiv) und kann weiter machen.
Ist eine Teilsumme größer als die Erbhaelfte, braucht man nicht weitersuchen, diese Teilsumme ist falsch. Hier kann einfach die vorherige Lösung weitermachen.

Das ganze würde mit der Menge [5,9,3,1,8] einfach so aussehen:

Code:

// aktuelle Teilsumme ts
// neue aktuelle Teilsumme nts
// aktuell betrachteter Index i (Array 0 indiziert!)

ts = [5]
summe(5) = 5
// summe < Erbhaelfte
  
für alle i > 1 tue:
i = 1 -> nts = [5,9] // hier jetzt rekursiv weitermachen

  // rekursiver Aufruf
  ts = [5,9]
  summe(5,9) > Erbhaelfte // also nicht weiter machen

// da hier noch für alle i aktiv:
i = 2 -> nts = [5,3]

  // rekursiver Aufruf
  ts = [5,3]
  summe(5,3) < Erbhaelfte // also weiter

  für alle i > 2 (vorheriges i + 1) tue:
  i = 3 -> nts = [5,3,1]
  
    // rekursiver Aufruf
    ts = [5,3,1]  
    summe(5,3,1) < Erbhaelfte // also weiter
     
    für alle i > 3 (vorheriges i + 1) tue:
    i = 4 -> nts[5,3,1,8]
 
      // rekursiver Aufruf 
      summe(5,3,1,8) > Erbhaelfte // also nicht weiter
   
    i = 5 -> i > als Länge des Feldes // also nicht weiter
  
  i = 4 -> nts = [5,3,8] 
    
    // rekursiver Aufruf
    ts = [5,3,8]
    summe(5,3,8) > Erbhaelfte, also nicht weiter
  
  i = 5 -> i > als Länge des Feldes // also nicht weiter

i = 3 -> nts = [5,1]
...

So, jetzt steht hier der Code schon fast in Pseudocode. Es ist nicht mehr als die Überlegung, die man hat, wie hier das Backtracking aussieht. Man muss einfach nur eine aktuelle Teilsumme nehmen, ein neues Element hinzu tun und schauen ob das Element passt. Ist dies der Fall, macht man rekursiv weiter, sonst versucht man es mit dem nächsten Element.
Es ist wirklich nur die Idee von Backtracking, dass lässt sich auf alle Backtracking-Probleme so übertragen, man versucht etwas, prüft ob es so noch ok ist und wenn ja, dann kommt der nächste Schritt dazu, sonst versucht man etwas anderes. Hier mit der Einrückung soll noch mal die Hierachie veranschaulicht werden, wo der hinspringt. alles was auf der selben Höhe ist (also selber Abstand nach links) gehört zur gleichen Aufruf-Tiefe. Dass das Programm hier immer zurückspringt, wenn nichts gemacht wird, darum kümmert sich Delphi.
Es entspricht einfach dem

Delphi-Quellcode:

doFoo(x : Integer);
begin
  if (x > 0) then
  begin
   doFoo(x-1);
  end;
end;

Wobei hier x > 0 der Rekursionsanker ist (sonst hätte man unendlich viele Aufrufe). Ruft man das so auf, mit x = 1, dann wird Delphi hier doFoo(1-1) Aufrufen und auf das Ergebnis warten. Ist doFoo(1-1) berechnet, springt kennt doFoo(1) das Ergebnis und kann weiter machen (wobei hier nichts weiter passiert).
Man sollte also immer auch über einen solchen Anker (wann ist man fertig) nachdenken und nie in eine Rekursion springen, bevor dieser Anker geprüft wurde (sonst kann es eine endlose Rekursion geben, gut endet im Stack-Overflow).

Für das Erb-Problem ist natürlich klar, dass man fertig ist (mit dem Zweig) wenn man eine gültige Lösung hat, die das Problem löst oder wenn der aktuelle Zweig eine ungültige Lösung enthält, die nicht mehr zum Erfolg führen kann (zu klein und keine weiteren Elemente verfügbar oder bereits zu groß und keine neg. Zahlen erlaubt).

Hoffe das hilft weiter (denke die Aufrufe und Abfragen die schon fast Pseudocode sind sollten da einiges erklären).

Trotzdem, bei Unklarheiten ruhig nachfragen, taucht häufiger und gerne auf.

Gruß Der Unwissende

[-lx-]

Das was du beschriben hast ist mir so in der Theorie schon ganz klar ;)


Aber nach meiner Einschätzung macht dies genau doch mein Programmcode. Oder ?





mfg

[Der_Unwissende]

Zitat:

Zitat von -lx-

Aber nach meiner Einschätzung macht dies genau doch mein Programmcode. Oder ?

Na ja, nicht ganz. Eigentlich hast du erstmal einen kleinen Fehler drin. Den findest du sicherlich selbst schnell, schau dir einfach mal die Überprüfungen an, eine Bedingung dürfte nie wahr sein (an dieser Stelle).

[-lx-]

Welche Bedingung meinst du ?


Diese ? If Erbe > ErbHaelfte



So nun mein jetziger Stand (23:56) :

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte, TErbe: Integer) ;
var j: Integer ;
    begin
      If i <= length(Feld) Then
          begin
            For j:= i To length(Feld) Do
                begin

                  If (TErbe + Feld[j]) = Erbhaelfte Then
                      begin
                        Edit1.Text:= 'Gefunden _ ' + IntToStr(TErbe+Feld[j]) ;
                      end
                  Else  If (TErbe + Feld[j]) < Erbhaelfte Then
                      begin
                        SucheLoesung(i+1, Erbhaelfte, TErbe+Feld[j]) ;
                      end
                  Else If (TErbe + Feld[j]) > Erbhaelfte Then
                      begin
                        //TErbe:= TErbe - tmp ;
                      end;

                end;
          end;
    end;



begin
If (ErbeBerechnen mod 2) = 0 Then SucheLoesung(1, ErbeBerechnen div 2, 0)
  Else Edit1.Text:= 'Erbe nicht teilbar!' ;

Für mich macht es so noch vel mehr Sinn und ich muss nichts addieren oder abziehen, wenn nicht absolut sicher ist, dass alles passt.

Nuuuur... 17,42,7,4,16 und 1,9,7,3,8 gibt er immer noch die Hälfte der Summe aus, obwohl er keine ausgeben sollte.




mfg und gute nacht

[Der_Unwissende]

Zitat:

Zitat von -lx-

Welche Bedingung meinst du ?

Diese ? If Erbe > ErbHaelfte

Ja, die war so verschachtelt, dass du erst prüfst ob die Summe < Erbhaelfte ist und nur wenn das nicht der Fall ist, dann prüfst du diese Bedingung zusätzlich ab. Wenn ein Fall keine Behandlung hat (wie bei dir), dann solltest du den einfach weglassen :wink:

Zitat:

Zitat von -lx-

Delphi-Quellcode:

...
For j:= i To length(Feld) Do
begin

  If (TErbe + Feld[j]) = Erbhaelfte Then
  begin
    Edit1.Text:= 'Gefunden _ ' + IntToStr(TErbe+Feld[j]) ;
  end
  Else  If (TErbe + Feld[j]) < Erbhaelfte Then
  begin
    SucheLoesung(i+1, Erbhaelfte, TErbe+Feld[j]) ;
  end

Ja, hier hast du dir einen hübschen Fehler eingebaut, den man leicht übersehen kann. An sich ist der Lerneffekt am größten, wenn du einfach noch mal von vorne anfängst (mit der gleichen Idee!) und schaust was du machen wolltest und was hier gemacht wird.
An sich kannst du (da ich die Stelle schon stark eingegrenzt habe) natürlich leicht alles durchraten und mal schauen, aber davon hast du ehrlich gesagt nichts.
Aber mal kurz zum Ablauf zurück, du schaust erst mal nach, ob die aktuelle Partitionierung des Erbes der Erbhaelfte entspricht. Soweit, so gut. Ist dem so gibst du es aus, auch klar. Aber davor ist ja noch eine Zeile, du machst das wie oft? Na ja, von i bis length(Feld) mal, wenn also das erste Element schon die Erbhaelfte ist, dann gibst du wohl length(Feld) - 1 mal aus, wie groß das Element ist.
Aber das ist nicht weiter schlimm, nicht ganz das was man erwartet und bei großen Feldern vielleicht lästig, aber eben nicht falsch.

Als nächstes betrachtest du den Fall, dass die aktuelle Partitionierung noch kleiner ist als das Erbe. Ist dies der Fall, möchtest du das nächste mögliche Element (ebend das Element Feld[j]) hinzuaddieren und wenn auch diese Summe immer noch kleiner ist als die Erbhaelfte (impliziert ja, dass TErbe kleiner ist), dann möchtest du rekursiv weiter machen. Um weiter zu machen sind ein paar Dinge nötig, die du als Parameter übergibst:

• Der Index des nächsten Elements das hinzugefügt werden kann
• Die Erbhaelfte (konst. für ein Feld)
• Der Wert der aktuellen Partionierung

Ok, überleg dir einfach mal ein wenig ob du hier die richtigen Argumente übergibst. Das ich behaupte, dass es noch einen Fehler gibt, heißt ja nicht dass es wirklich einen geben muss. Gut, da das Programm nicht macht was du erwartest gibt es recht sicher einen, aber der muss wiederum nicht hier liegen.
Schau dir einfach erstmal diese Stellen an, vielleicht siehst du dann ja gleich, was du hier falsch gemacht hast. Hier ist es allerdings so eine Stelle, an der man leicht einen solchen Fehler machen kann.

Es gibt allerdings Möglichkeiten solche Fehler zu minimieren. Viele lernst du (hoffentlich) schon in der Schule kennen, allerdings muss ich auch sagen, dass ich damals als Schüler keine wirkliche Motivation hatte solche Dinge umzusetzen. Trotzdem seien sie hier nochmal erwähnt, ein gutes Programm beginnt immer mit Einfachheit und Lesbarkeit. Alles sollte sich so gut wie es geht selbst erklären. Variablennamen sollten immer selbstsprechend sein (tmp oder i sind es nicht). Dann ist es ganz schlimm, dass hier TErbe als Variablenname verwendet wird. Das T steht in Delphi (per Konvention) für Type, zeigt also einen Datentypen an. Wenn du z.B. TFeld verwendest, dann weiß man so, dass dies ein Datentyp ist, während (auch per Konvention) PFeld ein Zeiger (p = Pointer) auf ein TFeld wäre.
Die Konventionen zum Codestil sind eigentlich nur Richtlinien, keiner muss sich dran halten, aber man sollte es doch immer tun. Immerhin möchtest du ja auch Code den du bekommst verstehen, halten sich alle an die gleichen Konventionen, sollte das immer leicht möglich sein.
Ja, ansonsten bleibt noch die Einrückung. Hier hast du ja immer konsequent eingerückt und auch immer ein begin end - Block in jeder Kontrollstruktur drin, dass ist sehr gut! Wirklich! Viele dumme Fehler passieren hier schnell, weil jmd. eine Zeile noch der Kontrollstruktur (schleifen, Bedingungen und Case) zuordnet, weil die Zeile falsch eingerückt wurde, während eben ohne begin end nur die erste Zeile wirklich zur Struktur gehört.
Egal wie einfach ein Code ist, an sich tut auch immer ein Kommentar gut. Du solltest allerdings auch wirklich nur sinnvolle Kommentare verwenden. Ein Kommentar muss nicht das ganze Programm in jeder Einzelheit beschreiben, aber es sollte einfach kurz gesagt werden, was die Idee ist und warum es so gemacht wird. Wenn du größere Programme schreibst oder mit mehr als einer Person an einem arbeitest, dann gibt es einfache Teile im Code, die siehst du nach Monaten wieder und weißt sonst nicht, warum du da was gemacht hast.

Ok, dann such mal deinen Fehler (bist ja auf dem richtigen Weg!)

Gruß Der Unwissende

[-lx-]

lalala..... :mrgreen:

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte, TErbe: Integer) ;
var j: Integer ;
    begin
     {Memo1.Lines.Add('i: ' + IntToStr(i)) ;
      Memo1.Lines.Add('Erbhaelfte: ' + IntToStr(Erbhaelfte)) ;
      Memo1.Lines.Add('TErbe: ' + IntToStr(TErbe)) ;
      Memo1.Lines.Add('__________') ;}

     { If TErbe = Erbhaelfte Then Edit1.Text:= 'Gefunden _ ' + IntToStr(TErbe)
        Else
            begin }

              For j:= i To length(Feld) Do
                  begin


                    If (TErbe + Feld[j]) = Erbhaelfte Then
                        begin
                          Edit1.Text:= 'Gefunden _ ' + IntToStr(TErbe+Feld[j]) ;
                        end

                    Else  If (TErbe + Feld[j]) < Erbhaelfte Then
                        begin
                          If j < length(Feld) Then
                              begin
                                SucheLoesung(j+1, Erbhaelfte, TErbe+Feld[j]) ;
                              end;
                        end;


                  end;
            {end;}
    end;





begin
If (ErbeBerechnen mod 2) = 0 Then SucheLoesung(1, ErbeBerechnen div 2, 0)
  Else Edit1.Text:= 'Erbe nicht teilbar!' ;

Also bei all meinen Beispielen sowie einfach paar Zufallsdinger gibt er entweder das Teilerbe aus (richtige Teilerbe) oder eben nichts bzw. dass das Erbe nicht teilbar ist.

Soweit ich das sehe, ist der Code nun richtig.


Würde mich freuen wenn das jemand bestätigen könnte. Weil dann kann ich mich an die Ausgabe der verwendeten "Münzen" bzw. Felder machen.





mit freundlichen Grüßen

[-lx-]

So... nun hier die finale Version samt Ausgabe der Stellen der benutzen Zahlen.

Delphi-Quellcode:

[...]


type
  TFeld         = Array[1..5] of Integer ;
  TFeldBoolean  = Array[1..5] of Boolean ;


[...]


var
  Form1: TForm1;
  Feld: TFeld = (1,9,5,3,8) ;
  Selectiert: TFeldBoolean = (False, False, False, False, False) ;

implementation

{$R *.dfm}



procedure TForm1.Button1Click(Sender: TObject);

    procedure ShowSelection ;
    var i: Integer ;
        begin
          For i:= 1 To length(Selectiert) Do
              begin
                If Selectiert[i] Then
                    begin
                      Memo1.Lines.Add('An Feldposition ' + IntToStr(i) + ' --> ' + IntToStr(Feld[i])) ;
                      Selectiert[i]:= False ;
                    end;
              end;
          Memo1.Lines.Add('---------------------------') ;
          Memo1.Lines.Add(' ') ;
        end;


    function Summieren(): Integer ;
    var i, tmp: Integer ;
        begin
          tmp:= 0 ;
          For i:= 1 To length(Feld) Do
              begin
                tmp:= tmp + Feld[i] ;
              end;
          result:= tmp ;
        end;


    procedure SucheLoesung(i, Erbhaelfte, TErbe: Integer) ;
    var j: Integer ;
        begin
        { Memo1.Lines.Add('i: ' + IntToStr(i)) ;
          Memo1.Lines.Add('Erbhaelfte: ' + IntToStr(Erbhaelfte)) ;
          Memo1.Lines.Add('TErbe: ' + IntToStr(TErbe)) ;
          Memo1.Lines.Add('__________') ; }

          For j:= i To length(Feld) Do
              begin

                If (TErbe + Feld[j]) = Erbhaelfte Then
                    begin
                      Selectiert[j]:= True ;
                      Memo1.Lines.Add('Erbe teilbar!') ;
                      Memo1.Lines.Add('Erbe pro Person: ' + IntToStr(TErbe+Feld[j]) + ' €') ;
                      Memo1.Lines.Add(' ') ;
                      Memo1.Lines.Add(' ') ;
                      Showselection;
                    end

                Else  If (TErbe + Feld[j]) < Erbhaelfte Then
                    begin
                      If j < length(Feld) Then
                          begin
                            Selectiert[j]:= True ;
                            SucheLoesung(j+1, Erbhaelfte, TErbe+Feld[j]) ;
                            Selectiert[j]:= False ;
                          end;
                    end;

              end;
        end;


begin

If (Summieren mod 2) = 0 Then SucheLoesung(1, Summieren div 2, 0)
  Else Memo1.Lines.Add('Erbe nicht teilbar!') ;

end;

end.

[Cöster]

Der Code sieht gut aus. Ich denke, Zeile 34 (Selektiert[I] := False) könntest du dir sogar noch sparen, denn beim Auflösen der Inkarnationen geschieht dies sowieso.

[Cöster]

Was mir noch aufgefallen ist:

Wenn eine Lösung gefunden wurde, wird die For-Schleife von j nicht abgebrochen. Selbst, wenn man nach 'ShowSelection' (Z. 72) Break oder Exit aufrufen würde, würde aber nur die aktuelle Inkarnation abgebrochen. In den unteren Inkarnationen wird die Schleife auf jeden Fall zuende (bis j = Length(Feld)) durchlaufen.

Wie ließe sich das denn lösen?

[Der_Unwissende]

Zitat:

Zitat von Cöster

Wenn eine Lösung gefunden wurde, wird die For-Schleife von j nicht abgebrochen. Selbst, wenn man nach 'ShowSelection' (Z. 72) Break oder Exit aufrufen würde, würde aber nur die aktuelle Inkarnation abgebrochen. In den unteren Inkarnationen wird die Schleife auf jeden Fall zuende (bis j = Length(Feld)) durchlaufen.

Wie ließe sich das denn lösen?

Ist die Signatur nicht vorgegeben, sondern entwickelt man eine Lösung für ein Problem (und macht das rekursiv), so wird man hier wahrscheinlich mind. zwei Dinge anders machen. Das eine ist, man arbeitet mit einem Akkumulator. Das ist eine Art zusätzlicher Parameter, in der die Lösung mitgeschleppt wird. Da diese sich über die Rekursion aufbaut, gibt es einen Aufruf an dem die Lösung feststeht. Hier braucht man dann (mit Akkumulator) nicht zurückspringen. Das kann ordentlich Ressourcen schonen.
Der andere Punkt ist, bei so einem Problem kann man z.B. einer Funktion einen Rückgabewert geben, der anzeigt ob die Lösung gefunden wurde (auch ein globales Flag wäre denkbar), dann sollte man prüfen ob das Ergebnis eines Aufrufs gültig war und ggf. die weitere Ausführung des Aufrufs abbrechen.

Noch wahrscheinlicher würde man aber aus dem Grund die Rekursion gerade vermeiden und sich für eine Iteration entscheiden

Gruß Der Unwissende

[-lx-]

Also ist es richtig ? Bzw. könnt ihr den Code bestätigen ? =)

[Der_Unwissende]

Zitat:

Zitat von -lx-

Also ist es richtig ? Bzw. könnt ihr den Code bestätigen ? =)

Schon, aber sowas ist immer ohne Gewähr. Das hat aber schon jmd. gemacht!