Weiß jemand wie man dieses Programm schreibt?

[MoxxiManagarm]

Kannst du mir vielleicht erklären was du damit genau ausdrücken willst?:

Nehmen wir das Beispiel 28. Die Methode Wechselgeld bekommt 28 als Parameter übergeben, damit ist betrag = 28. Und auch rest wird damit 28.
Dann schaust du dir die verfügbaren Geldbeträge an und findest 10. Damit erhöhst du die anzahl um 1 und reduzierst den rest um diesen Betrag 10. Damit ist rest nur noch 18. Weil rest damit noch größer als 0 ist fängt die Schleife von vorne an. Du findest wieder 10, anzahl wird erhöht und dein Rest ist 8. Schleifenwiederholung Rest ist 3, dann 1, dann 0. Erst bei 0 wird die Schleife nicht mehr wiederholt und die Methode wird beendet mit der Anzahl.

 

[Gelöschtes Mitglied 64282]

Nehmen wir das Beispiel 28. Die Methode Wechselgeld bekommt 28 als Parameter übergeben, damit ist betrag = 28. Und auch rest wird damit 28.
Dann schaust du dir die verfügbaren Geldbeträge an und findest 10. Damit erhöhst du die anzahl um 1 und reduzierst den rest um diesen Betrag 10. Damit ist rest nur noch 18. Weil rest damit noch größer als 0 ist fängt die Schleife von vorne an. Du findest wieder 10, anzahl wird erhöht und dein Rest ist 8. Schleifenwiederholung Rest ist 3, dann 1, dann 0. Erst bei 0 wird die Schleife nicht mehr wiederholt und die Methode wird beendet mit der Anzahl.

Okay das habe ich verstanden, danke! Das muss jetzt nur noch übersetzt werden.. 😂 Ihr denkt auch ich bin doof.

 

[Gelöschtes Mitglied 64282]

Ich würde das als ersten Anfang durchaus durchgehen lassen. @mihe7 hat zwar aufgeteilt, aber er hat da evtl. etwas zu viel auf einmal genommen.

Also einfach einmal die Aufgabe wirklich Satz für Satz abhaken:

1. Implementieren Sie in einer Klasse Kohle Münzgeldrückgaben. Dazu sind verschiedene verfügbare Münzwerte vorgegeben.
2. 1. Implementieren Sie eine Methode Wechselgeld , die den auszugebenden Betrag als Parameter vom Typ int übergeben bekommt.
3. Die zur Verfügung stehenden Münzwerte sind 1, 2, 5 und 10.
4. Realisieren Sie die Münzrückgabe als Greedy-Algorithmus, sodass immer die größtmögliche Münze gewählt wird, die den noch auszugebenden Restbetrag nicht übersteigt.
5. Zusätzlich soll die jeweils gewählte Münze auf der Konsole ausgegeben
6. und am Ende soll die Gesamtzahl der ausgegebenen Münzen als Rückgabewert von der Methode zurückgegeben werden.

