Rekursion

[EveresT]

Hallo,

ich versuche derzeit Java zu erlernen mit dem Programmierkus Java von Programmierkurs Java .Noch bin ich bei der imperativen Programmierung und habe da bereits Probleme mit der Rekursion, weshalb ich mehrere Übungsaufgaben durcharbeite.

Die Aufgabenstellung bei der ich Probleme habe ist folgende:

Es sollen mehrere Funktionen implementiert werden:

int getAnzahlZiffern(int zahl);


int getZiffernWert(int zahl, int stelle);  

Gibt den Ziffernwert an einer best. Stelle aus (Stelle zählt vonn rechts nach links bei 0 beginnend).


int ersetzeZiffer(int zahl, int stelle, int ziffer);

Eine Ziffer der Zahl "zahl" soll an Stelle "stelle" mit der Ziffer "ziffer" ersetzt werden. Diese Funktion macht mir Probleme, ich war bisher nur in der Lage sie mit einer zusätzlichen Variablen "durchlauf" zu lösen, was aber wohl nicht Sinn der Sache ist. Deswegen denke ich, dass ich noch etwas grundlegendes bei der Rekursion nicht verstanden habe und wäre froh, hier den entscheidenden Tipp zu erhalten.


Quellcode:


public class UEA8 {


	static int getBetrag(int zahl){

		if(zahl>=0)

			return zahl;

		else{

			return zahl*-1;

		}

	}


	static int getAnzahlZiffern(int zahl){

		if(getBetrag(zahl)>0){

			return getAnzahlZiffern(zahl/10)+1;

		}

		return 0;


	}


	static int getZiffernWert(int zahl, int stelle){

		if(stelle>0){

			return getZiffernWert(zahl/10, stelle-1);

		}

		return zahl%10;

	}




	static int ersetzeZiffer(int zahl, int stelle, int ziffer,int durchlauf){

		if(stelle>0){

			return ersetzeZiffer( zahl/10, stelle-1, ziffer, durchlauf+1)+(zahl%10)*potenz(10,durchlauf); 

		}

		zahl=zahl/10;

		if(zahl>0){

			zahl=zahl*10+ziffer;	

		}else{

			zahl=zahl*10-ziffer;

		}





		return  zahl*potenz(10,durchlauf);


	}



	public static int potenz(int zahl, int pot){

		if (pot==0)

			return 1;

		if (pot>0){	

			return potenz(zahl, pot-1)*zahl;

		}

		if (pot<0){

			return 1/(potenz(zahl, -pot-1)*zahl);

		}

		return 0;

	}	




	public static void main(String[]args){

		int zahl=IO.readInt("Zahl:");

		int stelle=IO.readInt("Die wievielte Ziffer soll ersetzt werden?:");		

		int ziffer=IO.readInt("Mit welcher Ziffer soll diese Ziffer ersetzt werden?");


		System.out.println("Betrag: " +getBetrag(zahl));

		System.out.println("Anzahl Ziffern: " +getAnzahlZiffern(zahl));

		System.out.println("Diese Ziffer wird ersetzt: "+getZiffernWert(zahl, stelle));

		System.out.println("Neue Zahl: " +ersetzeZiffer(zahl, stelle,ziffer, 0));


	}

}

Bearbeitet 18. Januar 2011 von flashpixx
Code-Tags

[flashpixx]

Bitte verwende das nächste mal Code-Tags

[Torsten Hündling]

Als erstes Mal

@flashpixx: Wenn du keine Lust hast, dich mit dem Problem zu beschäftigen -> syntax ist nicht alles (ich glaube, es geht hier nicht um code-tags, auch wenn diese das Leben vielleicht einfacher machen)

@EveresT: du hast die aufgaben gepostet ... und du hast eine rekursive lösung dieser aufgaben direkt danach danach gepostet. wie wäre es, wenn du eine frage stellst, was du nicht verstehst:

Wenn es nur um Rekursion geht, frag Dich doch einfach mal, wie oft du 1 von einer X-beliebigen Zahl abziehen musst, bist du 0 erhältst?

Bearbeitet 19. Januar 2011 von Torsten Hündling

[flashpixx]

Als erstes Mal

@flashpixx: Wenn du keine Lust hast, dich mit dem Problem zu beschäftigen -> syntax ist nicht alles (ich glaube, es geht hier nicht um code-tags, auch wenn diese das Leben vielleicht einfacher machen)

zur Info http://forum.fachinformatiker.de/java/143878-posten-code-speziell-fuer-newbies.html

[EveresT]

@ flashpixx: In Ordnung werde ich das nächste mal berücksichtigen, wusste ich nicht. Muss aber auch zugeben, dass ich mir zuvor nicht die Mühe gemacht habe die entsprechenden Forenregeln durchzulesen.

@ Torsten Hündlung: Sorry, habe mich wohl nich klar genug ausgedrückt. In der Aufgabenstellung war die Rede von der Funktion

"int ersetzeZiffer(int zahl, int ziffer, int stelle);"

Ich habe die Aufgabe aber nur lösen können, indem ich eine Hillfsvariable "int durchlauf", sowie eine weitere Funktion "int potenz(int zahl, int pot)" hinzugezogen habe. Diese Lösung mit der Hilfsvariable erscheint mir sehr ähnlich einer Schleifenlösung (vielleicht bilde ich mir das auch nur ein weil ich nich genug Ahnung habe), was ja nicht Sinn der Sache ist. Ich wollte wissen ob es eine Lösung gibt, ohne diese Hilfsvariable, d.h. nur mit der Funktion

