Problema
La successione di Fibonacci inizia con F(1) = 1, F(2) = 1, e ogni termine successivo è la somma dei due precedenti: 1, 1, 2, 3, 5, 8, 13, 21, ... Trova il punto in cui la successione raggiunge per la prima volta n cifre decimali. I termini superano presto gli interi a 64 bit, quindi, se il tuo linguaggio non ha interi grandi, sommali come array di cifre.
Implementa fibonacci_with_n_digits(n).
Input
n: il numero di cifre.
Output
Restituisci l'indice i del primo termine F(i) con almeno n cifre. Per n = 1 la risposta è 1.
Vincoli
1 ≤ n ≤ 1000
Esempi
Input:
n = 2
Output atteso:
expected = 7
Input:
long long n = 2;
Output atteso:
long long expected = 7;
Input:
long n = 2;
Output atteso:
long expected = 7;
Spiegazione
F(6) = 8 ha una cifra e F(7) = 13 ne ha due, quindi la risposta è 7.
Input:
n = 4
Output atteso:
expected = 17
Input:
long long n = 4;
Output atteso:
long long expected = 17;
Input:
long n = 4;
Output atteso:
long expected = 17;
Spiegazione
F(16) = 987 e F(17) = 1597, quindi la risposta è 17.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Tieni solo gli ultimi due termini.
Suggerimento 2
Memorizza ogni termine come cifre e sommali con i riporti.
Suggerimento 3
Conta l'indice man mano, partendo da F(1) = 1.
Complessità attesa
tempo O(n²), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.