Fibonacci Folge

• 1.1 Aufgabenstellung
• 1.2 Schreiben von Code 
• 1.3 Spezifischere Aufgabenstellung
• 1.4 Debuggen von Code
• 1.5 Testen von Code
• 1.6 Optimieren von Code 
• 1.7 Von Python zu C++
• Fazit

1.1 Aufgabenstellung

Schreibe einen Code für eine Fibonacci Folge.

1.2 Schreiben von Code

def fibonacci_sequence(n):
    sequence = []
    if n >= 1:
        sequence.append(0)
    if n >= 2:
        sequence.append(1)
    for i in range(2, n):
        sequence.append(sequence[i-1] + sequence[i-2])
    return sequence

n = 10
result = fibonacci_sequence(n)
print(result)

Anmerkung:

ChatGPT: In diesem Code wird die Funktion fibonacci_sequence(n) verwendet, um eine Liste zu erzeugen, die die Fibonacci-Zahlen bis zur gegebenen Anzahl n enthält. Die Funktion beginnt mit einer leeren Liste sequence.

Für n größer oder gleich 1 wird die Zahl 0 zur Sequenz hinzugefügt. Wenn n größer oder gleich 2 ist, wird auch die Zahl 1 zur Sequenz hinzugefügt.

Dann wird eine Schleife von 2 bis n-1 durchlaufen, und in jedem Schritt wird die Summe der beiden vorherigen Zahlen in die Sequenz eingefügt.

Am Ende wird die generierte Sequenz zurückgegeben und ausgegeben.

Im Beispiel wird n auf 10 gesetzt, was bedeutet, dass die ersten 10 Fibonacci-Zahlen generiert werden. Das Ergebnis wird ausgegeben. Man kann den Wert von n anpassen, um eine Fibonacci-Folge unterschiedlicher Länge zu erzeugen.

1.3 Spezifischere Aufgabenstellung

Vor langer Zeit entdeckte ein Archäologen Team eine uralte Höhle, die voller Rätsel und Geheimnisse war. Tief im Inneren der Höhle fand das Team ein mysteriöses Artefakt, das mit alten Inschriften bedeckt war.

Die Inschriften wiesen auf eine geheime Bedeutung der Fibonacci-Folge hin. Es hieß, dass die Fibonacci-Zahlen eine Schlüsselrolle bei der Entschlüsselung des Artefakts spielen könnten. Die Legende besagte, dass das Artefakt eine unglaubliche Macht besaß, aber nur freigesetzt werden konnte, wenn eine bestimmte Eigenschaft der Fibonacci-Folge erfüllt war.

Die Archäologen standen vor der Aufgabe, diese Eigenschaft der Fibonacci-Folge zu entschlüsseln und den Wert zu finden, der das Artefakt aktivieren würde. Sie studierten die Inschriften und erkannten, dass das Geheimnis in der Summe bestimmter Fibonacci-Zahlen lag.

Die Aufgabe bestand darin, den kleinsten Wert n zu finden, für den die Summe aller Fibonacci-Zahlen bis zur n-ten Zahl ein bestimmtes Ziel überstieg. Das Team brauchte diese Information, um das Artefakt zu aktivieren und seine Macht freizusetzen.

Die Archäologen setzten ihre mathematischen Fähigkeiten ein, um den Code zu knacken und das Geheimnis der Fibonacci-Folge zu entschlüsseln. Sie schrieben ein Programm, das die Fibonacci-Zahlen generierte und die Summe berechnete, bis das Ziel überschritten wurde. Schließlich fanden sie den gesuchten Wert n und konnten das Artefakt aktivieren.

Ihre Aufgabe besteht nun darin, das Programm der Archäologen zu vervollständigen. Schreiben Sie eine Funktion, die den kleinsten Wert n berechnet, für den die Summe aller Fibonacci-Zahlen bis zur n-ten Zahl ein gegebenes Ziel überschreitet. Sie können Ihre Lösung basierend auf den Erkenntnissen und dem Code der Archäologen entwickeln.

Bereiten Sie sich darauf vor, das Artefakt zu aktivieren und seine geheimnisvolle Macht zu entfesseln!

Erster Code:

def activate_artifact(target_sum):
    fibonacci_sequence = [0, 1]
    sum_fibonacci = 1
    n = 2

    while sum_fibonacci <= target_sum:
        fibonacci_num = fibonacci_sequence[n-1] + fibonacci_sequence[n-2]
        fibonacci_sequence.append(fibonacci_num)
        sum_fibonacci += fibonacci_num
        n += 1

    return n

