Hilfe bei Pseudocode-Frage

Endaleyn

Mitglied
Hallo,

ich hab folgenden Pseudocode gegeben:

Code:
 f(x,y) = if x < y then 0 else f(x-y, y) + 1 fi

Und soll dies Fragen beantworten

(a) Geben Sie fur x = 27, y = 5 die Folge der Aufrufe von f an.
(b) Welche Funktion wird durch diesen Algorithmus realisiert?
(c) Fur welche Werte terminiert f ?

Zu a)
Verstehe ich das richtig:

1. f(27,5)=f(27-5,5)+1=f(22,5)+1= ?
2. f(22,5)=f(22-5,5)+1=f(17,5)+1= ?
3. f(17,5)=f(17-5,5)+1=f(12,5)+1= ?
4. f(12,5)=f(12-5,5)+1=f(7,5)+1= ?
5. f(7,5)=f(7-5,5)+1=(2,5)+1= 0 // da x<y

daraus würde für c) folgen für die Werte x=2 und y=5, aber das wäre wohl zu einfach.
 
Doch, stimmt.
Ich habe mir da keine große Mühe gemacht:

Java:
public class F {
	public static void main(String[] args) {
		System.out.println(f(27, 5));
	}
	private static int f(int x, int y) {
		System.out.println(x + " - " + y);
		return(x < y ? 0 : f(x - y, y) + 1);
	}
}

Code:
27 - 5
22 - 5
17 - 5
12 - 5
7 - 5
2 - 5
5
 
Zuletzt bearbeitet:
Welche Funktion wird dadurch realisiert?
Für mich sieht es so aus als könnte man den Rest einer ganzzahligen Division ermitteln? 27 - 5*Aufrufe = Rest 2
 
Ich bin mir nicht 100 % sicher 🙂oops🙂, aber wenn ich mich nicht täusche lernt man sie bereits in der Grundschule (ist wohl das Schlimmste, was man in Mathe dort lernt) und hat in Java nur 1 Zeichen als Operator.
 
Das ist eine Ganzzahldivision: Solange x größer/gleich y ist, wird davon y abgezogen. Das +1 in der Formel "zählt" sozusagen die Anzahl der Aufrufe, und damit wie oft y in x enthalten ist.

Eine iterative Version wäre:

Java:
public void int f(int x, int y) {
   public int result = 0;
   while(x >= y) {
       x = x - y;
       result = result + 1;
   }
   return result;
}
 
Zuletzt bearbeitet:

Neue Themen


Zurück
Oben