Rückgabe von Wechselgeld nach einem Kauf

fr33g

Dobi schrieb:

krümelkacker schrieb:
Darf ich auch meckern?

Ich finde direct initialization da, wo copy initialization gereicht hätte, hässlich. Mir läuft da immer ein Schauer über den Rücken, wenn ich so etwas lese.
int i( 14 ); // direct initialization
int j = 15;  // copy initialization
Lasst Euch von den Namen doch nicht durcheinander bringen. DI ist jetzt nicht "schneller", weil's "direct" ist. Da kommt bei (wahrscheinlich) allen Compiler eh der gleiche Code bei raus.
Klar darfste meckern.
Dass bei Zuweisung an einer Deklaration nicht der Zuweisungsoperator benutzt wird, weiß ich. Ich find "int i( 14 );" aber irgendwie intuitiver als "int i = 14;", weil man dann diesen "Tweak" in der Sprache gar nicht bedenken muss.

Ob da der Zuweisungsoperator genutzt wird oder nicht, ist hier gar nicht die Frage, das sollte ja wohl klar sein, da es eine Initialisierung ist und keine Zuweisung. Es ging um Direct-Initialization oder Copy-Initialization

Lg freeG

pumuckl

fr33g schrieb:

Ob da der Zuweisungsoperator genutzt wird oder nicht, ist hier gar nicht die Frage, das sollte ja wohl klar sein, da es eine Initialisierung ist und keine Zuweisung. Es ging um Direct-Initialization oder Copy-Initialization

Weiß er ja, hat er ja auch geschrieben dass er das weiß.
Ob so oder so ist Jacke wie Hose. Es macht das selbe, und ob es jetzt ein "tweak" in der Sprache ist oder nicht, ist auch wurscht, weils beides gängige Praxis ist. Man sollte beides lesen können ohne drüber zu stolpern. Es ist eine reine Geschmacksfrage, welche Form man vorzieht.

fr33g

pumuckl schrieb:

fr33g schrieb:

Ob da der Zuweisungsoperator genutzt wird oder nicht, ist hier gar nicht die Frage, das sollte ja wohl klar sein, da es eine Initialisierung ist und keine Zuweisung. Es ging um Direct-Initialization oder Copy-Initialization

Weiß er ja, hat er ja auch geschrieben dass er das weiß.
Ob so oder so ist Jacke wie Hose. Es macht das selbe, und ob es jetzt ein "tweak" in der Sprache ist oder nicht, ist auch wurscht, weils beides gängige Praxis ist. Man sollte beides lesen können ohne drüber zu stolpern. Es ist eine reine Geschmacksfrage, welche Form man vorzieht.

Ich weiß ja dass er das weiß. Aber krümelkacker meinte ja den Unterschied zwischen Copy-Initialization und Direct-Initialization, den es oft gar nicht gibt. Und ich habe es dann so verstanden, als wie Dobi das gar nicht gemerkt hat, sondern dachte, Krümelkacker meinte das mit dem Zuweisungsoperator. Aber darum ging es ja Krümelkacker nicht.
Aber is ja jetzt auch Wurscht

Lg freeG

krümelkacker

Nee, ist ne reine Geschmacksfrage (in den meisten Fällen). Meine Präferenz habe ich kund getan (CI). Für mich sieht DI zu sehr nach einer Funktionsdeklaration aus. In C schreibt das ja auch keiner so auf.

Ich wollte nur nicht, dass einer denkt, dass DI irgendwie effizienter sei als CI und es nur deswegen verwendet.

life

Dobi schrieb:

Geht sicher auch wesentlich eleganter und wiederverwendbarer, aber damit du siehst, wie ich es meine, reichts, denk ich.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ...
	for ( vector <int>::const_iterator it( geldEinheiten.begin() ); it != geldEinheiten.end(); ++it )
	{
		int anzahl( 0 );
		while ( *it <= wechselgeld )
		{
			++anzahl;
			wechselgeld -= *it;
		}
		cout << anzahl << " Gegenstaende, die einen Wert von " << *it << " Cent repräsentieren." << endl;
	}
	return 0;
}