Wenn man das so aufteilt, dann kann man 1. und 2. erst einmal als abgehakt ansehen (So die schließenden Klammern auch da sind und das in einer Datei Kohle.java steht .. Es gibt also Randbedingungen, die wir nicht prüfen können. Aber Du solltest da etwas haben, das du übersetzen kannst (Entweder in einer Entwicklungsumgebung wird nichts angemeckert oder du rufst z.B. javac Kohle.java auf um es auf der Kommandozeile zu übersetzen.)

Da müsste man jetzt nur weiter machen. Die nächste Information ist erst einmal nicht so wirklich hilfreich in Sache Algorithmus. Aber zusammen mit 4. kannst Du evtl. beschreiben, wie Du vorgehen würdest, wenn Du es machen solltest: Du hast unbegrenzt 1, 2, 5 und 10 Cent Münzen und sollst mir 78 Cent geben. Wie gehst Du vor?

Vo

Das ist schon besser, aber da fehlt immer noch etwas....

So lange, wie der Restbetrag größer ist, als der Wert der Münze, nehme ich eine solche Münze und gebe es aus, erhöhe die Anzahl der benötigten Münzen um 1 und reduziere den Restbetrag um den Wert der Münze .

Worauf ich hinaus will ist: Du musst exakt werden. Im Code musst Du exakt sein. Da geht kein Wischi Waschi und nach meiner Erfahrung scheitert es genau an der Stelle. Du hast Dir das noch nicht exakt durchdacht und daher kann es nicht klappen!

Jetzt hast Du es deutlich formuliert und damit kann es 1:1 übersetzt werden:
a) Solange eine Bedingung erfüllt ist, mache ich etwas -> while (Bedingung) { Mache etwas }
b) Bedingung restbetrag > muenzenwert. -> Kann man also auch gut umsetzen
c) Ausgabe "Nehme Münze ...", anzahlMuenzen++ wäre eine Erhöhung der Anzahl der Münzen. Die Variable muss natürlich deklariert und initialisiert werden ... Restbetrag reduzieren: restbetrag = restwert - muenzwert;

Daher mein Ratschlag: Stell es Dir genau vor. Überleg genau, was Du machst. So ein Weg ist ok.

Du kannst aber auch gerne rechnen. Wenn es das ist, was Du machst, dann hast Du ein restwert / muenzwert als Anzahl der Münzen die du brauchst und restwert = restwert % muenzwert wäre der Rest.

Aber wie gesagt: Der Weg selbst ist mir egal. Nur stell es Dir exakt vor!

Und ein möglicher Zwischenschritt: Arbeite mit Stift und Zettel und du schreibst alles auf. Denn dann merkst Du, was Du alles brauchst / dir merken musst. Im Kopf merken gilt dabei nicht!

Das wird später einfacher werden, wenn Du das einfach "im Kopf machst". Aber wie gesagt: Wenn Du nicht durchdacht hast, was Du genau machen willst, dann wird das im Code scheitern. Das reale vorstellen ist halt in der Regel deutlich einfacher als es abstrakt im Code zu machen.

Voll gut erklärt danke

 

[temi]

Fangen wir mal an:
Du hast 78 Cent, die du in Münzen ausgeben willst.
Dir stehen 10, 5, 2 und 1 Cent Münzen zur Verfügung.
Du beginnst mit dem größten Münzwert: 10 Cent
78 Cent sollen es sein, 10 Cent ist weniger, also geht das.
Du gibst eine Münze aus, der Restbetrag ist 68 Cent.
10 Cent ist immer noch weniger als 68 Cent.
Du gibst eine weitere Münze aus, der Restbetrag ist 58 Cent.
...
10 Cent ist mehr als 8 Cent, du musst zum nächsten Münzwert übergehen.
5 Cent ist weniger als 8 Cent, das geht.
Du gibst eine Münze aus, der Restbetrag ist 3 Cent.
...

 

[kneitzel]

Voll gut erklärt danke

Ich würde mich freuen, wenn ich Dir damit geholfen habe. Mir geht es halt auch darum, dir etwas den Weg zu ebnen für zukünftige Aufgaben. Auch bei der Fehlersuche kommen Stift und Zettel am Anfang ganz gut (nur da geht es dann anders herum - man hat Code und geht den dann manuell durch )

Bei meiner Erläuterung nur aufpassen - ich war nicht sorgfältig genug mit den Namen... wird z.B. hier deutlich: "restbetrag = restwert - muenzwert" - das muss natürlich restbetrag = restbetrag - muenzwert heißen.... also da aufpassen mit Variablen und deren Namen ... Diese Nachlässigkeit tut mir leid, aber ich hoffe, dass dies nicht zu sehr verwirrt.

 

[BestGoalkeeper]

