Erste Schritte Verschiedene Anfängerfragen (Rekursion, Terminierung, Schleife, etc.)

[Esto88]

hallo,
im Zuge meiner Klausurvorbereitungen habe ich noch ein paar Fragen ... bei denen ihr mir vll. weiterhelfen könnt

Rekursion:
Ich habe folgende rekursive Methode und soll folgendes dazu beantworten:
Welchen Wert liefert der Aufruf f(6,4)? In welcher Reihenfolge und mit welchen Parametern wird f dabei rekursiv aufgerufen? Wie groß ist die maximale Rekursivtiefe, d.h. die maximale Anzahl gleichzeitig aktivieter Aufrufe?

static int f(int x, int y) {
  if (x < 2)
    return 1;
  else if (y<= 2)
   return 2;
  else
   return 2 * f(x-2, y/2) + f(x-1,y+1);
}

Frage A: Nun eigentlich dachte ich, ich versteh das ganze, aber anscheinend ist dem nicht so. Denn ist soll 13 Aufrufe geben und 19 herauskommen. (was auch tatsächlich rauskommt, wenn ichs durch Eclipse jage ...)

Ich frage mich was ich da falsch mache, denn ich hab bedeutend mehr aufrufe und bekomme 33 raus. Für meinen Denkansatz siehe Anhang.

Frage B: Oft gibt es bei solchen Aufgaben auch die Frage "Temeniert für alle x>= 0, y >= 0 der Aufruf f(x,y) mit der Rückgabe eines int-Wertes? Begründen Sie Ihre Antwort."

Wie gehe ich denn an so eine Frage am Besten ran? Gibt es ein Theorem/Faustregel oder sowas, das ich anwenden könnte?


Schleife:
Die Frage ist ob folgende Schleife terminiert und was rauskommt:

int x = 1;
int y = 2;
do {
  x = x + y;
  switch (x%3) {
   case 0: y = x + 1;
   case 1: y = x + 2; break;
   case 2: y = x + 3; break;
   default: y = x - 1; break;
  }
}while (y < 20);

Wenn ich das durch Eclipse jage, bekomm ich x = 19, y= 21 ... wenn ichs selbst ausrechne bekomme ich x = 34, y = 36 ... was passiert denn nachdem es das erste mal case 0 eintritt? Also

x = 1, y = 2
x = 3, y = 2 // vor der Schleife
x = 3, y = 4 // case 0
// und nu? laut eclipse müsste case 1 kommen, aber warum  das denn ?

URL: Online Java Compiler - Online Java Editor - Java Code Online - Online Java Runner

 

[stg]

Zunächst schon mal zu (A):
Dein Vorgehen ist richtig, du hast nur direkt zu Beginn einen Fehler im linken Teilbaum. f(4,2) gibt 2 zurück. Damit lautet das Ergebnis schließlich:
2 * 2 + 15 = 19

Eine allgemeingültige Regel zu Problem vom Typ (B) wird es kaum geben. Da hilft nur viele ähnliche Aufgaben durchzugehen, um "ein Gespür dafür zu entwickeln".

x = 1, y = 2
x = 3, y = 2 // vor der Schleife
x = 3, y = 4 // case 0
// und nu? laut eclipse müsste case 1 kommen, aber warum  das denn ?

3+4 ist 7, 7 mod 3 ist 1 ...

 

[CSHW89]

Wenn ich das durch Eclipse jage, bekomm ich x = 19, y= 21 ... wenn ichs selbst ausrechne bekomme ich x = 34, y = 36 ... was passiert denn nachdem es das erste mal case 0 eintritt? Also

x = 1, y = 2
x = 3, y = 2 // vor der Schleife
x = 3, y = 4 // case 0
// und nu? laut eclipse müsste case 1 kommen, aber warum  das denn ?

URL: Online Java Compiler - Online Java Editor - Java Code Online - Online Java Runner

