G
Guest
Gast
Hi zusammen,
ich habe die Aufgabe einen Algorithmus zu implementieren, der die Fibonacci-Zahl berechnet.
Dabei lautet die Aufgabenstellung:
Sei F(n) die n-te Fibonacci-Zahl. Zur konkreten Berechnung von F(n) zu
einem bekannten n gibt es zwei Algorithmen:
(Algorithmus A)
Man f¨uhrt fibonacci(n) durch. Die Programmroutine fibonacci(k)
bekommt als Eingabevariable k und liefert F(k) zur¨uck. Ihr Ablauf:
• Wenn k = 0, dann F(k) := 0
• Wenn k = 1, dann F(k) := 1
• Wenn k /2 {0, 1}, dann:
– F¨uhre fibonacci(k-1) durch; erhalte F(k − 1)
– F¨uhre fibonacci(k-2) durch; erhalte F(k − 2)
– Berechne F(k) = F(k − 1) + F(k − 2)
• Liefere den Wert F(k) zur¨uck.
(Algorithmus B)
1. Starte mit F(0) = 0, F(1) = 1, k = 0
2. Setze G(k) = (F(k + 1), F(k))
3. Speichere G(k)
4. Berechne F(k + 2) als Summe der beiden Komponenten von G(k)
5. Erh¨ohe k um 1
6. Abbruch für k + 1 = n, sonst zurück zu Schritt 2
(i) Berechne die Anzahl der benötigten Additionen für beide Algorithmen
am Beispiel n = 6.
Meine Implementierung:
Allerdings erhalte ich mit algoA(6) als Ergebnis 8 und mit algoB(6) als Ergebnis 9.
Meine Frage daher: Sind die beiden Algorithmen so korrekt nach der Aufgabenstellung programmiert? Mich verwundert das unterschiedliche Ergebnis von AlgoA und B.
ich habe die Aufgabe einen Algorithmus zu implementieren, der die Fibonacci-Zahl berechnet.
Dabei lautet die Aufgabenstellung:
Sei F(n) die n-te Fibonacci-Zahl. Zur konkreten Berechnung von F(n) zu
einem bekannten n gibt es zwei Algorithmen:
(Algorithmus A)
Man f¨uhrt fibonacci(n) durch. Die Programmroutine fibonacci(k)
bekommt als Eingabevariable k und liefert F(k) zur¨uck. Ihr Ablauf:
• Wenn k = 0, dann F(k) := 0
• Wenn k = 1, dann F(k) := 1
• Wenn k /2 {0, 1}, dann:
– F¨uhre fibonacci(k-1) durch; erhalte F(k − 1)
– F¨uhre fibonacci(k-2) durch; erhalte F(k − 2)
– Berechne F(k) = F(k − 1) + F(k − 2)
• Liefere den Wert F(k) zur¨uck.
(Algorithmus B)
1. Starte mit F(0) = 0, F(1) = 1, k = 0
2. Setze G(k) = (F(k + 1), F(k))
3. Speichere G(k)
4. Berechne F(k + 2) als Summe der beiden Komponenten von G(k)
5. Erh¨ohe k um 1
6. Abbruch für k + 1 = n, sonst zurück zu Schritt 2
(i) Berechne die Anzahl der benötigten Additionen für beide Algorithmen
am Beispiel n = 6.
Meine Implementierung:
Code:
public int algoA(int n) {
if (n == 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else {
counter++;
return algoA(n - 1) + algoA(n - 2);
}
}
public int algoB(int n) {
int k = 0;
int fK = 0;
int[] gK = new int[2];
do {
gK[0]= k + 1;
gK[1]=k;
counter++;
fK = gK[0] + gK[1];
k++;
}
while (k + 1 < n);
return fK;
}
Allerdings erhalte ich mit algoA(6) als Ergebnis 8 und mit algoB(6) als Ergebnis 9.
Meine Frage daher: Sind die beiden Algorithmen so korrekt nach der Aufgabenstellung programmiert? Mich verwundert das unterschiedliche Ergebnis von AlgoA und B.