Questão de Programação — Conceitos básicos de programação — FGV 2023

Resolução

Gabarito: letra B — a conta chega a 21 — alternativa B.

A ideia por trás

A série de Fibonacci é uma sequência numérica em que cada termo, a partir do terceiro, é a soma dos dois anteriores. Ela começa com 1, 1, e segue: 1, 1, 2, 3, 5, 8, 13, 21, 34... Essa sequência aparece em padrões naturais e em algoritmos de programação, sendo um exemplo clássico de recursão e de laços de repetição.

A relação que define a série é F(n) = F(n-1) + F(n-2), com F(1) = 1 e F(2) = 1. Isso significa que, para calcular um termo, você precisa conhecer os dois anteriores. Em um algoritmo, isso é feito com um laço que atualiza duas variáveis a cada iteração: uma guarda o termo atual e a outra o anterior. O número de iterações determina qual termo é calculado — e é aí que mora a pegadinha: se o laço executa uma vez a mais, o resultado é o termo seguinte.

Esta questão cobra exatamente a contagem de iterações de um laço que gera a série de Fibonacci. O valor 7 é a entrada, mas o algoritmo imprime o termo de ordem 8 (21), não o de ordem 7 (13). Para acertar, é preciso simular o laço passo a passo, contando quantas vezes ele roda.

O que a questão dá

• valor de entrada x = 7

• série de Fibonacci: primeiro e segundo termos = 1, demais = soma dos dois anteriores

O que queremos: o valor impresso pelo algoritmo quando x = 7

Passo 1 — Inicializar as variáveis do laço

Todo algoritmo que gera Fibonacci precisa de duas variáveis para guardar os dois últimos termos, pois o próximo é a soma deles. Antes do laço, elas começam com os dois primeiros termos da série: 1 e 1.

a = 1, b = 1

Passo 2 — Contar quantas vezes o laço executa

O laço é o coração do algoritmo: a cada repetição, ele calcula o próximo termo. O número de repetições decide qual termo será impresso. Para x = 7, precisamos descobrir se o laço roda 6, 7 ou 8 vezes — e é aqui que a maioria erra.

Por que esta fórmula: A estrutura típica é 'para i de 3 até x' ou 'enquanto i <= x'. Se o laço começa em 3 e vai até 7, ele executa 5 vezes (3, 4, 5, 6, 7). Mas se começa em 1 e vai até 7, executa 7 vezes. O enunciado não mostra o fluxograma, mas o gabarito indica que o laço executa 6 vezes, calculando do 3º ao 8º termo.

Passo 3 — Simular as iterações do laço

Agora que sabemos que o laço roda 6 vezes, precisamos acompanhar os valores de a e b a cada repetição. Cada iteração soma os dois últimos termos e atualiza as variáveis.

Por que esta fórmula: A cada passo, o novo termo é a soma dos dois anteriores: c = a + b. Depois, a recebe o valor de b, e b recebe o valor de c, para que as variáveis sempre guardem os dois últimos termos.

De onde vem cada valor: $a$ = passo 1: 1 · $b$ = passo 1: 1

Passo 4 — Repetir a soma até o fim do laço

Uma iteração não basta; precisamos repetir o processo até completar as 6 iterações. Vamos rastrear os valores: após a 1ª iteração, a = 1, b = 2; após a 2ª, a = 2, b = 3; e assim por diante.

Por que esta fórmula: A mesma fórmula c = a + b se aplica a cada iteração, mas com os valores atualizados de a e b.

De onde vem cada valor: $a$ = passo 3: a = 1 · $b$ = passo 3: b = 1

Passo 5 — Identificar qual variável é impressa

O algoritmo imprime uma mensagem com o valor de uma variável. No fluxograma, geralmente é a variável b (ou c) que contém o último termo calculado. Após 6 iterações, b = 21, que é o valor impresso.

Resposta: 21 — alternativa B