programm wert Algorithmus Programmierung KLausur programme Teilaufgabe

Dynamische Programmierung

Von: , Frage gestellt am Di, 18. Sep 2001

Hallo,
ich suche jemanden, der/die sich in dynamischer Programmierung auskennt und mir schreiben kann, ob mein Lösungsvorschlag richtig oder falsch ist . Es geht um eine die erste Teilaufgabe einer Klausur. Bin mir aber nicht sicher, ob dass wirklich zu dem Thema dynamische Programmierung gehört. Jedenfalls bezog sich die der zweite Teil auf dynamische Programmierung.
Es geht um einen Menge von Beträgen v1, v2, v3, ..vn und einen Betrag B. Es sollen alle möglichen Kombinationen aus den Beträgen gebildet werden, um B darzustellen. Z.B. B= 12 v1=2 und v2=5
12=6*2=2*5+1*2
Hoffe, dass sich jemand meldet.

Felix

4 Antworten zu dieser Frage

1. Antwort von nach einer Stunde 0 hilfreich

   Laesst sich mit dyn. Programmierung machen.

   Einfacher Fall: wir wollen nur rausbekommen, was wir alles an Zahlen erzeugen koennen, wobei wir fuer jede Zahl einen Ausdruck wissen wollen (andere Varianten gehen aehnlich).
   
   Denk Dir ein Array A von Ausdruecken (z.B. als String gespeichert)
   In A[v1] schreiben wir "v1" ind A[v2] "v2" usw.
   
   Nun brauchen wir zwei Schleifen In der aeuesseren zaehlen wir i
   von 1 bis zur groessten Zahl, die uns interessiert, hoch.
   
   Sollte A[i] nicht leer sein, so starten wir eine zweite
   innere schleife dir e von 1 bis i hochzaehlt.
   Ist A[e] nicht leer so setzen wir
   A[e+i] auf A[e] + "+" + A[i] (+ fuer Stringconkatenation)
   und
   A[e*i] auf A[e] + "*" + A[i]
   
   Ende Innere Schleife
   Ende aeussere Schleife
   
   Da e+i und e*i (da wir das ganze mit natuerlichen Zahlen spielen)
   immer groesser als i sind, koennen wir fuer jeden Wert von i wissen, dass wir alle kleineren Werte, die sich darstellen lassen schon "erschlagen" haben.
   
   Das Dynamische daran ist, dass wir die gefundenen Teilloesungen immer wieder verwenden.
   
   MfG
   Martin
   

   • Antwort von nach 3 Tagen 0 hilfreich

     Re: Laesst sich mit dyn. Programmierung machen.

     Hallo,
     ich habe das ganz anders gemacht. Moechte es mit einem Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein Betrag, sagen wir mal 12 DM. Dann koennte man folgende Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus wuerde ich folgendermassen beschreiben:
     1. Tue folgendes bei fuer jeden Muenzbetrag
     1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der Betrag<=0 und zaehle die Anzahl der Subtraktionen
     1.2 Falls Betrag = 0, dann brich ab gebe die Anzahl aus und gehe zu 1.
     1.3 Falls Betrag< 0, dann addiere v auf den Betrag, dekrementiere den Zaehler und gehe zu 1 und suche ein anderen Muenzbetrag aus ausser v.
     Wie siehts denn damit aus?
     
     Felix [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
     

     • Antwort von nach 4 Tagen 0 hilfreich

       Re^2: Laesst sich mit dyn. Programmierung machen.

       Hallo,
       ich habe das ganz anders gemacht. Moechte es mit einem
       Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein
       Betrag, sagen wir mal 12 DM. Dann koennte man folgende
       Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus
       wuerde ich folgendermassen beschreiben:
       1. Tue folgendes bei fuer jeden Muenzbetrag
       1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der
       Betrag<=0 und zaehle die Anzahl der Subtraktionen
       1.2 Falls Betrag = 0, dann brich ab gebe die Anzahl aus und
       gehe zu 1.
       1.3 Falls Betrag< 0, dann addiere v auf den Betrag,
       dekrementiere den Zaehler und gehe zu 1 und suche ein anderen
       Muenzbetrag aus ausser v.
       Wie siehts denn damit aus?
       
       Felix
       1. Das ist halt nicht dynamisch, weil Du fuer jeden Münzbetrag auch
       alle Zwischenwerte neu berechnen mußt.
       
       2. Muß das nicht unbedingt klappen: Gegeben 11 Mark und 2 und 5 Mark-Stücke. lösung ist 3*2+5. Wenn wir mit 2 anfangen, laufen wir bis -1, dann zu 1 und versuchen dann 1 mit 5 darzustellen (genauso wenn wir mit 5 anfangen).
       
       3. Nochnals der Rat: Schreib diese Programme doch bitte einfach.
       Dann nimmst Du dir einen Debugger und beobachtest das ganze.
       Du lernst einerseits wie man einen Debugger benutzt und andererseits viel mehr über die Algorithmen, als ich Dir hier erzählen kann.
       
       MfG
       Martin
       

       • Antwort von nach 4 Tagen 0 hilfreich

         Re^3: Laesst sich mit dyn. Programmierung machen.

         Hi,
         es gab den Hinweis mit der dynamischen Programmierung in der zweiten Teilaufgabe(der Klausur). Bei der ersten Teilaufgabe(das war die Aufgabe, die ich hier hin gepostet habe) gab es dazu kein Hinweis. Ich habe die Aufgabe so geloest, wie ich sie vor einigen Tagen hier beschrieben habe, weil ich den ganzen Kram mit der dynamischen Programmierung so gut wie gar nicht verstanden habe. Ausserdem bin ich nicht in der Lage sowas(z.B. meine vorschlagene Loesung) zu implementieren. Einige Sachen aus der Vorlesung kann ich nicht implementieren(Algorithmen und Datenstrukturen), sondern nur beschreiben, wie z.B. Graphenalgorithmen, Algorithmen in (a,b)-Baeume und Skip-Listen, etc..
         Es geht fuer mich bei dieser Klausur nur um Bestehen(4.0) oder 5.0. Ich habe die Vorlesung „Datenstrukturen und Algorithmen?nur widerwillig gemacht und habe da auch die groessten Schwierigkeiten im Studium. Also, ich habe aus dem ganzen dazugelernt, dass nicht Mathe die Schwierigkeiten in einem Informatistudium sind, sondern die ganzen Vorlesungen aus der theoretischen Informatik
         
         
         Felix Hallo,
         ich habe das ganz anders gemacht. Moechte es mit einem
         Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein
         Betrag, sagen wir mal 12 DM. Dann koennte man folgende
         Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus
         wuerde ich folgendermassen beschreiben:
         1. Tue folgendes bei fuer jeden Muenzbetrag
         1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der
         Betrag<=0 und zaehle die Anzahl der Subtraktionen
         1.2 Falls Betrag = 0, dann brich ab gebe die Anzahl aus und
         gehe zu 1.
         1.3 Falls Betrag< 0, dann addiere v auf den Betrag,
         dekrementiere den Zaehler und gehe zu 1 und suche ein anderen
         Muenzbetrag aus ausser v.
         Wie siehts denn damit aus?
         
         Felix
         1. Das ist halt nicht dynamisch, weil Du fuer jeden M?zbetrag
         auch
         alle Zwischenwerte neu berechnen mu?.
         
         2. Mu?das nicht unbedingt klappen: Gegeben 11 Mark und 2 und
         5 Mark-St?ke. l?ung ist 3*2+5. Wenn wir mit 2 anfangen,
         laufen wir bis -1, dann zu 1 und versuchen dann 1 mit 5
         darzustellen (genauso wenn wir mit 5 anfangen).
         
         3. Nochnals der Rat: Schreib diese Programme doch bitte
         einfach.
         Dann nimmst Du dir einen Debugger und beobachtest das ganze.
         Du lernst einerseits wie man einen Debugger benutzt und
         andererseits viel mehr ?er die Algorithmen, als ich Dir hier
         erz?len kann.
         
         MfG
         Martin
         

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!