In der Aufgabenstellung steht doch schon genau was du machen sollst...

 

[Gelöschtes Mitglied 64282]

In der Aufgabenstellung steht doch schon genau was du machen sollst...

Ich mach das ganze erst seit 2 Wochen sei bitte gnädig 😂

 

[Gelöschtes Mitglied 64282]

Fangen wir mal an:
Du hast 78 Cent, die du in Münzen ausgeben willst.
Dir stehen 10, 5, 2 und 1 Cent Münzen zur Verfügung.
Du beginnst mit dem größten Münzwert: 10 Cent
78 Cent sollen es sein, 10 Cent ist weniger, also geht das.
Du gibst eine Münze aus, der Restbetrag ist 68 Cent.
10 Cent ist immer noch weniger als 68 Cent.
Du gibst eine weitere Münze aus, der Restbetrag ist 58 Cent.
...
10 Cent ist mehr als 8 Cent, du musst zum nächsten Münzwert übergehen.
5 Cent ist weniger als 8 Cent, das geht.
Du gibst eine Münze aus, der Restbetrag ist 3 Cent.
...

Das verstehe ich. Aber ich weiß nicht wie man das als Programm schreibt. Mir fehlen auch manche Begrifflichkeiten zu den Schleifen z.B.

 

[MoxxiManagarm]

Ich möchte nochmal für dich klarstellen @LJO, dass es grundsätzlich 2 Vorgehen gibt.
1. Das methodische Vorgehen, welches ich beschrieben habe
2. Das mathematisch Vorgehen

Einzig und allein wegen dem Satz "Zusätzlich soll die jeweils gewählte Münze auf der Konsole ausgegeben" klingt es für mich so, als wäre das methodische Vorgehen das Ziel, wobei dir meisten hier (inkl. mir) eher das mathematische Vorgehen verwenden würden wenn dieser Satz nicht wäre. Bei dem mathematischen Vorgehen hättest du keine while-Schleife, sondern maximal eine for-Schleife, welche über die verfügbaren Münzgrößen iteriert.

 

[kneitzel]

Fangen wir mal an:
Du hast 78 Cent, die du in Münzen ausgeben willst.
Dir stehen 10, 5, 2 und 1 Cent Münzen zur Verfügung.
Du beginnst mit dem größten Münzwert: 10 Cent
78 Cent sollen es sein, 10 Cent ist weniger, also geht das.
Du gibst eine Münze aus, der Restbetrag ist 68 Cent.
10 Cent ist immer noch weniger als 68 Cent.
Du gibst eine weitere Münze aus, der Restbetrag ist 58 Cent.
...
10 Cent ist mehr als 8 Cent, du musst zum nächsten Münzwert übergehen.
5 Cent ist weniger als 8 Cent, das geht.
Du gibst eine Münze aus, der Restbetrag ist 3 Cent.
...

Das ist übrigens der Ansatz, wie man immer manuell anfangen kann ...
Also erst wirklich die Schritte so aufschreiben. Also noch ganz ohne Schleife.
78 Cent -> 10 Cent geben, Rest 68 Cent
68 Cent -> 10 Cent geben, Rest 58 Cent
...
18 Cent -> 10 Cent geben, Rest 8 Cent

Und wenn man das hat, ist der zweite Schritt: Ich sehe, dass ich da ständig das gleiche mache - also versuche ich es, zusammen zu fassen.
Wieso habe ich bei 8 Cent aufgehört? -> 8 Cent ist kleiner als 10 Cent.
Was habe ich da immer gemacht? 10 Cent geben, Vorne steht Rest, hinten steht Rest - 10 Cent. Und das ist der neue Rest-Wert im nächsten Durchgang.
==> So entsteht die Schleife.

