Programmieraufgabe "Münzenproblem"

[icarus2]

@Belli
Ja, diese Implementierung scheint korrekt zu sein. Allerdings ist sie sehr ineffizient, wegen den vielen Rekursionsaufrufen. Wie gesagt kann hier Memoization oder Dynamische Programmierung verwendet werden.

Ich moechte die Loesung dafuer hier allerdings nicht posten, da ich dem Thread Ersteller nicht den Spass nehmen will.

[Belli]

Tja, diese Begriffe, die Du da in den Raum wirfst, sagen mir nichts. Deshalb bin ich nicht in der Lage, eine andere Lösung zu entwerfen. Ich hab hier mal ein vollständiges Beispiel, das am Ende die benötigten Stücke ausgibt, wenn es denn eine Lösung gibt:

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

vector<int> m;
vector<int> r;

bool erreichbar(int b)
{
	if(b == 0)
		return true;
	if(b < 0)
		return false;

	for(int i = 0; i < m.size(); ++i)
	{
		if(erreichbar(b - m[i]))
		{
			r.push_back(m[i]);
			return true;
		}
	}

	return false;
}

int main(int argc, char **argv)
{
	stringstream ss;
	ss << argv[1];
	int b;
	ss >> b;

	m.push_back(3);
	m.push_back(5);

	erreichbar(b);	

	if(!r.size())
		cout << "geht nicht\n";

	for(int i = 0; i < r.size(); ++i)
		cout << r[i] << ' ';

}

[icarus2]

Belli schrieb:

Tja, diese Begriffe, die Du da in den Raum wirfst, sagen mir nichts.

Falls du dich fuer algorithmische Methoden interessierst soltest du dir einmal Dynamische Programmierung anschauen. Ist eine interessante Methode um schwierige Probleme effizient (in Pseudopolynomieller Zeit) zu loesen.

[ands]

Habe mir mal das Konzept der Memoization angeschaut, bin mir aber nicht sicher, ob ich das richtig verstehe...
Das Ziel der Memoization besteht ja darin, dass Zwischenergebnisse nicht mehrmals neu berechnet werden, sondern gespeichert und wiederverwendet werden. Habt ihr einen Tipp, wie man das auf das Münzenbeispiel anwendet?
Meine Idee:
Einen Vektor "vector<int> memory" welcher alle Zwischenbeträge die berechnet werden speichert. Das heisst ein neuer Zwischenwert soll nur berechnet werden, wenn er nicht schon im Vektor steht. Ich habe nun aber zwei Fragen/Probleme...an welchen Positionen muss ich diese Zwischenbeträge jeweils speichern bzw. wie muss ich sie speichern damit ich einfach prüfen kann, ob ein Betrag bereits vorhanden ist oder nicht? Und zweitens ist mir nicht ganz klar, wie ich die Schritte einbauen kann für Betrag == 0 oder Betrag <0?

[icarus2]

Eine rekursive Loesung hat ja Belli oben bereits gepostet. In der Loesung dort gibt es einen einzigen rekursiven Aufruf in Zeile 20, naemlich

erreichbar(b - m[i])

Das Ziel ist es nun, diesen Aufruf nicht jedes mal neu berechnen zu muessen. Das heisst du erzeugst ein Array einer bestimmten Laenge, um berechntete Teile der Rekursion zu speichern. Wenn du dann zum rekrusiven Aufruf kommst, hast du folgende zwei Moeglichkeiten:
1. Du hast erreichbar(b - m[i]) bereits berechnet. Dann verwende den Wert aus dem Array und rufe erreichbar(b - m[i]) nicht rekursiv auf.
2. Du hast erreichbar(b - m[i]) noch nicht berechnet. Dann rufe erreichbar(b - m[i] rekursiv auf und speichere dann die Loesung im Array.

Um herauszufinden, ob du erreichbar(b - m[i]) bereits berechnet hast oder nicht kannst du ein zweites Array der gleichen Groesse anlegen und dann mit true oder false speichern, ob du den Wert bereits berechnet hast.

Was du dich noch fragen musst ist, wie gross du das Array waehlen musst. Aber das kannst du sicher selber rausfinden.

Ich hoffe, die Beschreibung hilft dir etwas.

[Die erinnerung]

Da würde ich eher einen Vector nehmen.

[icarus2]

Die erinnerung schrieb:

Da würde ich eher einen Vector nehmen.

Wenn man Array sagt duerfte klar sein, dass man dann in C++ einen std::vector oder ein std::array verwendet

[Die erinnerung]

Soooooooooooooo sicher wäre ich mir da nicht...
(Ich hätte, hätte ich nicht nachgedacht, z.B bool benutzt[123]; gemacht. Zum Beispiel...)

[Belli]

Deswegen ist Nachdenken ja auch so wichtig. Ich würde auf den ersten Blick eine map wählen.

[ands]

Habe es mit Vektoren gemacht... mit den Tipps von icarus2 (danke!) ist's dann ziemlich einfach und klappt gut