0423 - Termeni Fibonacci mai mici ca un numar

Cerința

Se consideră şirul Fibonacci, definit astfel: $f1=1,f2=1,fn=fn-1+fn-2$, dacă n > 2. Se dă un număr natural n. Să se afişeze în ordine crescătoare, termenii şirului lui Fibonacci mai mici sau egali cu n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul afișează pe ecran termenii şirului lui Fibonacci mai mici sau egali cu n, în ordine crescătoare, separați printr-un spaţiu.

Restricții și precizări

1 ≤ n ≤ 500.000.000

Exemplul 1

Intrare

40

Ieșire

Datele introduse corespund restricțiilor impuse.

1 1 2 3 5 8 13 21 34

Exemplul 2

Intrare

0

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#0423 - Termeni Fibonacci mai mici ca un numar
def fibonacci(n):
    # inițializăm primii doi termeni ai șirului Fibonacci
    fib = [1, 1]
    # generăm șirul Fibonacci până când ultimul termen este mai mare decât n
    while fib[-1] <= n:
        fib.append(fib[-1] + fib[-2])
    # returnăm toți termenii șirului, mai mici sau egali cu n
    return fib[:-1]

if __name__ == "__main__":
    # citim numărul n de la tastatură
    n = int(input("Introduceți n: "))
    # verificăm dacă n este în intervalul [1, 500.000.000]
    if n >= 1 and n <= 500_000_000:
        print("Datele de intrare corespund restricțiilor impuse.")
        print("Termenii șirului lui Fibonacci mai mici sau egali cu", n, "sunt:", end=" ")
        for termen in fibonacci(n):
            print(termen, end=" ")
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")