Python - Listen, Greedy Algorithm

Aufrufe: 1896     Aktiv: 11.04.2020 um 22:52

0

So. Es geht weiter. Ich bin nun seit Vorgestern bei Aufgabe 4.7 von diesem schönen Blatt hier https://www.math.uni-bielefeld.de/~frettloe/teach/vorkurs/Aufgaben.pdf . Es soll ein beliebiger Betrag in Cent eingelesen werden. Also anstelle von 15,53€, sollen es 1553Cent sein. Diese möchte ich dann in beliebige, jedoch passende Münzen stückeln und ausgeben. Entweder als lange Liste ->['2Euro', '2Euro', '2Euro',(...),'2Cent', '2Cent', '1Cent'] oder als kurze Liste mit counter({'2Euro':3,(...)}).

Betrag_input = int(input("Geben Sie den Betrag in Cent an:\n"));

Betrag = [int(i) for i in str(Betrag_input)];
Betrag.reverse(); #Liste umdrehen, damit ich die Centwerte vorne habe
Münzen = [];
#twoCent = [] 
i = 0;
print(Betrag) #Kontrolle

while i <= len(Betrag): #Solange Zähler kleiner als die Anzahl der Elemente in Liste
    #n = 0;
    k = 0;
    for char in Betrag: #für das jeweilige Element in der List eist folgendes zu tun
        if char %2 != 0: #Ist zahl ungerade?
            char -= 1;
            k = 1; #Da ungerade, auf jeden Fall 1 Centstück vorhanden
            #Münzen.append('1Cent')
            if char %2 ==0: 'ja?, dann folgendes.
                n = char/2;
                round(n);
                n = int(n);
                char -=n*2;

            elif char ==1: 
                k = 1;


        elif char %2 ==0: #ist Zahl gerade?
            n = char/2;
            round(n);
            n = int(n)
            char -=n*2;
        if k == 0:
            print("Das war kein gültiger Betrag")
            break
    i += 1;
    del Betrag[0] #lösche den 'char' aus der Liste
    #twoCent.extend(['2Cent'*n]);
   # twoCent.split('t')
    Münzen.extend(['1Cent'*k, '2Cent, '*n])
print(twoCent) #ab hier nur Kontrollausgaben
print(n)
print(k)
print(Betrag)
print(Münzen);

Das ist mein Code bisher.

Wenn ich jetzt eine '9' eingebe erhalte ich:['1Cent', '2Cent, 2Cent, 2Cent, 2Cent']. Bei '99' erhalte ich das ganze 2 mal. bei '999' Drei mal. Bei einer '0' Erhalte ich eine beabsichtigte Fehlermeldung.

Soweit so gut.

Ich denke mir jetzt, dass der Algorithmus soweit erst mal seinen Zweck tut, ich jedoch die Werte anders speichern sollte. Und das ich anderer Seits die Liste [(...), '2Cent, 2Cent, 2Cent, 2Cent'] in dieser Form ---> ['2Cent', '2Cent', (...)] haben sollte, damit ich die einzelnen, gleichen Elemente auch zählen kann.

Sollte ich nochmal eine while Schleife oder If Bedingung ans Ende packen die dann sagt:" Solange i <= 2 nenne es Cent, else nenne es Euro"? Und wie kann ich die Liste in die gewünschte Form bringen? Kann ich die irgendwie an einem bestimmten Zeichen trennen wie einen String? Also sag, trenne alle Elemente nach 't' oder sollte ich da auch mit Indizes arbeiten? Also, die Anzahl der jeweiligen Münzen zählen und dann von [i1::i2] entnehmen.

Ich habe auch gelesen, dass man Listen nicht großartig manipulieren soll, wenn man eine Schleife über diese laufen lässt. Mit List.remove() funktioniert die Schleife zum Beispiel nicht, aber mit del Liste[i] schon. Sollte ich das trotzdem lassen?

  del Betrag[0]
    #twoCent.extend(['2Cent'*n]);
    #twoCent.split('t')
    if i <=1:
        Münzen.extend(['1Cent'*k, '2Cent, '*n])
    elif 2 <= i < len(Check):
        Münzen.extend(['1Euro'*k, '2Euro, '*n])
    i +=1;

So in der Art. Das oben stehende macht aber folgendes: Die ersten beiden Stellen als Cent ausgeben, also alles wie gehabt, dann 4 Stellen lang nichts und gibt dann die Werte als Euro aus... Warum macht es 4 Runden lang nichts?

BITTE keine explizite Lösung posten, nur Hinweise geben.

DANKESCHÖN!

PS: Witzig wird es auch, wenn ich '10' eingeben.

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
4 Antworten
0

Nur erstmal vorweg. Bedenke, dass du auch eine u gerade zahlt haben kannst ohne ein 1Cent stück z.B 5cent =1x 5 cent stück

Diese Antwort melden
geantwortet

Punkte: 75

 

