Medio · Secuencias
Número de Fibonacci
Imprime el N-ésimo número de Fibonacci: F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). La secuencia que ya viste en los ejemplos del editor — ahora la versión seria, con casos borde y una charla de rendimiento incluida.
En una fraseImprime F(N) con dos variables rodantes en N pasos: F(0) = 0 y F(1) = 1, mientras que la recursión ingenua recalcula los mismos valores un número exponencial de veces.
El problema
Entrada: un entero N (0 ≤ N ≤ 30).
Salida: F(N).
Ejemplos:
| Entrada | Salida |
|---|---|
0 | 0 |
10 | 55 |
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — lleva el par, no la secuencia
Nunca necesitas los Fibonacci anteriores — solo los dos últimos. Mantén a = F(i−1) y b = F(i); cada paso calcula t = a + b y desliza la ventana: a = b; b = t;. Tras N pasos, a es F(N).
Pista 2 — los dos casos base
Con el par arrancando en a = 0, b = 1: cero vueltas del bucle dejan a = 0 (la respuesta de N = 0) y una vuelta da a = 1 (la de N = 1). El bucle resuelve ambos casos base gratis — como en Factorial, la estructura correcta borra los bordes.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
int t = a + b;
a = b;
b = t;
}
cout << a << endl;
return 0;
}La pregunta de seguimiento en entrevistas: la versión recursiva (fib(n) = fib(n−1) + fib(n−2)) es elegante pero recalcula los mismos valores una cantidad exponencial de veces — O(2ⁿ) contra el O(N) de aquí. Arreglarla con memoización es el primer bocado de programación dinámica. Además: F(47) desborda int (ver tipos de datos), por eso el problema para en 30.
Análisis profundo
Por qué funciona
Dos variables llevan toda la secuencia. Guardar un array desperdicia memoria; la recursión ingenua desperdicia tiempo. La idea reutilizable es «solo los dos anteriores».
El coste
Iterativo: O(n) de tiempo y O(1) de espacio. Recursión ingenua: O(2^n); fib(40) tarda un segundo, fib(50) tarda un día.
Dónde falla
- Escribir
fib(n-1) + fib(n-2)directamente es exponencial: es el ejemplo estándar de lo que no hay que hacer. - F(90) supera un entero de 64 bits con signo. Averigua dónde se detiene tu tipo antes de imprimir basura.
Siguiente paso
Ahora, pensamiento a nivel de bits: Representación binaria.
Dos cosas para recordar
- Dos variables llevan toda la secuencia.
- La recursión ingenua de fib es O(2^n): la trampa clásica.
🐞 Esta versión falla: ábrela y pruébala
Una vuelta de más: todo se desplaza un término
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a = 0, b = 1;
for (int i = 0; i <= n; i++) {
int t = a + b;
a = b;
b = t;
}
cout << a << endl;
return 0;
}