Introdução à Programação · 1.º ano (indicativo)

Como escrever um programa para a sequência de Fibonacci?

  • 8 min de leitura
  • 4 exemplos resolvidos
  • 5 exercícios com solução
  • Atualizado em

Resposta curta

A sequência de Fibonacci começa em 0 e 1, e cada termo seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, … Em Python, guarde os dois últimos termos em a e b, mostre a em cada volta do ciclo e atualize com a, b = b, a + b.

Quando se aplica

A sequência de Fibonacci é um exemplo clássico de ciclo com estado: cada volta depende dos valores da volta anterior. Serve para treinar atribuições, rastreio de variáveis e condições de paragem (por número de termos ou por valor máximo). Aparece em Matemática (crescimento recursivo) e em muitos exercícios de exame de introdução à programação.

Definição

  • F(0) = 0 e F(1) = 1.
  • F(n) = F(n − 1) + F(n − 2), para n ≥ 2.
  • Primeiros termos: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Algumas fontes começam a sequência em 1, 1, 2, 3, … Confirme a convenção da sua disciplina; este artigo começa em 0.

Pré-requisitos

  • Variáveis, input(), int() e print().
  • Ciclos for com range e while com condição.
  • Atribuição múltipla: a, b = b, a + b calcula o lado direito todo antes de atribuir.

Método passo a passo

  1. Leia quantos termos quer: n = int(input("Quantos termos? ")).
  2. Inicialize os dois primeiros termos: a = 0 e b = 1.
  3. Repita n vezes: for i in range(n):.
  4. Mostre o termo atual a (recuado): print(a).
  5. Avance: a, b = b, a + b (recuado). O novo a é o antigo b, e o novo b é a soma dos dois antigos.
  6. Rastreie com n pequeno para confirmar.

Programa completo

  1. n = int(input("Quantos termos? "))
  2. a = 0
  3. b = 1
  4. for i in range(n):
  5. (recuada) print(a)
  6. (recuada) a, b = b, a + b

Rastreio para n = 7

Voltaa (mostrado)b antes da atualizaçãonovo anovo b
10111
21112
31223
42335
53558
658813
78131321

Os valores mostrados nas 7 voltas são, portanto, 0, 1, 1, 2, 3, 5 e 8.

Exemplos resolvidos

Exemplo 1 — Os primeiros 7 termos

Enunciado: O utilizador escreve n = 7. O que mostra o programa?

Resolução:

  1. Aplique o rastreio da tabela: a toma sucessivamente os valores 0, 1, 1, 2, 3, 5, 8.
  2. Em cada volta, print(a) mostra o valor atual, numa linha.

Resposta: 0, 1, 1, 2, 3, 5, 8 (um número por linha). Verificação: 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5 e 3 + 5 = 8.

Exemplo 2 — Soma dos primeiros 10 termos

Enunciado: Escreva um programa que calcule a soma dos 10 primeiros termos.

Resolução:

  1. Acrescente soma = 0 antes do ciclo e use for i in range(10):.
  2. Dentro do ciclo: soma += a e depois a, b = b, a + b.
  3. Os 10 termos são 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
  4. Soma: 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88.

Resposta: 88. Verificação: existe a propriedade de que a soma dos termos F(0) a F(n) é F(n + 2) − 1; com n = 9, F(11) − 1 = 89 − 1 = 88.

Exemplo 3 — Termos menores que 100 (ciclo while)

Enunciado: Mostre todos os termos menores que 100 e diga quantos são.

Resolução:

  1. a = 0, b = 1 e contador = 0.
  2. while a < 100: com, recuados, print(a), contador += 1 e a, b = b, a + b.
  3. Os termos mostrados são 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
  4. Depois de 89, o novo a é 144, que já não cumpre a < 100.

Resposta: 12 termos, de 0 até 89. Verificação: o termo seguinte, 144, ultrapassa 100.

Exemplo 4 — Nível de exame: o primeiro termo maior que 1000

Enunciado: Escreva um programa que encontre o primeiro termo maior que 1000 e a sua posição (F(0) tem posição 0).

Resolução:

  1. a = 0, b = 1 e posicao = 0.
  2. while a <= 1000: com, recuados, a, b = b, a + b e posicao += 1.
  3. Após o ciclo, print(a, posicao).
  4. Termos: 144 (posição 12), 233 (13), 377 (14), 610 (15), 987 (16), 1597 (17).
  5. 987 ≤ 1000, mas 1597 > 1000, logo o ciclo para com a = 1597.

Resposta: o termo é 1597 e a posição é 17. Verificação: 610 + 987 = 1597.

