Problema
I numeri di Lucas seguono la stessa regola dei numeri di Fibonacci (ogni termine è la somma dei due precedenti), ma partono in modo diverso: L(0) = 2 e L(1) = 1. La successione è 2, 1, 3, 4, 7, 11, 18, 29, …
Implementa lucas_numbers(n).
Input
n: l'indice del termine, a partire da 0.
Output
Restituisci L(n).
Vincoli
0 ≤ n ≤ 90
Esempi
Input:
n = 6
Output atteso:
expected = 18
Input:
long long n = 6;
Output atteso:
long long expected = 18;
Input:
long n = 6;
Output atteso:
long expected = 18;
Spiegazione
I termini sono 2, 1, 3, 4, 7, 11, 18, quindi L(6) = 18.
Input:
n = 0
Output atteso:
expected = 2
Input:
long long n = 0;
Output atteso:
long long expected = 2;
Input:
long n = 0;
Output atteso:
long expected = 2;
Spiegazione
La successione inizia con L(0) = 2.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Tieni il termine corrente e il successivo in due variabili.
Suggerimento 2
L'unica differenza rispetto a Fibonacci sono i valori iniziali: 2 e 1.
Suggerimento 3
Per n = 90 il termine successivo non starebbe in 64 bit, quindi ferma il ciclo a n.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.