[C] Münzwechsler mit rekursiver Funktion

[AlexK84]

Hallo Leute!

Ich stell mich erst mal vor: Ich bin Alex und studiere an der Universität Hannover Elektrotechnik, und muss zur Zeit eine Einführung in C/C++ machen.

Dabei steh ich im Moment echt vor einem für mich scheinbar unlösbarem Problem. Ich muss bis Mittwoch einen Münzwechsler programmieren, der mir sämtliche möglichen Wechselkombinationen ausgibt. Eine genaue Beschreibung der Aufgabe und die vorgegebene Lösungsstruktur gibt es hier (Aufgabenteil b):

http://www.rts.uni-hannover.de/studium/programm/GDI_Aufgabenblatt9.pdf

Ich hab einfach keine Idee, wie ich die Funktion "kombinationen" realisieren soll, wahrscheinlich bin ich im Kopf einfach mittlerweile absolut festgefahren.

Ich soll ja immer bei der größten Münzart (hier 50 Cent) anfangen, und dann alle Möglichkeiten , mit dierser Münze zu wechslen erst einmal berechnen lassen. Bei 124 Cent wären das ja zum Beispiel:

2*50 Cent
1*50 Cent
0*50 Cent

dann soll die Funktion ja wohl rekursiv weitermachen mit der nächstkleineren Münzart, aber wie bekomm ich da die Zuordnung im Feld genutzt[] hin?

Ach ja: Ich hab meinen bisher zustande gabrachten Quelltext mal angehängt.

Ich bin dankbar für jeden Denkanstoß,
Alex

 

[Limit]

Re: Münzwechsler mit rekursiver Funktion in C

void kombinationen(int mg, int betrag) {

	genutzt[mg]=betrag%wert[mg];

	if(mg<mg_min) printf("%d %d %d %d %d %d",&genutzt[0], &genutzt[1], &genutzt[2], &genutzt[3], &genutzt[4], &genutzt[5]);
	else kombinationen(mg-1,betrag-genutzt[mg]*wert[mg]);
}

so ungefähr könnte das vlt aussehen.

kA, ob es syntaktisch funktioniert, ich habe nur sehr wenig Erfahrung mit C, aber es sollte zumindest als Denkanstoss zu gebrauchen sein.

 

[AlexK84]

Re: Münzwechsler mit rekursiver Funktion in C

Mit dieser Lösung bekomme ich aber nur genau eine Kombinationmöglichkeit, oder? Ich soll aber alle Möglichen ausgeben, für 123 cent also z.b.

2*50, 1*20, 3*1
oder
2*50, 2*10, 3*1
usw.

Trotzdem, Danke für die Mühe.

 

[Chris_82_CH]

Re: Münzwechsler mit rekursiver Funktion in C

Puhhh, das war mühsam, aber ich habs doch geschaft ;-) :

void kombinationen(int mg, int betrag){
	if(betrag == 0){
		ausgeben();
	}else{
		int i;
		for (i=mg; i>= 0; i--){
			if(betrag >= wert[i]){
				genutzt[i]++;
				kombinationen(i,betrag - wert[i]);
				genutzt[i]--;
			}
		}
		
	
	}

}

sollte eigentlich funktionieren, d.h. ich habs nur mit Zahlen <10 getestet. Das wurde mir dann zu zeitraubend

Gruss

Chris

 

[Wizard of OS]

Re: Münzwechsler mit rekursiver Funktion in C

google mal nach backtracking!!

die lösung ist nich so trivial wie du denkst.

ich kann die mustercodes in java geben, sind fast 1:1 in C++.

 

[AlexK84]

@Chris_82_CH:

Deine Lösung funktioniert! Ich weiß gar nicht, wie ich dir danken soll. Hast mir und einigen Komilitonen echt aus der Patsche geholfen. Danke!

Alex