Erros frequentes

  • Atualizar em duas linhas separadas: a = b seguido de b = a + b. Na segunda linha o a já mudou, e a sequência fica errada (obtém-se 0, 1, 2, 4, 8, …). Use a, b = b, a + b, ou uma variável temporária.
  • Inicializar a e b com valores errados, como a = 1 e b = 1, o que dá a variante 1, 1, 2, … sem o 0 inicial.
  • Errar o número de termos: range(n) dá exatamente n termos. Com range(n + 1) aparecem n + 1.
  • **Esquecer a atualização no while:** a condição a < 100 nunca fica falsa e o programa não termina.
  • **Colocar o print depois da atualização,** o que salta o 0 inicial.
  • **Esquecer o int()** na leitura de n.

Exercícios propostos

Tente resolver primeiro no caderno; depois confira.

1Exercício 1

Escreva os primeiros 5 termos que o programa mostra para n = 5.

Ver solução

a vale 0, 1, 1, 2, 3 nas cinco voltas. Mostra 0, 1, 1, 2, 3.

2Exercício 2

Qual é o décimo termo da sequência (o primeiro, 0, conta como termo 1)?

Ver dica

Continue a lista: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Ver solução

Os 10 primeiros termos são 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. O décimo é 34.

3Exercício 3

Calcule a soma dos 6 primeiros termos e indique como o programa a obteria.

Ver solução

soma = 0; for i in range(6): com soma += a e a, b = b, a + b. Termos: 0, 1, 1, 2, 3, 5; a soma é 12.

4Exercício 4

Quantos termos pares existem entre os termos menores que 100? Escreva a condição que os conta.

Ver dica

Um número é par se a % 2 == 0.

Ver solução

Os termos menores que 100 são 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Os pares são 0, 2, 8 e 34: 4 termos (3 se não contar o zero). Condição no ciclo: if a % 2 == 0: pares += 1.

5Exercício 5

Adapte o programa para uma sequência do tipo Fibonacci que comece com 2 e 5. Quais são os primeiros 5 termos?

Ver solução

Basta inicializar a = 2 e b = 5. Os termos são 2, 5, 2 + 5 = 7, 5 + 7 = 12, 7 + 12 = 19. Mostra 2, 5, 7, 12, 19.

Perguntas frequentes

Quando se usa este método?

Quando cada resultado depende dos dois anteriores e quer gerar a sequência por ordem. O ciclo com a, b = b, a + b gera todos os termos com poucas variáveis e sem repetir cálculos.

Existe um método mais rápido?

Para um termo isolado, existe a fórmula fechada de Binet, mas envolve números irracionais e perde precisão com valores grandes. O ciclo é exato com inteiros e é o que se pede em introdução à programação.

Posso resolver com recursão?

Sim, definindo fib(n) como fib(n - 1) + fib(n - 2), mas a versão ingénua repete muitos cálculos e fica lenta para n grande. Confirme no programa da sua disciplina se a recursão já foi abordada.

Que erros são mais comuns?

Atualizar a e b em linhas separadas, inicializar mal e errar o número de termos. Veja a secção «Erros frequentes».

Resumo

  • Fibonacci: F(0) = 0, F(1) = 1 e F(n) = F(n − 1) + F(n − 2).
  • Duas variáveis, a e b, guardam os dois termos atuais.
  • a, b = b, a + b atualiza as duas ao mesmo tempo.
  • for i in range(n) gera n termos; while a < limite gera os termos abaixo de um valor.
  • Rastreie o programa com uma tabela para detetar erros de atualização.

Onde aprofundar

  • O programa da disciplina de Introdução à Programação da sua instituição — confirme a bibliografia em vigor.
  • A documentação oficial do Python, nas secções sobre for, while e atribuição.
  • O curso CS50 (Harvard), como referência pedagógica, em inglês.

Continue a estudar

1.º ano (indicativo)7 min

Como escrever um programa para o fatorial?

O fatorial de n (n!) é o produto 1 × 2 × … × n, com 0! = 1. Em Python, comece com fat = 1, percorra for i in range(2, n + 1): e multiplique com fat *= i. No fim…

4 exemplos5 exercícios com solução

1.º ano (indicativo)8 min

Como escrever um programa para somar números até zero?

Em Python, use um acumulador total = 0, leia o primeiro número e repita com while n != 0: somando n ao total e lendo o número seguinte dentro do ciclo. O zero funciona…

4 exemplos5 exercícios com solução

1.º ano (indicativo)8 min

Como escrever um programa para a tabuada?

Leia o número com n = int(input()) e percorra os multiplicadores de 1 a 10 com for i in range(1, 11):. Dentro do ciclo, mostre cada linha com print(n, "x", i, "=", n *…

4 exemplos5 exercícios com solução

1.º ano (indicativo)9 min

Qual é a diferença entre while e for?

O for percorre uma sequência ou repete um número de vezes conhecido à partida. O while repete enquanto uma condição for verdadeira, por isso serve quando não se sabe…

4 exemplos5 exercícios com solução

Ver tudo de Introdução à Programação · Capítulo: Estruturas de repetição