target_sum = 1000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Anmerkung:

In diesem Code wird die Funktion activate_artifact(target_sum) definiert, die den kleinsten Wert n berechnet, für den die Summe aller Fibonacci-Zahlen bis zur n-ten Zahl das Ziel target_sum überschreitet.

Die Funktion verwendet eine Liste fibonacci_sequence, um die Fibonacci-Zahlen zu speichern. Zu Beginn sind die ersten beiden Zahlen (0 und 1) bereits in der Liste enthalten. Eine Variable sum_fibonacci wird initial auf 1 gesetzt, da die Summe bisher nur die erste Fibonacci-Zahl (1) ist. Der Wert n steht für den aktuellen Index der Fibonacci-Zahlen.

In einer Schleife wird die Fibonacci-Folge fortgesetzt, indem in jedem Schritt die nächste Fibonacci-Zahl berechnet wird, indem die letzten beiden Zahlen in der Liste addiert werden. Die berechnete Zahl wird zur Liste hinzugefügt und zur sum_fibonacci-Variable addiert.

Die Schleife wird solange ausgeführt, bis sum_fibonacci das Ziel target_sum überschreitet. Dann wird n zurückgegeben, da n den Index der nächsten Fibonacci-Zahl darstellt, die die Summe überschreitet.

Im Beispiel wird target_sum auf 1000 gesetzt. Der Code berechnet den kleinsten Wert n, bei dem die Summe aller Fibonacci-Zahlen bis zur n-ten Zahl 1000 überschreitet. Das Ergebnis wird ausgegeben.

Sie können den Wert von target_sum anpassen, um verschiedene Szenarien zu testen und den Index der Fibonacci-Zahl zu finden, bei dem die Summe das Ziel überschreitet.

Bereiten Sie sich darauf vor, das Artefakt zu aktivieren und seine geheimnisvolle Macht zu entfesseln!

Ergebnis:

Der Code funktioniert und gibt den richtigen Wert der das Artefakt aktiviert wider.

1.4 Debuggen von Code

Funktionierender Code:

def activate_artifact(target_sum):
    fibonacci_sequence = [0, 1]
    sum_fibonacci = 1
    n = 2

    while sum_fibonacci <= target_sum:
        fibonacci_num = fibonacci_sequence[n-1] + fibonacci_sequence[n-2]
        fibonacci_sequence.append(fibonacci_num)
        sum_fibonacci += fibonacci_num
        n += 1

    return n

target_sum = 1000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Fehlerhafter Code:

def activate_artifact(target_sum):
    fibonacci_sequence == [0, 1]  # Fehler: Falscher Operator, sollte "=" statt "==" sein
    sum-fibonacci = 1  # Fehler: Ungültiges Zeichen "-", sollte ein "_" sein
    n = 2
    while sum_fibonacci <= target_sum:
        fibonacci_num = fibonacci_sequence[n-1] + fibonacci_sequence[n-2]
        fibonacci_sequence.append(fibonacci_num)
        sum_fibonacci += fibonacci_num
        n += 1
    return n - 1

target_sum = 1000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Debugged:

def activate_artifact(target_sum):
    fibonacci_sequence = [0, 1]
    sum_fibonacci = 1
    n = 2

    while sum_fibonacci <= target_sum:
        fibonacci_num = fibonacci_sequence[n] + fibonacci_sequence[n-2]
        fibonacci_sequence.append(fibonacci_num)
        sum_fibonacci += fibonacci_num
        n += 1

    return n - 1

target_sum = 1000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Ergebnis:

Der Debuggte Code ist zwar frei von Syntaxfehlern, jedoch sind einige Logikfehler beibehalten worden, sodass der Code dennoch nicht funktioniert.

Debugge den Code mithilfe der Artefakt Aufgabenstellung.

def activate_artifact(target_sum):
    fibonacci_sequence = [0, 1]
    sum_fibonacci = 1
    n = 2

    while sum_fibonacci <= target_sum:
        fibonacci_num = fibonacci_sequence[n-1] + fibonacci_sequence[n-2]
        fibonacci_sequence.append(fibonacci_num)
        sum_fibonacci += fibonacci_num
        n += 1

    return n - 1

target_sum = 1000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Ergebnis:

Mithilfe der Aufgabenstellung schafft es ChatGPT den Code vollständig zu debuggen. Der Code ist jetzt frei von Syntax und Logikfehlern.

1.5 Testen von Code

Teste diesen Code, indem du sinnvolle Werte verwendest

