Médio Rust

Iterador personalizado: números de Fibonacci

Enunciado

Implemente um iterador Fibonacci que gera a sequência de Fibonacci infinita (0, 1, 1, 2, 3, 5, ...). Use-o para coletar os 10 primeiros números em um Vec<u64> e imprimi-los.

Requisitos

  • Crie uma struct Fibonacci com campos para os dois últimos valores.
  • Implemente o trait Iterator para Fibonacci com Item = u64.
  • Use .take(10).collect::<Vec<u64>>() para obter os 10 primeiros.
  • Imprima o vetor resultante.

Código inicial

struct Fibonacci {
    // defina os campos
}

impl Iterator for Fibonacci {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        // implemente
    }
}

fn main() {
    let fib = Fibonacci { /* inicialize */ };
    let primeiros: Vec<u64> = fib.take(10).collect();
    println!("{:?}", primeiros);
}

Saída esperada

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Ver dica

Mantenha dois campos: atual e proximo. No next, retorne atual e atualize os valores. Como é infinita, sempre retorne Some.

Mostrar solução 
struct Fibonacci {
    atual: u64,
    proximo: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { atual: 0, proximo: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let valor = self.atual;
        let novo = self.atual + self.proximo;
        self.atual = self.proximo;
        self.proximo = novo;
        Some(valor)  // sempre Some, pois é infinita
    }
}

fn main() {
    let fib = Fibonacci::new();
    let primeiros: Vec<u64> = fib.take(10).collect();
    println!("{:?}", primeiros);
}

Passo a passo

  1. Definimos a struct Fibonacci com dois campos u64: atual (o valor a ser retornado) e proximo (o próximo da sequência).
  2. O método new inicializa com 0 e 1, os dois primeiros números.
  3. No next, guardamos self.atual em valor, que será retornado.
  4. Calculamos novo = self.atual + self.proximo e avançamos: self.atual recebe self.proximo, e self.proximo recebe novo.
  5. Retornamos Some(valor). Como a sequência é infinita, nunca retornamos None.
  6. No main, criamos o iterador e usamos take(10) para limitar a 10 elementos, depois collect para Vec<u64>.

Por que funciona

O trait Iterator só exige o método next. Ao implementá-lo, ganhamos todos os adaptadores (take, map, filter, etc.) gratuitamente. O iterador é preguiçoso: cada chamada a next calcula o próximo número sob demanda. take(10) cria um novo iterador que para após 10 elementos, e collect consome tudo.

Erros comuns

  • Esquecer de atualizar os campos: se não atualizar self.atual e self.proximo, o iterador retornaria sempre 0. Corrija com as atribuições na ordem correta.
  • Retornar None prematuramente: como a sequência é infinita, não deve haver condição de parada. Se colocar if self.atual > 100 { None }, o take(10) ainda funcionaria, mas o iterador não seria mais infinito.
  • Overflow: após muitos elementos, u64 pode estourar. Para uso finito, não é problema; para infinito, use u128 ou aceite o pânico.

Outra forma de resolver

Usar std::iter::successors para criar a sequência sem struct:

let fib = std::iter::successors(Some((0, 1)), |&(a, b)| Some((b, a + b))).map(|(a, _)| a);
let primeiros: Vec<u64> = fib.take(10).collect();

É preferível quando a lógica é simples e não precisa de estado nomeado.

Saída esperada

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]