Das lässt sich 1:1 auch übertragen:
- Du machst es für 10 Cent
- Du machst es für 5 Cent
- Du machst es für 2 Cent
- Du machst es für 1 Cent
Das ist also auch eine Schleife. Du machst immer das Gleiche. Also für jeden Münzwert machst Du es einmal, wobei die Münzwerte sortiert sind.
Das wäre also wieder eine Schleife und die Münzwerte können - so wie Du es schon richtig hattest - in einem Array abgelegt sein. Die Schleife geht also das Array durch und macht da etwas ...

Das auch nur einfach als mögliche Vorgehensweise.

Viele dieser Vorgehen muss man paar Mal gemacht haben, denn diese kommen immer wieder. Das wird also von Mal zu Mal einfacher. Aber vielleicht hilft es, Dir das etwas bewusst zu machen. Später läuft sowas automatisch ab. Da braucht man es in diesem Detail nicht mehr aufschreiben. Aber das wiederholt sich auch durchaus auf anderen Ebenen. Dann spricht man halt über Pattern oder so (Aber das ist etwas, das Du jetzt erst einmal ignorieren kannst!)

 

[mihe7]

Wir wollen Code sehen!

 

[kneitzel]

Das verstehe ich. Aber ich weiß nicht wie man das als Programm schreibt. Mir fehlen auch manche Begrifflichkeiten zu den Schleifen z.B.

Kannst Du denn einmal versuchen, das erarbeitete nur für die 10 Cent Münze als Code zu schreiben?
Du hast ja schon:

public class Kohle {
    public static int Wechselgeld (int decimal) {
        return 0;
    }
}

decimal ist also der Betrag in Cent. Und du willst:
Solange der (Rest)betrag > als 10 Cent ist, willst Du Ausgaben: "10 Cent Münze gegeben" und den (Rest)Betrag um 10 Cent reduzieren.

 

[MoxxiManagarm]

Ich mach das ganze erst seit 2 Wochen sei bitte gnädig 😂

Das ist im übrigen sehr grenzwertig. Und ich hoffe du verstehst mich jetzt nicht falsch. Aber wir befinden uns hier in einem Forum. Wir versuchen Probleme zu lösen. Natürlich ist das Große Ganze dieser Aufgabe für dich ein Problem, das verstehe ich, aber es stellt sich heraus, dass dir massiv Grundlagen fehlen. Damit brauchst du eigentlich eher Nachhilfe. Dafür ist ein Forum eigentlich nicht geeignet und das, was wir hier gerade tun, entspricht einer Nachhilfe. Du merkst aber sicher, dass die Diskussion dadurch stark ausartet.

 

[Gelöschtes Mitglied 64282]

Das ist im übrigen sehr grenzwertig. Und ich hoffe du verstehst mich jetzt nicht falsch. Aber wir befinden uns hier in einem Forum. Wir versuchen Probleme zu lösen. Natürlich ist das Große Ganze dieser Aufgabe für dich ein Problem, das verstehe ich, aber es stellt sich heraus, dass dir massiv Grundlagen fehlen. Damit brauchst du eigentlich eher Nachhilfe. Dafür ist ein Forum eigentlich nicht geeignet und das, was wir hier gerade tun, entspricht einer Nachhilfe. Du merkst aber sicher, dass die Diskussion dadurch stark ausartet.

Mir muss doch auch niemand helfen der das nicht möchte. Ich tu mich eben sehr schwer damit und habe deshalb um Hilfe gebeten und freue mich auch darüber. Ich dachte ihr macht das eben schon länger und für euch ist das ein Klax.

 

[kneitzel]

Mir muss doch auch niemand helfen der das nicht möchte. Ich tu mich eben sehr schwer damit und habe deshalb um Hilfe gebeten und freue mich auch darüber. Ich dachte ihr macht das eben schon länger und für euch ist das ein Klax.

Die Aufgabenstellung wäre für uns ein Klax. Nur es ist Dir ja nicht damit geholfen, dass wir das schnell lösen können. Du musst verstehen, wie das funktioniert.