Hier sind alle Testwerte:

Große Zielsummen:

target_sum = 1000000
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Mit einer großen Zielsumme von 1.000.000 testen wir die Leistungsfähigkeit des Codes und ob er korrekte Ergebnisse in angemessener Zeit liefert.

Negative Zielsummen:

target_sum = -100
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Teste, wie der Code mit negativen Zielsummen umgeht. Beachte, dass die Summe der Fibonacci-Zahlen nie negativ sein kann, daher sollte das Ergebnis möglicherweise spezifiziert werden, dass das Artefakt nicht aktiviert werden kann.

Zielsummen kleiner als die erste Fibonacci-Zahl:

target_sum = 5
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

In diesem Fall ist die Zielsumme kleiner als die erste Fibonacci-Zahl (1). Das Ergebnis sollte spezifiziert werden, dass das Artefakt nicht aktiviert werden kann.

Zielsummen gleich der ersten Fibonacci-Zahl:

target_sum = 1
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Wenn die Zielsumme genau der ersten Fibonacci-Zahl entspricht, sollte das Ergebnis der Index 2 sein.

Zielsummen gleich einer Fibonacci-Zahl:

target_sum = 55
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Wenn die Zielsumme einer bestimmten Fibonacci-Zahl entspricht, sollte das Ergebnis der Index dieser Fibonacci-Zahl sein.

Leere Zielsumme:

target_sum = 0
result = activate_artifact(target_sum)
print(f"The artifact will be activated at Fibonacci index: {result}")

Eine Zielsumme von 0 sollte spezifiziert werden, dass das Artefakt nicht aktiviert werden kann.

Indem wir sinnvolle Testwerte verwenden, stellen wir sicher, dass der Code auf realistische Szenarien reagiert und korrekte Ergebnisse liefert.

Ergebnis:

Es ist wichtig ChatGPT ausführlich zu beschreiben was das Ziel und der Weg einer Aufgabe ist. Zuerst habe ich ChatGPT gefragt, ob es mir den Code auf unterschiedliche Werte testen kann. Daraufhin hat er mir Ergebnisse für die Werte 50, 100 und 5000 ausgegeben. Danach habe ich ChatGPT gefragt ob es die Testwerte für sinnvoll hält und habe daraufhin folgende mit Bedacht gewählte Testwerte ausgegeben bekommen.

1.6 Optimieren von Code

Unoptimierter Code mit Zeitrechnung

Zeitwerte:

target_sum 1.000 à 0.0006787776947021484 seconds

target_sum 10.000 à 0.006041765213012695 seconds

target_sum 100.000 à 0.11957406997680664 seconds

target_sum 1.000.000 à 1.8766372203826904 seconds

target_sum 10.000.000 à 39.43403458595276 seconds

Optimierter Code mit Zeitrechnung

import time

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

target_sum = 1000
fibonacci_sequence = []
sum_fibonacci = 0
n = 0

# Zeitmessung starten
start_time = time.time()

# Generierung der Fibonacci-Zahlen bis zur Zielsumme
while sum_fibonacci <= target_sum:
    fibonacci_num = fibonacci(n)
    fibonacci_sequence.append(fibonacci_num)
    sum_fibonacci += fibonacci_num
    n += 1

# Zeitmessung beenden
end_time = time.time()

result = n - 1
print(f"The artifact will be activated at Fibonacci index: {result}")
print(f"Time taken for computation: {end_time - start_time} seconds")

Zeitwerte:

target_sum 1.000 à 0.00045299530029296875 seconds

target_sum 10.000 à 0.0003542900085449219 seconds

target_sum 100.000 à 0.0003669261932373047 seconds

target_sum 10^681 à 1.1066935062408447 seconds

Ergebnis:

Man sieht, dass ein optimierter Code einiges ausmacht. Während der nicht optimierte Code bei einer Zahl mit Sieben Nullen bereits 39.43 Sekunden für die Berechnung benötigt hat, hat der optimierte Code erst bei einer Zahl mit 681 Nullen über eine Sekunde Berechnungszeit benötigt!

Der optimierte Code ist wesentlich schneller, weil er die exponentielle Matrixpotenzierung verwendet, um die Fibonacci-Zahlen effizient zu berechnen. Im Vergleich zum unoptimierten rekursiven Ansatz hat die exponentielle Matrixpotenzierung mehrere Vorteile:

