Problem der Erbteilung ?

[-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 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 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 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 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

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.....

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