Und die Frage ist, wie dieses Wissen vermittelt werden kann, das Dir fehlt. In einem Forum ist dies sehr schwer. Bei einer Nachhilfe könnte man viel besser auf Dich eingehen, Probleme identifizieren. Es würde ggf. eine Lösung vorgegeben aber du würdest direkt eine andere Aufgabe bekommen. Das wäre also ein ganz anderes Vorgehen, das möglich würde: Man kann direkt die Lösung einmal zeigen.
Das geht hier aber nicht:
a) Das müsste ausgearbeitet werden - da ja nicht nur die Lösung sondern auch der Lösungsweg wichtig ist incl. Erläuterungen ist das etwas, das nicht mal eben so geschrieben wird.
b) Deine Problematik ist für Dich die Aufgabe. Sobald Du eine Lösung hast, ist Deine Motivation da jetzt weiter zu machen, gering. Zumal von uns ja auch keine weitere Führung kommen dürfte ist es danach erst einmal vorbei und das hat Dir dann nicht geholfen. In wenigen Tagen bist Du da, wo Du jetzt auch bist. Nur eben hast Du eine andere Aufgabe, vermutlich mit gesteigerter Schwierigkeit und die wirst Du nicht bearbeiten können ...

Daher fürchte ich, dass das Forum da keine wirkliche Hilfe bieten kann - auch wenn ich es versucht habe (Wobei man meinen Ansatz mit geteilter Meinung sehen kann. Ich habe halt etwas überlegt, was Dir ggf. fehlt um solche Aufgaben generell lösen zu können.... Und da war ein Punkt eben dieses genaue Visualisieren, was da passieren soll / muss.)

Aber kriegst Du das hin, was ich hier geschrieben habe?

Kannst Du denn einmal versuchen, das erarbeitete nur für die 10 Cent Münze als Code zu schreiben?
Du hast ja schon:

public class Kohle {
    public static int Wechselgeld (int decimal) {
        return 0;
    }
}

decimal ist also der Betrag in Cent. Und du willst:
Solange der (Rest)betrag > als 10 Cent ist, willst Du Ausgaben: "10 Cent Münze gegeben" und den (Rest)Betrag um 10 Cent reduzieren.

Wir können da versuchen, jetzt Schritt für Schritt zum Ziel zu kommen ...

 

[MoxxiManagarm]

Mir muss doch auch niemand helfen der das nicht möchte. Ich tu mich eben sehr schwer damit und habe deshalb um Hilfe gebeten und freue mich auch darüber.

Ich meinte ja du sollst mich nicht falsch verstehen ;-) Ich möchte dir helfen, und du siehst ich versuche das auch. Aber der Beitrag ist schon sehr lang ohne dass ich das Gefühl habe, dass wir wirklich voran kommen. Das liegt u.a. daran, dass ein Forum kein geeignetes Medium ist um so tiefgründig auf dich eingehen zu können wie du es, zumindest jetzt gerade, benötigst. Falls die Aufgabe aus einem Studium stammt, gibt es da nicht immer Tutorenprogramme, wo ältere Semester die jüngeren unterstützen?

Ich dachte ihr macht das eben schon länger und für euch ist das ein Klax.

Ja, wir machen das schon länger und ja das ist ein Klax. Aber nicht zuletzt die Ethik verbietet es uns Lösungen auf dem Silbertablett anzubieten. Hilfe zur Selbsthilfe ist der bessere Weg, aber dieser Weg ist in deinem Fall äußerst steinig

 

[Gelöschtes Mitglied 64282]

Ich meinte ja du sollst mich nicht falsch verstehen ;-) Ich möchte dir helfen, und du siehst ich versuche das auch. Aber der Beitrag ist schon sehr lang ohne dass ich das Gefühl habe, dass wir wirklich voran kommen. Das liegt u.a. daran, dass ein Forum kein geeignetes Medium ist um so tiefgründig auf dich eingehen zu können wie du es, zumindest jetzt gerade, benötigst. Falls die Aufgabe aus einem Studium stammt, gibt es da nicht immer Tutorenprogramme, wo ältere Semester die jüngeren unterstützen?



