Aufgabe«Leonardo von Pisa»

💻 Python

Der große Mathematiker Leonardo Pisan, bekannt unter dem Pseudonym Fibonacci, hinterließ uns die berühmte Zahlenfolge. Jedes ihrer Elemente, beginnend mit dem dritten, ist die Summe der beiden vorherigen.

Die Fibonacci-Folge ist wie folgt definiert:
Φ₀ = 0
Φ₁ = 1
Φₙ = Φₙ₋₁ + Φₙ₋₂ für n > 1

Der Anfang der Folge sieht so aus: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Sie erhalten eine natürliche Zahl A. Ihre Aufgabe — Bestimmen Sie, ob diese Zahl Teil der Fibonacci-Folge ist. Wenn ja, geben Sie ihre Seriennummer N (Index) aus, sodass Φₙ = A. Wenn die Zahl 1 in der Folge vorkommt, nehmen Sie an, dass ihr Index 1 ist. Wenn die Zahl A keine Fibonacci-Zahl ist, geben Sie -1 aus.

Eingabeformat

Die Eingabe erfolgt durch eine ganze nicht-negative Zahl a (0 ≤ a ≤ 10¹⁸).

Ausgabeformat

Geben Sie eine ganze Zahl ein: die Seriennummer N, für die & Phi; n = A. Wenn eine solche Zahl nicht existiert, geben Sie -1 aus.

Beispiel

Eingabe

Ausgabe

Hinweis

There will be no clue here, decide for yourself!

main.py

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Entwicklerlösung

# Получаем на вход число A
a = int(input())

# Обрабатываем частный случай для 0
if a == 0:
    print(0)
else:
    # Инициализируем первые два члена последовательности и их индекс n.
    # f0 соответствует φ(n-1), f1 соответствует φ(n)
    f0, f1 = 0, 1
    n = 1
    
    # Используем цикл while для генерации чисел Фибоначчи,
    # пока текущее число f1 меньше искомого числа a.
    while f1 < a:
        # Это "магия" Python для параллельного присваивания.
        # Новое значение f0 становится старым f1,
        # а новое f1 становится суммой старых f0 и f1.
        # Это эквивалентно:
        # temp = f1
        # f1 = f0 + f1
        # f0 = temp
        f0, f1 = f1, f0 + f1
        n += 1
        
    # После выхода из цикла проверяем, почему он завершился.
    # Если f1 равно a, значит, мы нашли число.
    if f1 == a:
        print(n)
    # Если f1 стало больше a, значит, мы "проскочили" искомое число,
    # и его нет в последовательности.
    else:
        print(-1)