Rückgabe von Wechselgeld nach einem Kauf

[wikisid]

Hmm, ich sollte meine Beiträge genauer lesen... m_nⁿ ist natürlich exponentiell.

[Clonex]

Ich möchte mich vielmals für die Hilfe hier bedanken.

Hier mal meine Lösung. Ich weiß wenn Ihr Profis das jetzt seht wird euch bestimmt schlecht aber wie gesagt ich lerne noch....

#include <iostream>
using namespace std;

int main() {

	int kaufbetrag, gezahlt;
	cout << "Bitte geben Sie den den Kaufbetrag in Cent ein: " << endl;
	cin >> kaufbetrag;
	cout << "Bitte geben Sie den Gezahlten Betrag in Cent ein: " << endl;
	cin >> gezahlt;

	int wechselgeld = gezahlt - kaufbetrag;
	if (kaufbetrag==gezahlt) {
		cout << " Passend bezahlt!" << endl;
	}
	if (kaufbetrag>gezahlt) {
		cout << "Zu wenig bezahlt, restart!" << endl;
	}
	int change [] = { 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50,
			20, 10, 5, 2, 1 };
	int j=0;
	int calc;

	while (j<=14) {
		calc= wechselgeld/change[j];
		if (calc>0) {
			cout << "Sie bekommen " << calc <<" mal " << change[j]
					<< " cent zurück!" << endl;
			wechselgeld=wechselgeld-calc*change[j];
		}
		j++;
	}
	return 0;
}

[Skym0sh0]

nein sieht doch ganz gut aus am anfang...

[volkard]

Die while-Schleife wäre lieber eine for-Schleife.
Die Variable calc wäre lieber noch lokaler.
Sonst perfekt, würde ich sagen.

[mrperfekt]

wechselgeld noch lokaler
"Bitte geben Sie den Gezahlten Betrag in Cent ein: " ← "gezahlten" klein, ev. Punkt anstatt Doppelpunkt
else if bei zweitem if
14 nicht hardcoden sondern als const int change_size = sizeof(change)/sizeof(*change); definieren
zeile 29: operator -= nehmen

Versteh das nicht falsch; deines ist wirklich nahezu perfekt, gerade für einen Anfänger. Aber bevor Mods so etwas als perfekt deklarieren dürfen, muss man es doch noch etwas perfektionieren.

[cvcv]

mrperfekt schrieb:

wechselgeld noch lokaler
"Bitte geben Sie den Gezahlten Betrag in Cent ein: " ← "gezahlten" klein, ev. Punkt anstatt Doppelpunkt
else if bei zweitem if
14 nicht hardcoden sondern als const int change_size = sizeof(change)/sizeof(*change); definieren
zeile 29: operator -= nehmen

Versteh das nicht falsch; deines ist wirklich nahezu perfekt, gerade für einen Anfänger. Aber bevor Mods so etwas als perfekt deklarieren dürfen, muss man es doch noch etwas perfektionieren.

Der Text ist nun ja mal ziemlich wayne.
Er braucht kein else if bei dem 2. if. Die Bedingungen schliessen sich gegenseitig aus. Wenn der Betrag == ist, dann procct die 1. if-verzweigung, wenn der Betrag > ist dann procct die 2.
Wie sollt er den operator -= nehmen ? Das ist ja wohl Geschmackssache, seine Variante sogar irgendwie lesbarer.
Was ich für mehr erwähnenswert halten würde ist :

if (kaufbetrag>gezahlt) {
        cout << "Zu wenig bezahlt, restart!" << endl;
    }

Du behauptest zwar etwas von einem restart, dieser geschieht aber nie. Dein Programm würde in dem Fall einfach weiterlaufen und zu irgendeinem Crap-Ergebnis führen. Pack die Eingaben in eine while-schleife die erst endet, wenn alles richtig eingegeben wurde.
Und : Mach die Überprüfungen doch bevor du Wechselgeld berechnest.

[Dobi]

Habs nicht hinbekommen, zu beweisen, dass greedy in unserem monetären System zum Optimum führt.
Im Netz gefunden habe ich auch nichts.
( Geldeinheit[n] >= 2 * Geldeinheit[n+1] ) zusammen damit, dass das die 1 auch dabei ist, scheint zwar hinreichend zu sein, aber nicht notwendig. Die Fibonacci-Folge erfüllt das ja nicht, trotzdem habe ich da auch keinen Fall gefunden, wo es nicht klappt.
Lässt sich das denn überhaupt beweisen? Und wenn ja wie? life?

[life]

Dobi schrieb:

( Geldeinheit[n] >= 2 * Geldeinheit[n+1] ) zusammen damit, dass das die 1 auch dabei ist, scheint zwar hinreichend zu sein, aber nicht notwendig.

Nein, das ist nicht hinreichend. Siehe mein Gegenbeispiel von Seite 4.

Lässt sich das denn überhaupt beweisen? Und wenn ja wie? life?

Klar lässt sich das beweisen. Du solltest nur nicht versuchen, das Problem zu verallgemeinern, sondern dir ganz konkret die gegebene Münzwerte (also im wesentlichen 1,2,5) anschauen.

[Dobi]

Ah, sorry. Dein Gegenbeispiel hatte ich schon wieder vergessen.

Ok, also für 1, 2 und 5 kann mans natürlich beweisen, indem mans für 1,2,3,4 und 5 einzeln zeigt (alle Zusammensetzungsmöglichkeiten durchgehen, Greedy-Ergebnis danebenhalten, sehen, dass es das Optimum trifft) und dann sagt, dass alles ab 6 aufwärts immer n5 + etwas schon bewiesenes ist.
Für unser System wärs dann halt alles bis 500. Vermutlich kann man das dann auch wieder aufteilen, weil sich das 1,2,5-Muster immer wieder wiederholt.
Aber auch dann könnt ich nur wieder "Ist halt so." sagen. Und ich befürchte, dass das nicht reicht.
Der Schritt "Für 1 bis 5 hab ichs einzeln gezeigt." ist also einfach.
Aber wie beweise ich, dass n5 + etwas schon bewiesenes auch wieder ein Optimum bringt?

[wikisid]

Dobi schrieb:

Aber wie beweise ich, dass n*5 + etwas schon bewiesenes auch wieder ein Optimum bringt?

Angenommen, greedy gelte für m=5. Sie muss auch für m+1 gelten, da keine bessere Nicht-Greedy-Zerlegung existiert. Denn diese müsste ...

• ... genau so viele 5er-Münzen besitzen wie die Greedy-Zerlegung, da ansonsten die Summe aller Nicht-5er-Münzen grösser wäre als 5 und kleiner gleich m und es für diese Summe eine bessere, mindestens aber gleich gute greedy Zerlegung gäbe.
• ... genau so viele 1er- und 2er-Münzen besitzen. Denn wenn sie maximal viele 5er-Münzen besitzt, ist ihre Summe kleiner 5, wo greedy das Maximum liefert.

So schwierig war das jetzt nicht

Über die notwendigen Voraussetzungen des Münzsets muss ich allerdings noch genauer nachdenken.

[volkard]

wikisid schrieb:

Dobi schrieb:

Aber wie beweise ich, dass n*5 + etwas schon bewiesenes auch wieder ein Optimum bringt?

Angenommen, greedy gelte für m=5. Sie muss auch für m+1 gelten, da keine bessere Nicht-Greedy-Zerlegung existiert. Denn diese müsste ...

• ... genau so viele 5er-Münzen besitzen wie die Greedy-Zerlegung, da ansonsten die Summe aller Nicht-5er-Münzen grösser wäre als 5 und kleiner gleich m und es für diese Summe eine bessere, mindestens aber gleich gute greedy Zerlegung gäbe.
• ... genau so viele 1er- und 2er-Münzen besitzen. Denn wenn sie maximal viele 5er-Münzen besitzt, ist ihre Summe kleiner 5, wo greedy das Maximum liefert.

So schwierig war das jetzt nicht

Den Beweis kann ich kein Bißchen nachvollziehen.

[Life@work]

wikisid schrieb:

Dobi schrieb:

Aber wie beweise ich, dass n*5 + etwas schon bewiesenes auch wieder ein Optimum bringt?

Angenommen, greedy gelte für m=5. Sie muss auch für m+1 gelten, da keine bessere Nicht-Greedy-Zerlegung existiert. Denn diese müsste ...

• ... genau so viele 5er-Münzen besitzen wie die Greedy-Zerlegung, da ansonsten die Summe aller Nicht-5er-Münzen grösser wäre als 5 und kleiner gleich m und es für diese Summe eine bessere, mindestens aber gleich gute greedy Zerlegung gäbe.
• ...

Warum kleiner gleich m? Wenn die optimale auf 5er ganz verzichtet, wäre die Summe der Nicht-5er m+1.

[Dobi]

Zwei gerade promovierende Mathematiker haben auf eine Mail eines Kollegens zu dem Thema übrigens auch nicht geantwortet.

@life: Du hattest ja den Beweis gefordert. Klär mich doch mal bitte auf.