Ja, wir machen das schon länger und ja das ist ein Klax. Aber nicht zuletzt die Ethik verbietet es uns Lösungen auf dem Silbertablett anzubieten. Hilfe zur Selbsthilfe ist der bessere Weg, aber dieser Weg ist in deinem Fall äußerst steinig

Da hast du recht 😂 Ich bin aber auch leider jemand der super gerne mir Lösungen lernt. Ich kann so einfach besser denken und verstehen. Vielleicht finde ich jemanden der es mir macht weil so wird das hier heute denke ich nichts mehr. Danke trotzdem für eure Hilfe.

 

[Gelöschtes Mitglied 64282]

Die Aufgabenstellung wäre für uns ein Klax. Nur es ist Dir ja nicht damit geholfen, dass wir das schnell lösen können. Du musst verstehen, wie das funktioniert.

Und die Frage ist, wie dieses Wissen vermittelt werden kann, das Dir fehlt. In einem Forum ist dies sehr schwer. Bei einer Nachhilfe könnte man viel besser auf Dich eingehen, Probleme identifizieren. Es würde ggf. eine Lösung vorgegeben aber du würdest direkt eine andere Aufgabe bekommen. Das wäre also ein ganz anderes Vorgehen, das möglich würde: Man kann direkt die Lösung einmal zeigen.
Das geht hier aber nicht:
a) Das müsste ausgearbeitet werden - da ja nicht nur die Lösung sondern auch der Lösungsweg wichtig ist incl. Erläuterungen ist das etwas, das nicht mal eben so geschrieben wird.
b) Deine Problematik ist für Dich die Aufgabe. Sobald Du eine Lösung hast, ist Deine Motivation da jetzt weiter zu machen, gering. Zumal von uns ja auch keine weitere Führung kommen dürfte ist es danach erst einmal vorbei und das hat Dir dann nicht geholfen. In wenigen Tagen bist Du da, wo Du jetzt auch bist. Nur eben hast Du eine andere Aufgabe, vermutlich mit gesteigerter Schwierigkeit und die wirst Du nicht bearbeiten können ...

Daher fürchte ich, dass das Forum da keine wirkliche Hilfe bieten kann - auch wenn ich es versucht habe (Wobei man meinen Ansatz mit geteilter Meinung sehen kann. Ich habe halt etwas überlegt, was Dir ggf. fehlt um solche Aufgaben generell lösen zu können.... Und da war ein Punkt eben dieses genaue Visualisieren, was da passieren soll / muss.)

Aber kriegst Du das hin, was ich hier geschrieben habe?


Wir können da versuchen, jetzt Schritt für Schritt zum Ziel zu kommen ...

Ich weiß echt nicht wie ich anfangen soll..

 

[MoxxiManagarm]

Und wenn es bei den Aufgaben 1 und 2 nicht so richtig klappen will, so kannst du auch immer noch Punkte mit den Aufgaben 3 und 4 absahnen. 3 würde dann halt nicht funktionale Methoden aufrufen, aber wäre umgesetzt. Für 4 brauchst du nicht mal einen Programmcode. Du musst wie gesagt nur verschiedene Beträge für die Münzen {1, 3, 6, 8} durchspielen (nach dem bisherigen Vorgehen) und schauen ob es offensichtlich eine andere Lösung mit weniger Münzen gibt. Mach dir dafür ruhig eine Tabelle, fang meinetwegen bei 1 an.

Betrag	Münzen nach dem bisherigen Vorgehen	Lösung mit weniger Münzen?
1	1	-
2	1 1	-
3	3	-
4	3 1	-
5	3 1 1	-
6	6	-
7	6 1	-
8	6 1 1	-
9	8 1	(nur gleich viele Münzen 6 3)

