Erste Schritte Rechnen mit Schleifen? Denkanstoß gesucht

[woopwoop]

Hallo zusammen,

ich habe in der Schule Java und bin momentan dabei mich einzuarbeiten.
Ich stehe vor einen Problem an dem ich schon ne Weile arbeite und bräuchte dazu ein paar Denkanstöße.

Ich habe 100€. Dafür soll ich Kombinationen ausgeben mit welchen Scheinen ich das abbilden kann. (Hier in dem Fall 20er, 10er, 5er).
Also z.B.
Lösung 1: 5x20er
Lösung 2: 5x20er, 2x10er
usw.

Ich habe überlegt dass ich dazu vermutlich schleifen benötige, hab aber überhaupt keinen Ansatz wie ich damit alle Varianten abdecken soll.

Hat jemand einen Tipp für mich?

Gruß

 

[Meniskusschaden]

Ich habe überlegt dass ich dazu vermutlich schleifen benötige

Ja, so könntest du das machen. Drei ineinandergeschachtelte Schleifen, jede zählt eine Schein-Sorte hoch. Dann musst du innen nur noch prüfen ob der Wert stimmt und ggfs. die Zähler ausgeben.

 

[Xyz1]

@Meniskusschaden Dynamische Programmierung möglich? Ernstgemeinte Frage. Wenn ja was wie?

Erbitte Ratschlag.

@woopwoop Genau SO (wie nach Meniskusschaden dargelegt) solltest Du nach Deinem Kenntnisstand das machen!

 

[Meniskusschaden]

@Meniskusschaden Dynamische Programmierung möglich?

Hm, bin nicht sicher, ob es geht bzw. etwas bringt. Es wird ja auch nicht die optimale Lösung gesucht, sondern alle Lösungen. Man könnte es natürlich in ein Optimierungsproblem abwandeln, etwa den Betrag in möglichst wenig Scheine aufzuteilen. Aber da scheint mir - zumindest bei unseren Scheinsorten - auch ein einfacher Greedy-Algorithmus zu genügen.

 

[Xyz1]

Jetzt bin ich genausoschlau wie vorher.
Vielleicht weiß @mihe7 ein klein wenig dazu!

 

[Xyz1]

Doch ich habs.

Ein eindimensionales dynamisches Optimierungsprogrammierungsproblem - auf der man sich vor und zurück bewegt.

Unterscheidet sich aber natürlich nicht vom gefräßigem Ansatz in der Laufzeit....

Ich werde das gleich ma implementieren.

 

[mihe7]

Vielleicht weiß @mihe7 ein klein wenig dazu!

Wie komm ich zu der Ehre?!?

Ich sehe es wie @Meniskusschaden. Um die Minimalzahl an Scheinen zu ermitteln, dürfte Greedy reichen, weil jeder größere Schein mindestens zwei kleinere Scheine ersetzt.

public class Scheine {
    public static final int[] WERTE = {500,200,100,50,20,10,5};

    public int[] scheine(int wert) {
        int[] result = new int[WERTE.length];
        for (int i = 0; i < WERTE.length; i++) {
            result[i] = wert / WERTE[i];
            wert -= result[i] * WERTE[i];
            // oder wert %= WERTE[i];
        }
        return result;
    }
}

 

[Xyz1]

@mihe7 und @Meniskusschaden
Da wir schon bei Lösungen sind Damit ginge es - weiß nicht genau wieso und lässt sich natürlich noch vereinfachen

public static void main(String[] args) {
    int[] werte = {50, 20, 10};
    int[] scheine = new int[werte.length];
    int wert = 0;
    for (int i = 0; i >= 0;) {
        //System.out.println(i);
        if (i == werte.length) {
            if (wert == 100) {
                System.out.println(Arrays.toString(scheine));
            }
            i--;
            scheine[i] = scheine[i] + 1;
            wert = wert + werte[i];
        } else {
            if (wert > 100) {
                wert = wert - werte[i] * scheine[i];
                scheine[i] = 0;
                i--;
                if (i >= 0) {
                    scheine[i] = scheine[i] + 1;
                    wert = wert + werte[i];
                }
            } else {
                i++;
            }
        }
    }
}

Und es gibt aus

0, 0, 10
0, 1, 8
0, 2, 6
0, 3, 4
0, 4, 2
0, 5, 0
1, 0, 5
1, 1, 3
1, 2, 1
2, 0, 0

 

[Xyz1]

@Meniskusschaden Ist das noch Greedy?

 

[mihe7]

@DerWissende letztlich definieren wir beide ein Stellenwertsystem, nennen wir es mal monetär. Während bei mir der Wert im Prinzip einfach von dezimal zu monetär umgerechnet wird, zählst Du im monetären System durch und gibst die monetäre Zahl aus, sobald sie dem dezimalen Wert entspricht. Dabei wird aber nichts optimiert.

 

[Xyz1]

@mihe7 Eigentlich hätte ich das anders gemacht, aber wir sind ja hier im Anfänger-Thema .... er soll auch etwas nachdenken IMO
Ob und wenn ja wie optimiert werden kann - das erscheint mir sehr nebulös

 

[woopwoop]

Wow ihr seid ja richtig aktiv. Ich werde erstmal sehn was ich mit den Infos anfangen kann. Vielen Dank schon mal

Edit: hab grade gesehn dass ihr Arrays benutzt habt, das sollen wir explizit nicht machen da wir das noch nicht "können" :/

 

[mihe7]

hab grade gesehn dass ihr Arrays benutzt habt, das sollen wir explizit nicht machen da wir das noch nicht "können"

Gut, dann kannst Du Dir selbst auch noch was überlegen

 

[woopwoop]

Aber wenn ich mir eine Funktion schreibe die mir die Berechnung machen soll, kann ich ja nur einen Wert (zB für die 20er ein int 20) von dieser zurück geben lassen? Muss ich dann immer eine eigene machen?

 

[mihe7]

kann ich ja nur einen Wert (zB für die 20er ein int 20) von dieser zurück geben lassen?

Ja, und?

 

[Xyz1]

kann ich ja nur einen Wert (zB für die 20er ein int 20) von dieser zurück geben lassen

Bei meiner Schleife können alle Werte eingesetzt werden auch 1 oder 97 oder so etwas zB.