"int ersetzeZiffer(int zahl, int ziffer, int stelle);". Wenn dem so wäre, wüsste ich gerne wie, weil mir dann hoffentlich die Rekursion noch klarer wird. =)

Und zu der Frage: So oft wie ich 1 zu 0 addieren muss um diese Zahl zu erhalten. =) Meinst du das so?

Bearbeitet 19. Januar 2011 von EveresT

[flashpixx]

zu der Stellenposition: man braucht nur 2 Parameter, die Zahl und die Stelle.

Mach es Dir an einem Bsp klar: Wenn ich die Zahl 12345 habe und ich will die 3. Stelle, d.h. die "3", wie komme ich daran !? Überlege Dir, wie die Zahl im Dezimalsystem repräsentiert, d.h. was die Stellen aussagen. Mit ein bisschen Mathematik aus der Grundschule kann man das schnell berechnen

[EveresT]

Ja das mit der Stellenposition habe ich ja auch in der Funktion

"getZiffernWert(int zahl, int stelle);" realisiert. Das Problem ist jetzt aber, dass ich eine Stelle ersetzen muss. Dann muss ich ja die entsprechenden letzten Ziffern abtrennen, sie aber gleichzeitig speichern, um sie später wieder hinzuzufügen, wobei sie entsprechend mit 10^x mulitipliziert werden müssen.

Oder denke ich zu kompliziert bzw. falsch?

[flashpixx]

Oder denke ich zu kompliziert bzw. falsch?

nur ein Hinweis: Du hast die Zahl 12345 und willst die 3. Stelle, was passiert denn wenn Du 12345 durch 10^3 dividierst ?

[Torsten Hündling]

12345 = 1*10^(4) + 2345;

2345 = 2*10^(3) + 345;

345 = 3*10^(2)+45;

Wenn du dann noch siehst, dass die entsprechende 10er Potenz um 1 niedriger ist, als die Anzahl der Stellen in der aktuellen Rekursion hast Du eigentlich alle Informationen zusammen, die Du brauchst.

Basisfall: Ziffer * 10er Potenz + Zahl % 10er Potenz.

[EveresT]

Danke, das hat schon weitergeholfen!

Habe jetzt folgenden Code entwickelt, der zwar noch nicht richtig ist, habe ihn aber mit Comments versehen, vielleicht kannst du mir ja sagen, was ich da falsch sehe. Wichtig zu erwähnen ist noch, das hab ich bisher vergessen, die Stellen werden von rechts nach links ausgelsen wobei, die erste Zahl Stelle 0 ist,z.B. bei 3456 wäre Stelle 2 die 4.

static int ersetzeZiffer(int zahl, int stelle, int ziffer){

		if(stelle>0){

			return ersetzeZiffer(zahl/potenz(10,stelle), stelle=0, ziffer) +(zahl%potenz(10,stelle));

			/*

			 *Ruft die Funktion erneut auf, wobei die Variable "zahl" soviele Ziffern

			 *abgeschnitten kriegt, bis die zu ersetzende Ziffer die letzte Ziffer

			 *ist.

			 *Die Variable "stelle" wird 0, die Ziffer bleibt gleich.

			 * Zurueckgegebn wird der entsprechende abgeschnittene Wert.

			 */

		}

		/*  

		 * Bei der zweiten Inkarnation ist stelle==0, also kommen wird zum unteren

		 * Teil.

		 */

		zahl=zahl/10; // die zu ersetzende Ziffer wird abgeschnitten

		zahl=zahl*10+ziffer; // die einzusetzende Ziffer wird angehängt

		return +(zahl*potenz(10,stelle));	/*

											 * Zu dem vorhin bereits gelieferten Wert,

											 * werden die ersten Ziffern zurückgeliefert,

											 * die so häufig *10 genommen werden, dass

											 * die Groesse der eingegeben Zahl erhalten

											 * wird.

											 */ 

[Torsten Hündling]

if(stelle > 0) {

 // Rekursion

}

return +(zahl*potenz(10,stelle));

Das heißt, dass Du 10^0 nimmst und nicht wie eigentlich gedacht, den ermittelten Wert wieder auf die ursprüngliche Potenz hochmultiplizierst.

[EveresT]

Ja logisch, habe stelle ja gleich 0 gesetzt beim zweiten Funktionsaufruf, danke!

Also muss ich entweder in die if-Bedingung zu Beginn eine andere Bedingung setzen bzw. irgendwie wieder den ursprünglichen Stellen wert erhalten, richtig? *grübel*

[Torsten Hündling]

Der Basisfall, in dem die Rekursion abbricht, ist, wenn stelle == 1 (oder 0) - 1 bietet sich in diesem Fall etwas an.

ein Beispiel für den Basisfall

ersetzeZiffer(12345, 1, 9) {

  int ersteStelle = 12345 / 10^4; // ersteStelle  = 1

  int rest = 12345 % 10^4; // rest = 2345

  return 9 * 10^4 + rest; // 52345

}

Wenn die Stelle > 1 ist, muss eine rekursiver Aufruf erfolgen. Diesem übergibst du dann das kleinere Problem, nämlich rest = 2345 und stelle = stelle -1;

In der Return-Anweisung sind eigentlich schon alle Informationen erhalten. Den Teil 9 * 10^4 kann man anhand der übergebenen Parameter bestimmen und der Teil "+ rest" wird rekursiv mit neuen Parametern bestimmt.