Tipp: Du muss nicht mehr viele Zahlen gehen bis du in dieser Tabelle einen solchen Fall finden würdest

 

[mihe7]

Ich weiß echt nicht wie ich anfangen soll..

Schritt für Schritt. Hier nochmal das Skelett mit Kommentar:

public class Kohle {

    /** Gibt die benötigten Münzen am Bildschirm aus,
      * um betrag mit Wechselgeld auszuzahlen und
      * gibt die Anzahl der benötigten Münzen zurück.
      *
      * @param  betrag  der auszuzahlende Betrag.
      * @return Anzahl für das Wechselgeld benötigte Münzen.
      */
    public static int Wechselgeld (int betrag) {
        return 0;
    }
}

Der Code liefert das korrekte Ergebnis, für den Fall, dass Kohle.Wechselgeld(0) aufgerufen wird, d. h. falls betrag == 0 gilt.

Aufgabe: passe den Code so an, dass er auch für Kohle.Wechselgeld(1) das korrekte Ergebnis liefert.

 

[BestGoalkeeper]

Ganz so einfach ist es nicht auf den optimalen Algorithmus zu kommen...
Ich habe jetzt herausgefunden, dass du solange (Betrag >= 14) gilt den greedy Ansatz verfolgen kannst - und danach leider in die Innereien musst:

Spoiler

    public static int wechselgeld(int betrag, int threshold, boolean print) {
        if (print) {
            System.out.println(betrag);
        }
        List<Integer> t1 = new LinkedList<>();
        List<Integer> t2 = new LinkedList<>();
        while (betrag >= threshold) {
            betrag -= 8;
            t1.add(8);
            t2.add(8);
        }
        for (int i = betrag; i >= 0; i--) {
            t2.add(1);
        }
        int i = wechselgeld(betrag, t1, t2);
        if (print) {
            System.out.println(i);
            System.out.println(t2);
        }
        return i;
    }

    public static int wechselgeld(int betrag, List<Integer> temp, List<Integer> best) {
        int[] m = { 8, 6, 3, 1 };
        for (int i = 0; i < m.length; i++) {
            if (betrag - m[i] >= 0) {
                temp.add(m[i]);
                wechselgeld(betrag - m[i], temp, best);
                if (betrag - m[i] == 0 && temp.size() < best.size()) {
                    best.clear();
                    best.addAll(temp);
                }
                temp.remove(temp.size() - 1);
            }
        }
        return best.size();
    }

    public static void main(String[] args) {
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 12, false)).sum());
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 13, false)).sum());
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 14, false)).sum()); // optimal threshold
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 15, false)).sum());

        wechselgeld(13, 14, true);
    }

 

[MoxxiManagarm]

Ich habe jetzt herausgefunden, dass du solange (Betrag >= 14) gilt den greedy Ansatz verfolgen kannst

Wie kommst du auf 14?

 

[mihe7]

Ganz so einfach ist es nicht auf den optimalen Algorithmus zu kommen...

Doch, weil für je drei Münzen a, b, c mit a < c und b < c gilt: a+b <= c.

 

[BestGoalkeeper]

Wie kommst du auf 14?

14-8=6 -> 6, 15-8=7 -> 6 1, 16-8=8 -> 8, 17-8=9 -> 8 1, 18-8=10 -> 8 1 1, 19-8=11 -> 8 3, 20-8=12 -> 6 6 (nicht 8 3 1), 21-8=13 -> 6 6 1 (nicht 8 3 1 1)
wäre der Threshold 13 dann 21-8-8=5 -> 8 3 1 1 vs 6 6 1.

Doch, weil für je drei Münzen a, b, c mit a < c und b < c gilt: a+b <= c.

Wie meinst du das? Ist #71 falsch?

 

[MoxxiManagarm]

