Problem
Beginne die Folge mit 1 und 2. Jeder folgende Term ist die Summe der beiden vorherigen. Berücksichtige nur gerade Terme, die höchstens so groß wie limit sind, und addiere sie.
Implementiere even_fibonacci_sum(limit).
Eingabe
limit: Der größte Wert eines Terms, der berücksichtigt werden darf.
Ausgabe
Gib die Summe zurück, oder 0, falls es keine passenden Terme gibt.
Einschränkungen
0 ≤ limit ≤ 10¹⁵. Das Ergebnis passt in einen vorzeichenbehafteten 64-Bit-Integer.
Beispiele
Eingabe:
limit = 50
Erwartete Ausgabe:
expected = 44Eingabe:
long long limit = 50;
Erwartete Ausgabe:
long long expected = 44;Eingabe:
long limit = 50;
Erwartete Ausgabe:
long expected = 44;Erläuterung
Die geraden Terme sind 2, 8 und 34. Ihre Summe ist 44.
Eingabe:
limit = 1
Erwartete Ausgabe:
expected = 0Eingabe:
long long limit = 1;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long limit = 1;
Erwartete Ausgabe:
long expected = 0;Erläuterung
Der erste gerade Term ist 2, der den Grenzwert überschreitet.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Du brauchst nur die geraden Fibonacci-Zahlen, nicht die ganze Folge.
Hinweis 2
Erzeuge die Folge, bis der nächste Term das Limit überschreitet, und addiere die passenden Terme.
Hinweis 3
Achte auf die Grenze, wenn das Limit selbst eine Fibonacci-Zahl ist.
Erwartete Komplexität
Zeit O(log limit), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.