[infostudents] Re: Algotheorie Task 2
- From: Jonas Gehring <jonas.gehring@xxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Sun, 21 Dec 2008 23:25:20 +0100
Nachtrag: Ich überlege gerade, ob dein Programm nicht trotz der Tabelle
exponentielle Laufzeit hat und damit ja nicht wirklich dynamische
Programmierung nutzt.
Betrachtet man die sich ändernden Werte pro Runde, so werden doch in der
gleichen Runde alle Schritte, die zu ihnen hingeführt haben, auch berechnet.
Ein kleines Beispiel mit deinen Münzen:
Runde 1:
Tabelle: 4 und 7
Berechnet: 8, 11, 11, 14
Runde 2:
Tabelle: 4, 7, 8, 11 und 14
Berechnet: 8, 11, 11, 14, 12, 15, 15, 18, 18, 21
Runde 3:
Tabelle: 4, 7, 8, 11, 12, 14, 15, 18 und 21
Berechnet: 8, 11, 11, 14, 12, 15, 15, 18, 16, 19, 18, 21, 19, 22, 22, 25,
25, 28
Runde 4:
Tabelle: 4, 7, 8, 11, 12, 14, 15, 16, 18, 19, 21, 22, 25, 28
Berechnet: ...
Das sieht mir irgendwie stark nach dem Baum für die Fibonacci-Berechnung aus,
aber genau begründen kann ich es aus zeitlichen Gründen gerade nicht.
Intuitiv wird aber wie oben bereits gesagt in jeder Runde jeder Wert
praktisch komplett neu berechnet (da alle vorherigen Rechnungen wiederholt
werden).
Wie dem auch sei, sobald du dir die Werte merkst, die sich ändern und im
nächsten Durchlauf nur von diesen aus neue Werte berechnest, geht's
natürlich.
Gruß,
Jonas
On Sunday 21 December 2008 22:38:28 you wrote:
> Hi,
>
> Bitte sag falls ich mich irre, aber nach einem kurzen Blick sieht es für
> mich so aus als ob du einfach alle möglichen auszahlbaren Beträge aufzählst
> und sobald du den gegeben gefunden hast aufhörst. Allerdings generierst du
> die Werte in der Tabelle ständig neu, obwohl sich ja nur wenige ändern.
> Andererseits ist es meiner Meinung nach mit dynamischer Programmierung
> gelöst und deshalb auch richtig. Den Vorteil dynamischer Programmierung
> kann man hier allerdings etwas besser ausnutzen.
>
> Hier ist ein Vorschlag von mir, der genau andersrum rechnet, also den
> auszuzahlenden Betrag rekursiv zerlegt. Der Pseudocode im PDF sollte
> reichen, zur Sicherheit aber auch nochmal in C.
>
>
> Gruß,
> Jonas
>
> On Sunday 21 December 2008 22:17:47 Alexander Nutz wrote:
> > Hallo,
> >
> > im Anhang ist ein Mini-Programm, dass ich zur 2 geschrieben habe - ist
> > recht simpel, tut aber glaub ich schon, was es soll und verwendet auch
> > die Tabelle, wie vorgeschlagen.
> >
> > (ist C-Sharp Code, der eigentliche Code müsste aber fast identisch unter
> > Java laufen..)
> >
> > Die Idee:
> > Lege eine Bool-Tabelle der Größe Zahlbetrag+1 an mit der Bedeutung
> > table[i]=true gdw ich kann betrag i bezahlen
> > initialisiere mit den vorgegebenen Werten
> > so lange sich noch was ändert addiere auf jeden true-Eintrag in der
> > Tabelle jeden Münzwert drauf und trage das Ergebnis wieder in der
> > Tabelle ein.
> > gib den x-ten Eintrag aus
> >
> > Was denkt ihr?
> >
> > Grüße
> > alex
> >
> > SilSie@xxxxxx schrieb:
> > > Hi,
> > >
> > > wenn du zuerst die große Münze "abfragst", findest du vielleicht nicht
> > > immer eine Lösung, obwohl man den Betrag auszahlen könnte... siehe
> > > dazu Vorlesung über Greedy Algorithmen.
> > > Das schwere ist ja, dass wirklich jede Kombination von Münzen den
> > > Betrag ergeben könnte. Wenn man gleich den Betrag der größten abzieht,
> > > lässt man schon viele Möglichkeiten aus.
> > >
> > > Gruß,
> > > Silvan
> > >
> > > Jonas Gehring schrieb:
> > >> Hi,
> > >>
> > >> Ich würde mal so anfangen: Für den Betrag testen ob er größer als eine
> > >> Münze ist (am besten mit der größten anfangen). Falls ja, dann
> > >> rekursiv die Methode für Betrag-Münze aufrufen. Wenn "ja" zurückkommt,
> > >> "ja" zurückgeben, ansonsten es mit der nächstkleineren Münze
> > >> versuchen. Wenn der Betrag gleich ist, dann nat. sofort "ja"
> > >> zurückgeben.
> > >>
> > >> "Dynamisch" kann man das Ganze z.B. so machen, indem man vor jeder
> > >> Rückgabe den Wert in einer Tabelle bzw. in einem Array speichert und
> > >> dieses bei jedem Aufruf zuerst abfragt.
> > >>
> > >> Gruß,
> > >> Jonas
> > >>
> > >> On Wednesday 17 December 2008 22:25:18 Silvan S. wrote:
> > >>> Hi,
> > >>>
> > >>> ich finde die Aufgabe keineswegs trivial. Wenn du dort "Ist dem nicht
> > >>> so probieren wir der Reihe nach den ganzen Array mit Münzwerten
> > >>> durch. " bist, was genau willst du dann machen? Nur auf Teilbarkeit
> > >>> überprüfen? Das reicht doch überhaupt nicht... Es könnte doch -jede-
> > >>> beliebige Kombination von Münzen den gewünschten Betrag x ergeben...
> > >>>
> > >>> Gruß,
> > >>> Silvan
> > >>>
> > >>> don.vito.c@xxxxxx schrieb:
> > >>>> Hallo Lista,
> > >>>>
> > >>>> ich habe mir jetzt eine Menge Gedanken gemacht zu der Aufgabe, aber
> > >>>> ich komme nicht dahinter, warum wir das mit einem Array machen
> > >>>> sollen. Die Aufgabe ist ja eigentlich Erstsemester-mäßig. Ich finde
> > >>>> es ist nämlich viel einfacher, einfach die kleinste Zahl im Array
> > >>>> mit den Münzwerten zu nehmen und zu testen ob sie die andere Zahl
> > >>>> teilt. Ist dem so, so sind wir fertig. Ist dem nicht so probieren
> > >>>> wir der Reihe nach den ganzen Array mit Münzwerten durch.
> > >>>>
> > >>>> Vielleicht kann mir ja mal einer von euch sagen wozu man hier einen
> > >>>> Array von Wahrheitswerten bilden soll. Ich finde da keinen wirklich
> > >>>> guten rekursiven Ansatz.
> > >>>>
> > >>>> Gruß,
> > >>>> Cornelius---
> > >>>> Sent through the Infostudents Mailinglist
> > >>>>
> > >>>> List Archive:
> > >>>> //www.freelists.org/archives/infostudents/
> > >>>>
> > >>>> Subscribe / Unsubscribe:
> > >>>> //www.freelists.org/list/infostudents
> > >>>
> > >>> ---
> > >>> Sent through the Infostudents Mailinglist
> > >>>
> > >>> List Archive:
> > >>> //www.freelists.org/archives/infostudents/
> > >>>
> > >>> Subscribe / Unsubscribe:
> > >>> //www.freelists.org/list/infostudents
Other related posts:
