Dollarnoten Algorithmus

miztrinkler

Ich habe ein Problem, und zwar soll ich einen Algorithmus schreiben (Struktogramm und C-Programm), der mir ausrechnet, auf wie viele verschiedene Varianten man 100$ bezahlen kann. Man darf nur Noten benützen, also 100 $, 50$ , 20 $, 10$ , 5 $, 2$ und 1$-Noten. Hat jemand eine Idee? Ich habe keinen Schimmer, wie ich das am Besten anstelle

Danke für jede Hilfe.

Gruss Michal

stichwort: rekursion

Krösus

Schnellschuß:

static int s_iAnzMgktn = 0;

static void Zerlege(int);

void main(void) //Illegal, ist mir aber wurscht!
{
	Zerlege(100);
	printf("Anzahl aller Möglichkeiten mit Beachtung der Reihenfolge = %d\n", s_iAnzMgktn);
	printf("Anzahl aller Möglichkeiten ohne Beachtung der Reihenfolge = ???\n");
}

void Zerlege(int dollars)
{
	if(dollars < 0)
		return;
	if(dollars == 0) //if(!dollars) tut's auch, aber so wird klarer, was gemeint ist
	{
		++s_iAnzMgktn;
		return;
	}
	Zerlege(dollars - 100);
	Zerlege(dollars - 50);
	Zerlege(dollars - 20);
	Zerlege(dollars - 10);
	Zerlege(dollars - 5);
	Zerlege(dollars - 2);
	Zerlege(dollars - 1);
}

Ohne Beachtung der Reihenfolge (wahrscheinlich die Intention der Aufgabe) wird's wohl deutlich komplexer!

Krösus

Nicht viel komplizierter, folgendes dürfte es tun (immer zuerst die großen Scheine wegnehmen):

static int s_iAnzMgktn = 0;

static void Zerlege(int, int);

void main(void) //Illegal, ist mir aber wurscht!
{
	Zerlege(100, 100);
	printf("Anzahl aller Möglichkeiten ohne Beachtung der Reihenfolge = %d\n", s_iAnzMgktn);
}

void Zerlege(int dollars, int min)
{
	if(dollars < 0)
		return;
	if(!dollars)
	{
		++s_iAnzMgktn;
		return;
	}
	if(min >= 100) Zerlege(dollars - 100, 100);
	if(min >= 50)  Zerlege(dollars - 50,  50);
	if(min >= 20)  Zerlege(dollars - 20,  20);
	if(min >= 10)  Zerlege(dollars - 10,  10);
	if(min >= 5)   Zerlege(dollars - 5,   5);
	if(min >= 2)   Zerlege(dollars - 2,   2);
	if(min >= 1)   Zerlege(dollars - 1,   1);
}

Bashar

Krösus schrieb:

void main(void) //Illegal, ist mir aber wurscht!

Warum schreibst du Held nicht einfach int? gcc-User werden es dir danken

Mis2com

Irgendwie kapier ich den Algorithmus nicht...

Wie kommt man darauf?

Hm, man gibt eine Zahl an und jetzt zerlegt er das in verschiedene Möglichkeiten, hm, aber dadurch macht er doch bei jedem Aufruf s_iAnzMgktn + 1, wenn es nicht <= 0 ist...
Ich kapiers nicht, kann das mal einer erklären?

PS: Derjenige der den Thread eröffnet hat, hatte keine Ahnung, ich denke da ist eine Erklärung sowieso besser.

lustig

Du musst den Betrag so in die Geldscheine unterteilen, dass du am Schluss genau 0 Dollars hast. Falls du noch mehr als 0$ hast, musst du noch mehr wegnehmen. Falls weniger musst du wieder zurück aus der Funktion, denn dann hast du zuviel weggenommen. Deshalb sind die Beträge beim Aufrufen der grösse nach geordnet. Falls du genau 0$ hast, hast du eine Lösung gefunden. Also Zähler der gefundenen Lösungen erhöhen und zurückkehren. Ich hoffe das war jetzt halbwegs verständlich.