Fehlt nur noch der Korrektheitsbeweis. Wenn man z.B. auch 4€ Münzen hätte, wäre deine Strategie ja fehlerhaft (z.B. 8€ mittels 5€+2€+1€ zu wechseln wäre dann nicht optimal, sondern 4€+4€). Warum klappt die Strategie also in diesem Fall?

Dobi

life schrieb:

Warum klappt die Strategie also in diesem Fall?

Weil die nächstgrößere Einheit bei unserer Währung immer mindestens doppelt so groß ist wie die kleinere.
Hab ich deinen Test bestanden?

volkard

Dobi schrieb:

life schrieb:

Warum klappt die Strategie also in diesem Fall?

Weil die nächstgrößere Einheit bei unserer Währung immer mindestens doppelt so groß ist wie die kleinere.
Hab ich deinen Test bestanden?

Gegenbeispiel:
Die 1-Cent-Münze wurde abgeschafft.
Will 8 Cent rausgeben.
Gebe zuerst 5 und verzweifle.

Dobi

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?
Was machen wir eigentlich, wenn wir beliebige Geldeinheiten haben, von allen aber nicht beliebig viel. Dann kanns ja sein, dass das Ziel ist, dem Kunden möglichst viel Wechselgeld zurückzugeben aber nicht mehr als nötig. Hilft es dann, wenn wir uns vorstellen, dass der Kunde das Welchselgeld nicht in ein Portemonnaie tut, sondern in einen Rücksack?

life

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

Dobi

life schrieb:

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

90+1+1+1+1+1+1+1+1+1+1 ist zwar unschön, aber nicht zum Verzweifeln.

life

Dobi schrieb:

life schrieb:

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

90+1+1+1+1+1+1+1+1+1+1 ist zwar unschön, aber nicht zum Verzweifeln.

Jedenfalls nicht optimal.

Dobi

Ich hab doch schon eingesehen, dass man das so aufblähen kann, dass es ne O(c^n)-Rucksack-Geschichte wird. Und nein, DAS werde ich nicht beweisen.

life

Im Allgemeinen ist das Problem NP-Vollständig. In dem konkreten Fall funktioniert die Greedy-Strategie allerdings tatsächlich. Und genau letzteres sollst du beweisen ;).

Dobi

Heute ist Informatik für mich dann halt Natur- und nicht Strukturwissenschaft. Also darfst du versuchen, meine Theorie zu falsifizieren. Die Möglichkeit dazu bietet sie ja, so.
OK, ich denk mal (googleunterstützt) nach. Jetzt interessierts mich.

Ich denke, wenn man die Optimas von allen Geldbeträgen betrachtet, wird es irgendwann eine Regelmässigkeit geben, so dass Opt(n) = g + Opt(n - g) aller n>c, wobei g=grösster Münzwert.

Die Tabelle bis dahin lässt sich in konstanter Zeit generieren und auch der Rest ist eine simple Rechnung. Folglich wäre das Problem in O(1) lösbar, von NP-complete keine Spur. Das wäre im Übrigen auch eine Vorgehensweise, mit der sich die Greedy-Strategie noch optimieren liesse: n = n mod g. Auch dann ist die Laufzeitkomplexität O(1).

Den Beweis überlasse ich dir

[quote="wikisid"so dass Opt(n) = g + Opt(n - g) aller n>c, wobei g=grösster Münzwert.[/quote]Ups, soll heissen g ist ein Vielfaches des grössten Münzwertes, es muss nicht genau ihm entsprechen (siehe Beispiel mit Münzsatz (90, 24, 1)).

life

Beim verallgemeinerten NP-vollständigen Problem sind die Münzbeträge, die einem zum Wechseln zur Verfügung stehen, auch eine Eingabe des Algorithmus.

Der Algo geht auch mit Eingabe der Münzbeträge. Und die Periode tritt IMHO nach kgV(m₁, m₂, m₃, ..., m_n) Einheiten auf, also läuft er in O(n·m_n).

NP-Complete wird er IMHO, wenn nur eine begrenzte Anzahl Münzen zur Verfügung steht.

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;
}