4. Backtracking Problematik

Backtracking Problematik

  • V

    Maffe001 schrieb:

    Ich denke, er meint Addition. Wenn Substraktion auch noch dazu zählt, na dann "Prost, Mahlzeit". Aber eigentlich dürfte man mit beidem zu gar keinem Ende kommen , oder? 😕

    doch, das jeht janz flott.

    //unjetestet
rest0=50;
for(rest1=rest0;rest1>=0;rest1-=7)
for(rest2=rest1;rest2>=0;rest2-=5)
for(rest3=rest2;rest3>=0;rest3-=3)
printf("%d %d %d",rest3-rest2,rest2-rest1,rest1-rest0);
    0
  • M

    Aber wenn ich Subtraktion zulasse, habe ich doch eine unendliche Anzahl von Kombinationsmöglichkeiten. Schliesslich ist 3-3 = 0 und schon hab ich wieder eine Kombination mehr.
    Dass die Erstellung einer Kombination schnell gemacht ist, zweifel ich ja gar nicht an. 😃

    0
  • V

    Maffe001 schrieb:

    Aber wenn ich Subtraktion zulasse, habe ich doch eine unendliche Anzahl von Kombinationsmöglichkeiten.

    jo.

    Dass die Erstellung einer Kombination schnell gemacht ist, zweifel ich ja gar nicht an. 😃

    ich hab alle bei addidion aufgelistet. und mein "doch" bezug sich auch nur auf "Aber eigentlich dürfte man mit beidem zu gar keinem Ende kommen". bei addidion kommt man schnell zum ende.
    der erste faktor (die 3) kann auf 11 weisen vorkommen. keinmal, einmal, zweimal, ...
    die 5 kann auf 7 weisen vorkommen.
    die 7 kann auf 6 weisen vorkommen.
    macht maximal 11*7*6 möglichkeiten. in wirklichkeits sind sogar viel weniger, weil wo die ja zugleich reinsollen in die 50.

    0
  • F

    Hallo,
    erstmal Danke für die vielen Antworten. Rekursiv ist auch ok. Am besten per "exhaustive search".

    Eben habe ich mich unverständlich ausgedrückt. Also es gibt eine endliche Lösungmenge der Kombinationen, da nur Addition abgedeckt werden soll.
    z.B:
    11 + 11 + 11 + 11 = 55 > 50 -> Keine Lösung
    11 + 11 + 11 + 7 = 51 > 50 -> Keine Lösung
    ...
    7 + 3 + 7 + 3 + 7 + 3 + 7 + 3 + 7 + 3 = 50 -> Ist eine Lösung -> Ausgeben
    aber auch
    7 + 7 + 7 + 7 + 7 + 3 + 3 + 3 + 3 + 3 = 50 -> Ist eine Lösung -> Ausgeben
    usw.

    0
  • A

    @Folmstat
    Und wie weit bist du schon mit deiner Lösung?

    0
  • F

    Gestern habe ich probiert und probiert, aber ich habe keinen Ansatz finden können, da ich noch keine großen Erfahrungen habe. Erst hatte ich es versucht mit mehreren for-Schleifen, aber ich habe es nicht hinbekommen. Dann wollte ich rekursion benutzen, habe das aber auch nicht gebacken bekommen. 😕

    0
  • A

    Wie würdest du es denn auf dem Papier machen, wenn du es Schritt für Schritt durchgehen musst?

    Ich würde dir sogar empfehlen, dass du es einmal iterativ (mit Schleifen) und einmal rekursiv machst.

    0
  • F

    Iterativ würde ich sagen

    wenn SUMME <= 50 mache SUMME += 11
    wenn SUMME = 50 gib die Zahlenkobination aus
    wenn SUMME > 50 mache SUMME -= 11 bis SUMME < 50
    dann SUMME += 7 solange bis SUMME = 50, oder SUMME > 50
    ist SUMME = 50 gib die Kombination aus
    ist SUMME > 50 mache SUMME-=7 bis SUMME < 50 und dann SUMME+=3 usw...

    0
  • A

    Es geht beides iterativ und rekursiv.

    Jetzt versuch mal deine einzelnen Schritte in Quellcode umzusetzen und dann zeig uns mal dein Konstrukt.

    0
  • F

    Werde ich machen, aber dafür muss ich erstmal nach Hause und da habe ich kein Internet. Also wird es frühestens Morgen drinnen sein.

    0
  • F

    So, mein Ergebniss liegt vor.

    Ich habe nicht 50, sondern 25 genommen und die Zahlen 11, 7, 5 und 3, um die Kombinationen zu bilden.
    Erster Gedanke war, wie viele Möglichkeiten es gibt und da komme ich auf 9*6*4*3 = 648 Möglichkeiten. Meine Idee ist, dass die Gleichung 2*x+3*y+5*z+8*v=25 erfüllt sein muss. Also muss ich alle Möglichkeiten der Gleichung checken und, wenn sie erfüllt ist ausgeben.

    Eine Frage ist jetzt, gibt es einen Trick, wie man for-Schleifen leicht in eine Rekursion umwandeln kann und ist mein Vorgehen das erschöpfende durchsuchen? Da ich alle Kombinationen durchgehe müsste dem so sein.
    Unten ist mein Quelltext.

    #include <stdio.h> 

int main( void){
  int n, i, j, k; /* Hilfsvariablen */
  //int zaehler=0;

  for(n=0; n<=25; n+=11) /* Schleife fuer 11 */ 
  {
    for(i=0; i<=25; i+=7) /* Schleife fuer 7 */
    {
      for(k=0; k<=25; k+=5) /* Schleife fuer 5 */
      {
        for(j=0; j<=25; j+=3) /* Schleife fuer 3 */
	{ 
	  zaehler++;
	  if((n + i + k + j)==25)
	    printf("*** Loesung: %d*11 + %d*7 + %d*5 + %d*3 ***\n", n/11, i/7, k/5, j/3);
	  //else
	    //printf("Keine Loesunge: %d*11 + %d*7 + %d*5 + %d*3// Zaehler: %d\n", n/11, i/7, k/5, j/3, zaehler);

	}        
      }
    }
  }
  return 0;
}
    0
Anmelden zum Antworten