Und was ist mit 12?
8 3 1 (greedy) vs 6 6

 

[BestGoalkeeper]

12 liegt ja unter dem Threshold von 14, es würde also richtig 6 6 berechnet werden vom Algorithmus...

@mihe7 Ich bezog mich auf den zweiten Aufgabenteil

 

[MoxxiManagarm]

Ich raff's nicht, wo in der Aufgabe steht denn etwas anderes als Greedy?

 

[BestGoalkeeper]

Ich raff's nicht, wo in der Aufgabe steht denn etwas anderes als Greedy?

Achso! Nirgendwo, aber da im zweiten Aufgabenteil der Greedy nicht mehr optimal ist, habe ich einen Nicht-Greedy-Ansatz hinzugefügt...

 

[MoxxiManagarm]

Achso, aber ich glaube das verwirrt LJO eher nur noch mehr 😅

 

[mihe7]

@mihe7 Ich bezog mich auf den zweiten Aufgabenteil

Ach so. Dann ist das eben die Erklärung, warum der Algorithmus nicht mehr optimal ist

 

[Meniskusschaden]

Wie kommst du auf 14?

Verstehe ich auch nicht. Bei 18 wäre doch 6+6+6 optimal und nicht 8+8+1+1.

 

[BestGoalkeeper]

Verstehe ich auch nicht. Bei 18 wäre doch 6+6+6 optimal und nicht 8+8+1+1.

Upps... Ja ihr vollkommen recht, 19 wäre der optimale Threshold: (bis 19 darf man noch -8 rechnen, darunter nicht mehr)

    public static int wechselgeld(int betrag, int threshold, boolean print) {
        if (print) {
            System.out.println(betrag);
        }
        List<Integer> t1 = new LinkedList<>();
        List<Integer> t2 = new LinkedList<>();
        while (betrag >= threshold) {
            betrag -= 8;
            t1.add(8);
            t2.add(8);
        }
        for (int i = betrag; i >= 0; i--) {
            t2.add(1);
        }
        int i = wechselgeld(betrag, t1, t2);
        if (print) {
            System.out.println(i);
            System.out.println(t2);
        }
        return i;
    }

    public static int wechselgeld(int betrag, List<Integer> temp, List<Integer> best) {
        int[] m = { 8, 6, 3, 1 };
        for (int i = 0; i < m.length; i++) {
            if (betrag - m[i] >= 0) {
                temp.add(m[i]);
                wechselgeld(betrag - m[i], temp, best);
                if (betrag - m[i] == 0 && temp.size() < best.size()) {
                    best.clear();
                    best.addAll(temp);
                }
                temp.remove(temp.size() - 1);
            }
        }
        return best.size();
    }

    public static void main(String[] args) {
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 12, false)).sum());
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 13, false)).sum());
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 14, false)).sum()); // non-optimal threshold
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 15, false)).sum());
        
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 18, false)).sum());
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 19, false)).sum()); // optimal threshold
        System.out.println(IntStream.rangeClosed(0, 100).map(i -> wechselgeld(i, 20, false)).sum());

        wechselgeld(18, 14, true);
        wechselgeld(18, 19, true);
    }

Hab gar nicht so weit gedacht...

 

[Gelöschtes Mitglied 64282]

Weiß wer wie man seinen Beitrag löschen kann? Würde das gerne machen.

 

[mihe7]

Weiß wer wie man seinen Beitrag löschen kann? Würde das gerne machen.

Gar nicht. Evtl. kann Dir @mrBrown weiterhelfen, oder Du versuchst es mal über den Report-Link des betreffenden Beitrags. Ein ganzes Thema wird man aber vermutlich nicht entfernen.

 

[BestGoalkeeper]

Weiß wer wie man seinen Beitrag löschen kann? Würde das gerne machen.

Das klingt doch jetzt sehr nach dem Erschleichen einer Lösung