Danke für deine Antwort. Bei der 5 hab ich mir gedacht das ich entweder: (2Cent, 2Cent, 1Cent) ausgeben lasse, das geht bisher. Oder, dass ich es so in der Art wie: Wenn Liste 2Cent 2Cent 1 Cent enthält, lösche Inhalt und packe 5 Cent rein. Oder, lasse Liste wie sie ist und packe 'oder 5Cent rein'. Aber ich glaub das kann ich erst mal später machen, sobald ich die Sachen so bekomme, wie ich sie gern hätte.

Die Fehlermeldung bei Eingabe 'Null' hab ich auch schon, anders als oben, vor die Schleife gepackt.

  ─   anonym259a1 09.04.2020 um 01:02

Kommentar schreiben

0

Alsovorerst ich bin kein Python Experte. Aberspontan würde ich sagen: Lies den Betrag ein Nimm den größten verfügbaren wert bei den Münzen 2 Euro also 200 und bei scheinen (für Fortgeschrittene) 50000 Teste ob der eingegebene wert größer als dein größter verfügbarer wert ist Speichere den Eingabewert Bearbeite nun nur noch die Kopie des Inputs, so hast du ihn für Ausgaben oder Berechnungen noch zur Verfügung. Man könnte die neue variable passend als Rest benennen. Ziehe es so oft ab, wie möglich Für jedes abziehen, hänge den wert an die Liste an. Geht der eine wert nicht mehr nimm den nächst kleineren. Du könntest wahrscheinlich die Werte der Reihe nach in ein Array schreiben und nach unten durch integrieren. Also [200,100,50,20,10,5,2,1] Wenn Rest ==0 bist du fertig

Mit den geldscheinen geht das dann genauso nur dass die Oma dann ein größeres Array an verfügbaren Werten hat also [50000,20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1]

Für die Aufgabe mit der Anzahl machst du eine zusätzliche Schleife beim abziehen eines wertes und setztdan den zähler mit "i x 'wert des scheines / der münze"

Wenn das Programm dann geschrieben ist und meine Idee funktioniert, kann der pap ja einfach aus dem Programm abgeschrieben werden.

Für weitere Fragen stehe ich gerne zur Verfügung. Lese mich auch wenn notwendig in Python ein.

LG

Diese Antwort melden
geantwortet

Punkte: 75

 

Ich verstehe deine Lösung heute Abend leider nicht mehr...

Ich werde es mir nach 'ner Mütze voll Schlaf nochmal durchlesen.

Vielen, vielen Dank erst mal!

  ─   anonym259a1 09.04.2020 um 01:39

Kommentar schreiben

0

Naja aber es ist mit Verlaub nicht besonders gut durchdacht, wenn nur 1cent und 2cent benutzt werden. Würdest du ein Programm kaufen als Senior / Seniorin das nur 2euro 2cent und 1cent Münzen ausgibt?

Gucke morgen nochmal bzw heute tagsüber

Diese Antwort melden
geantwortet

Punkte: 75

 

Ich würde es schon nicht kaufen, weil man Cents als Tausender eingeben soll. :D

Danke.

  ─   anonym259a1 09.04.2020 um 01:31

Das ist wohl richtig
Kommst du damit klar?

Mir ist eingefallen: du kannst auch ein Array mit den zugehörige wertTexten machen also
Im array1 Index 0 50000 und in Array 2 Index 0 500 Euro so kann der zähler i dafür gleich mitverwendet werden.
Kann auch sein, dass es bei Python wie bei manch anderen Sprachen auch eine art Zuordnungsliste gibt. Meist Hash oder dictionary genannt dann kann man einem wert der dann als Index funktioniert einen anderen (auch von anderen datentypen) zuweisen. Man baut also Schlüssel-wert-Paare oder key-value-pairs

Würde es dir helfen, falls du noch weiterhin Probleme hast die Lösung in einer anderen Sprache zu sehen oder als pseudocode?

  ─   idefix 10.04.2020 um 00:36

Nö. War bisher alles nicht das, was ich gesucht habe, aber ich werd schon klar kommen -bzw, bin ich schon. Ich wollte es ja mit Listen machen, ohne Listen fällt es mir sehr leicht. Dictionaries gibt es auch, ja, aber ich möchte es nur mit Listen machen. Auch wenn es vielleicht umständlich erscheint, aber ich will das Programm nicht nur einfach irgendwie realisieren, sondern eben mit Listen.

Danke trotzdem. Ich versuchs in Zukunft lieber wieder auf reddit und co.

  ─   anonym259a1 11.04.2020 um 13:20

Kommentar schreiben

0

Ist keine Antwort, weil du nichts explizites wolltest aber nur mal so, falls du was hast z.b Visual Studio Community zum C# lesen und ausführen enter image description here

enter image description here

Diese Antwort melden
geantwortet

Punkte: 75

 

Kommentar schreiben