Java Rekursive Berechnung von Kopien

[Sophie87]

Hallo,
sitz hier gerade in der Uni um für Übungen die Aufgaben zu machen. Darunter ist eine eigentlich total einfache Aufgabe - und zwar die, einen Copy-Shop zu entwerfen, der abhängig von der verlangten Kopie-Anzahl verschiedene Vergünstigungen in den Preis mit einbezieht.

Der Nutzer soll also Angeben, wie viele Kopien er will und das Programm soll nach folgender Tabelle den Preis berechnen:

1 Kopie = 0.1 EUR
6 Kopien = 0.5 EUR
15 Kopien = 1 EUR

Das ganze ist iterativ und rekursiv zu lösen. Die iterative Lösung hat 3 Minuten gedauert und lief direkt fehlerfrei. Die rekursive Variante macht mir aber zu schaffen. Meinen (in meinen Augen) bisher besten Lösungsansatz seht ihr hier:

static double REK_kosten(int k) {
	if (k==15) {return 1;} else
	if (k==6) {return 0.5;} else
	if (k<=6 & k>0) {return 0.1;} else
	if (k==0) {return 0;}
	 else {
		if (k/15>1) {return k/15*REK_kosten(k-1);} else
		if (k/6>1) {return k/6*REK_kosten(k-1);} else
		return k*REK_kosten(k-1);
	  }
}

Hab jetzt bestimmt schon auf 10 verschiedene Weisen versucht dem Problem zu begegnen, aber immer ist die Ausgabe verkehrt (oder nur in den Sonderfällen 0, 1, 6, 15 richtig).

Bin hier langsam am verzweifeln. Hab Rekursion noch nie gemocht aber hier ists irgendwie aus. Verstehe nicht so ganz wie ich es so hinbekommen soll, dass der rekursiv die 3 (bzw. 4) Fälle berücksichtigt.

Kann mir jemand helfen?

 

[pappy]

nur ein tip: integerdivision so wie du sie in der rekursion nutzen willst funktioniert nicht da deine logik bei 16/15 >1 ziehen sollte aber da integerdivision ist es nur 1 und 1 != >1. (keine garantie kann selber nich programmieren )

 

[Sophie87]

Habe jetzt durch Typecasting the Divisionsgenauigkeit erhöht, hat aber auch nichts gebracht. :-/

Auch ein paar andere Anpassungen in der Zwischenzeit (besonders in Richtung Modulo-Operator) blieben erfolglos :-/

 

[Simpson474]

Wenn ich die Aufgabenstellung richtig verstanden habe, dann sollte das ganze in etwa so aussehen:

static double REK_kosten(int k) 
{
	double retval = 0.0;
	bool isFinished = false;

	if (k >= 15)
	{
		k -= 15;
		retval = 1.0;
	}
	else if(k >= 6)
	{
		k -= 6;
		retval = 0.5;
	}
	else if(k > 0)
	{
		k--;
		retval = 0.1;
	}
	else
	{
		isFinished = true;
	}

	if (!isFinished)
	{
		retval += REK_kosten(k);
	}

	return retval;
}

 

[Sophie87]

Zumindest stimmen die Ergebnisse mit denen des iterativen Alg. überein ;-)

Jetzt muss ich mir das mal genauer zu gemüte führen und gucken, warum mein Code so toll versagt hat ^^

 

[Simpson474]

Ich weiß nicht, was du mit deinen Gleichheitsvergleichen erreichen wolltest - der Sinn soll ja sein, so lange 15 oder mehr bzw. 6 oder mehr Kopien ausstehend sind, dass der günstigere Staffelpreis verwendet wird. Daher verwende ich so lange wie möglich die Staffelpreise und falle erst wenn weniger als 6 Kopien da sind in den Zweig für Einzelkopien. Wenn gar keine Kopie mehr gemacht werden soll, dann beende ich die Rekursion indem ich die Funktion kein weiteres Mal aufrufe.

 

[Sophie87]

Naja, das war halt die Funktion wie sie aus 10 verschiedenen Ansätzen entstanden ist; gut möglich dass da vieles nicht mehr gepasst hat. Meine Idee sah eigentlich genauso aus... nur hatte ich halt überprüft ob die Kopien 15 bzw. 6 überschreiten um sicherzustellen das ich um den richtigen Wert später inkrementiere. Aber dann hatte ich es von der Überprüfung >= auf == geändert wegen ner anderen Idee, und schwupps schon passts hier und da nicht mehr. So ist das halt.

Hab mir jetzt nach der Code-Vorlage den umgedrehten Fall (also wie viele Kopien für wie viel Geld) ebenfalls rekursiv zusammenbauen können, und da hats auch klack gemacht beim schreiben Danke nochmals.

 

[Cobinja]

Das hier mag ein einfaches Rekursions-Beispiel sein, aber oft ist es sinnvoll, mal zu gucken, ob man die Rekursionstiefe optimieren kann, sprich ob man das gleiche Ergebnis mit weniger Rekursionen hinbekommt:

public static double REK_kosten(int k) {
  double retval = 0;
  if (k >= 15) {
    retval = k / 15;
    return retval + REK_kosten(k % 15);
  }
  if (k >= 6) {
    retval = (k / 6) * 0.5;
    return retval + REK_kosten(k % 6);
  }
  if (k < 6)
    retval = k * 0.1;
  return retval;
}

Gerade bei sehr vielen Kopien spart das hier eine Menge rekursive Aufrufe. So braucht meine Lösung z.B. für 100 Kopien nur drei Aufrufe von REK_kosten().

 

[Simpson474]

Wobei deine Optimierung im Grunde fast schon die Rekursion überflüssig macht - der folgende Code sollte exakt das Gleiche machen:

public static double REK_kosten(int k) {
  double retval = k / 15;
  k = k % 15;
  
  retval += (k / 6) * 0.5;
  k = k % 6;
 
  return retval + k * 0.1;
};

Ich denke, die Aufgabe sollte viel mehr zeigen, wie eine Rekursion funktioniert. Für die einfachere Verständlichkeit denke ich ist ein unoptimiertes Beispiel besser geeignet.

 

[Cobinja]

Mir ist schon klar, wozu die Aufgabe gedacht ist. Ich wollte aber gerade deswegen daraufhinweisen, dass man bei Rekursionen schnell vom hundertsten in tausendste kommt, was man mit einer kleinen Optimierung beheben kann.

Als Vergleichs-Beispiel (Ok, bei Kopien vllt etwas übertrieben, aber in anderen Bereichen durchaus anwendbar):

50000 Kopien
Deine Rekursion: 3339 Aufrufe
Meine Rekursion: 2 Aufrufe