Switch-Case hat in Java (bzw. auch in C, C++, ect...) die "Eigenart", dass wenn ein Case korrekt ist, er alle weiteren Anweisungen dahinter ausführt, also auch die, in den anderen Cases. Dies kann man nur durch ein Break am Ende eines Case verhindern. Im Case 0 fehlt das Break, wodurch die beiden Anweisungen y=x+1 und y=x+2 immer beide ausgeführt werden, wenn Case 0 eintritt.

lg Kevin

 

[Esto88]

alles klar, danke soweit

Nochmal drei kleine Fragen:
1) Wenn ich eine Dezimalzahl in eine Oktazahl umwandeln will, teil ich durch 8, also bspw.:

123[SUB](Dez)[/SUB] = 173[SUB](Okt)[/SUB]

123 : 8 = 15 Rest 3
15: 8 = 1 Rest 7
1: 8 = 0 Rest 1

richtig? Wie sieht das denn aus wenn ich eine negative Dezimalzahl habe, also z.B. -123 ?


2) Wann genau wird bei einer for-Schleife das update ausgeführt? Nach oder vor dem Klammern-Block?
Also Wenn ich z.B.

for (int i = 1; i <= 6; i + 8) { Anweisung A; }

habe. Wird dann Anweisung A ein oder zweimal ausgeführt?



Update: 3) Folgender Code:

                int a = 4;
		int b = 2;
		do {
			a = a+b;
			System.out.println("a vor:"+b);
			if ((a%3) ==0); System.out.println("continue"); continue;
			b = b+1;
			System.out.println("b:"+b);
		} while((a%5) != 0);

Laut meiner Muster-Lösung terminiert der Code mit a = 15, b = 4.
Eclipse sagt aber:

Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	Unreachable code

	at trest.test6.main(test6.java:23)

Warum ist das so? Außerdem wenn die while-Bedingung von vorne herein nicht stimmt, also in dem fall a%5 = 0 wäre; würde sie trotzdem 1 mal durchlaufen und dann erst im zweiten Anlauf stoppen?

 

[arilou]

[...]
Rekursion:
[...]
Frage B: Oft gibt es bei solchen Aufgaben auch die Frage "Temeniert für alle x>= 0, y >= 0 der Aufruf f(x,y) mit der Rückgabe eines int-Wertes? Begründen Sie Ihre Antwort."

Wie gehe ich denn an so eine Frage am Besten ran? Gibt es ein Theorem/Faustregel oder sowas, das ich anwenden könnte?

Zuerst mal, du meinst wohl "Terminiert", nicht "Temeniert".

Theorem/Faustregel:
Ein rekursiver Ablauf terminiert auf jeden Fall, wenn das zu lösende Problem mit jedem Unteraufruf "kleiner"/"einfacher" wird.

In deinem "Rekursion"-Beispiel wird bei jedem Unteraufruf immer x kleiner gemacht - irgendwann muss die Rekursionstiefe dann mit dem "if( x < 2 ) return 1;" -Abschnitt abbrechen (sofern nicht irgendeine andere Bedingung schon vorher den "Ast" beendet).

Theorem: D.h. die "Problemgröße" muss monoton fallend sein - es muss nicht "steng monoton" sein, sofern sichergestellt ist, dass kein Rekursions-"Ast" sich in "gleichbleibender Problemgröße" verfangen kann.

 

[arilou]

zu 1): im Zweifelsfall - wandle die entsprechende positive Zahl, und setz' vor die Oktalzahl dann '-'...

zu 2): In deiner for-Schleife muss es wohl "i += 8" lauten, da fehlt ein '='; der Schleifenkörper wird 1* ausgeführt wobei i=1; dann wird i auf 9 hochgezählt, was nicht mehr der Durchlaufbedingung entspricht, womit die Schleife dann abbricht.

zu 3): Auch hier ein offensichtlicher Programmierfehler:

if ((a%3) ==0) { System.out.println("continue"); continue; }

Schon der ';' beendet den if - er muss weg. Zusätzlich hast du die '{' und '}' um den .println() und den continue; vergessen.