Schwerer Algo

Linuxxx

Hallo ich hab einen problem kann mir den jemand weiterhelfen ich brauch diese aufgabe in c mir fällt aber nicht ein wie ich das machen könnte

Aufgabe

Lesen Sie über Tastatureingabe einen ganzzahligen Geldbetrag ein. Ermitteln Sie zu diesem Betrag alle Möglichkeiten, wie er in Scheinen oder Münzen ausbezahlt werden kann, von denen es die Werte 500, 200, 100, 50, 20, 10, 5 und 1 gibt. Das Programm endet bei leerer Eingabe.

Sicher das es wirklich alle sein sollen? Das würden sehr schnell, sehr viele werden.

Linuxxx

ja ganz sicher leider ;))) ich hab mein prof gefragt also irgendwie komm ich nicht drauf bekomm es nicht hin

cin

Was hast du probiert, was funktioniert nicht?
Falls es am Algorithmus liegt: Rechner ausschalten, Blatt Papier nehmen, für kleine Geldbeträge alle Möglichkeiten ausprobieren, Zusammenhänge entdecken, Algorithmus in Code umwandeln.

btw.: Wie sollen die denn ausgegeben werden? Und vor allem: Wer darf das Probelesen? *g*

Xul

Das schreit nach Rekursion! Würd das Ganze vom Prinzip her so machen:

void Funktion(int Wert)
{
    if(Wert>0)
    {
        Funktion(Wert-500);
        Funktion(Wert-200);
        Funktion(Wert-100);
        Funktion(Wert-50);
        Funktion(Wert-20);
        Funktion(Wert-10);
        Funktion(Wert-5);
        Funktion(Wert-1);
     }
}

Probleme: Es werden Lösungen doppelt auftreten, die Ausgabe ist auch noch nicht realisiert und der Stack kann ganz schnell mal überlaufen. Soll ja erstmal n Denkanstoß sein.

Linuxxx

danke werde mal so ran gehen mal schauen ob es was wird

Andorxor

1)Ich würde erst einmal die einzelen Werte in die grösst möglichen Werte zerlegen
1 - []
5 - [1,1,1,1,1]
10 - [5,5]
20 - [10,10]

Dann würde ich den Zielwert in die grösst möglichen Werte zerlegen

26 -[20,5,1]

Dann würde ich das erste Vorkommen des grössten Wertes in diesen Ergebnis in den Wert aus 1 ersetzen
[10,10,5,1]
Dann würde ich Schritt 3 mit den kleineren Werten ausführen,und am Ende mit dem grössten Werten vereinen
[20,5,1]=>[20]+[5,1]=[20]+[1,1,1,1,1,1]

5)Dann führe ich den 3,4,5 mit den Ergebnissen von 3 und 4 nochmal aus,bis ich ein Ergebnis erhalten das sich nicht weiter zerlegen lässt

[10,5,5,5,1]
[10,10] +[1,1,1,1,1,1]

[5,5,5,5,5,1]
[10] +[5,5,1,1,1,1,1,1]

[5,5,5,5,1,1,1,1,1,1]
[10] +[5] +[1,1,1,1,1,1,1,1,1,1,1]

[5,5,5,1,1,1,1,1,1,1,1,1,1,1]

[5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

[5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

hardy

void Funktion(int Wert) 
{ 
    if(Wert>0) 
    { 
        Funktion(Wert-500); 
        Funktion(Wert-200); 
        Funktion(Wert-100); 
        Funktion(Wert-50); 
        Funktion(Wert-20); 
        Funktion(Wert-10); 
        Funktion(Wert-5); 
        Funktion(Wert-1); 
     } 
}

also wenn man hier einfach als weiteren parameter den zuletzt abgezogenen betrag noch dazunimmt und die funktion dann sicherstellt, dass im weiteren verlauf kein höherer betrag mehr abgezogen wird sollte es schon fast fertig sein.
was hier noch fehlt ist die korrekte abbruchbedingung, es sei denn meine geldautomaten sollen mir auf 1 eur einen 500 euroschein rausgeben dürfen

C++ Forumbot

Dieser Thread wurde von Moderator/in AndreasW aus dem Forum C# und .NET in das Forum ANSI C verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

c.rackwitz

edit: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_idx_728

Daniel E.

c.rackwitz schrieb:

file:///F:/My%20Websites/SICP/mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_idx_728

Clever

c.rackwitz

Daniel E. schrieb:

c.rackwitz schrieb:

file:///F:/My%20Websites/SICP/mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_idx_728

Clever

tja, google desktop search + >>"schwerer" algo<<
habs korrigiert