1. Reduzierte Anzahl von Berechnungen: Der rekursive Ansatz berechnet viele Fibonacci-Zahlen mehrmals, was zu redundanten Berechnungen führt. Die exponentielle Matrixpotenzierung berechnet jede Fibonacci-Zahl nur einmal und speichert das Ergebnis für zukünftige Verwendung.
2. Lineare Laufzeitkomplexität: Der rekursive Ansatz hat eine exponentielle Laufzeitkomplexität von O(2^n), was bedeutet, dass die Berechnungszeit mit jeder weiteren Fibonacci-Zahl stark ansteigt. Die exponentielle Matrixpotenzierung hat hingegen eine lineare Laufzeitkomplexität von O(log n), was bedeutet, dass die Berechnung auch für große Indizes effizient bleibt.
3. Effiziente Matrixoperationen: Die exponentielle Matrixpotenzierung nutzt optimierte Matrixoperationen, um die Berechnungen durchzuführen. Diese Operationen sind in effizienten Bibliotheken wie NumPy implementiert, was zu schnelleren Berechnungen führt.

Durch die Kombination dieser Vorteile kann der optimierte Code die Fibonacci-Zahlen viel schneller berechnen als der unoptimierte rekursive Ansatz. Es ist wichtig anzumerken, dass die exponentielle Matrixpotenzierung nicht nur für Fibonacci-Zahlen, sondern auch für andere rekursive Sequenzen oder Transformationen nützlich sein kann, um die Berechnungszeit zu reduzieren.

1.7 Python zu C++

#include <iostream>

#include <vector>

#include <cmath>

// Funktion zur Berechnung der Matrixpotenz

std::vector<std::vector<long long>> matrixPower(const std::vector<std::vector<long long>>& matrix, int n) {

   if (n == 0) {

       std::vector<std::vector<long long>> identity(matrix.size(), std::vector<long long>(matrix.size(), 0));

       for (int i = 0; i < matrix.size(); ++i) {

           identity[i][i] = 1;

       }

       return identity;

   }

   if (n == 1) {

      return matrix;

   }

   std::vector<std::vector<long long>> halfPower = matrixPower(matrix, n / 2);

   std::vector<std::vector<long long>> result = matrixMultiply(halfPower, halfPower);

   if (n % 2 == 1) {

       result = matrixMultiply(result, matrix);

   }

   return result;

}

// Funktion zur Matrixmultiplikation

std::vector<std::vector<long long>> matrixMultiply(const std::vector<std::vector<long long>>& matrix1, const std::vector<std::vector<long long>>& matrix2) {

   int rows1 = matrix1.size();

   int cols1 = matrix1[0].size();

   int cols2 = matrix2[0].size();

   std::vector<std::vector<long long>> result(rows1, std::vector<long long>(cols2, 0));

   for (int i = 0; i < rows1; ++i) {

       for (int j = 0; j < cols2; ++j) {

           for (int k = 0; k < cols1; ++k) {

               result[i][j] += matrix1[i][k] * matrix2[k][j];

           }

       }

   }

   return result;

}

// Funktion zur Berechnung der Fibonacci-Zahl

long long fibonacci(int n) {

   if (n <= 1) {

       return n;

   }

   std::vector<std::vector<long long>> matrix = {{1, 1}, {1, 0}};

   std::vector<std::vector<long long>> result = matrixPower(matrix, n - 1);

   return result[0][0];

}

int main() {

   int target_sum = 1000;

   std::vector<long long> fibonacci_sequence;

   long long sum_fibonacci = 0;

   int n = 0;

   // Generierung der Fibonacci-Zahlen bis zur Zielsumme

   while (sum_fibonacci <= target_sum) {

       long long fibonacci_num = fibonacci(n);

       fibonacci_sequence.push_back(fibonacci_num);

       sum_fibonacci += fibonacci_num;

       n++;

   }

   int result = n - 1;

   std::cout << "The artifact will be activated at Fibonacci index: " << result << std::endl;

   return 0;

}

In diesem C(++)-Code werden die Funktionen matrixPower und matrixMultiply implementiert, um die Matrixpotenzierung und Matrixmultiplikation durchzuführen. Die Funktion fibonacci berechnet die Fibonacci-Zahl unter Verwendung der exponentiellen Matrixpotenzierung. Der Hauptteil des Codes generiert dann die Fibonacci-Zahlen bis zur Zielsumme und gibt den Index des Artefakts aus.

Bitte beachten Sie, dass in diesem C(++)-Code long long für die Fibonacci-Zahlen verwendet wird, um den größeren Zahlenraum zu ermöglichen.

Fazit