Células preenchidas
Adições
Chamadas sem tabela

  • A preencher
  • Lida
  • Resposta

Mais sobre Fibonacci com programação dinâmica

Fibonacci com programação dinâmica

Os números de Fibonacci são o primeiro exemplo clássico de programação dinâmica. A recursão simples pede os mesmos termos vezes sem conta, mas com uma tabela que guarda cada termo o trabalho cresce apenas com n. Escolha um termo, opte pelo método ascendente ou descendente e avance passo a passo para ver cada célula preenchida uma única vez. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Escolha n, o termo a calcular, e o método: Ascendente preenche a tabela a partir da esquerda, Descendente mantém a recursão mas consulta primeiro a tabela, e a linha por baixo da tabela passa a ser a pilha de chamadas em aberto. Novo exemplo escolhe outro n. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escreva n, o termo a calcular, e escolha Ascendente ou Descendente.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
  3. Veja cada célula ler as duas células anteriores. Com Descendente, a linha por baixo da tabela é a pilha de chamadas em aberto.

Ascendente e descendente

O método ascendente (bottom-up), também chamado tabulação, começa com F(0) = 0 e F(1) = 1 e preenche a tabela da esquerda para a direita: cada nova célula é a soma das duas células anteriores. O método descendente (top-down), também chamado memoização, mantém a definição recursiva: para encontrar F(n), pede F(n − 1) e F(n − 2). A diferença em relação à recursão simples é que cada chamada consulta primeiro a tabela e só calcula um termo se a sua célula ainda estiver vazia. Ambos preenchem cada célula uma vez e usam n − 1 adições.

Porque é que a recursão simples é tão lenta

Sem tabela, F(n) chama F(n − 1) e F(n − 2), ambos chamam F(n − 3), e assim por diante: as chamadas formam uma árvore em que os mesmos termos aparecem vezes sem conta. O número de chamadas é 2·F(n + 1) − 1, que cresce tão depressa como os próprios números de Fibonacci: 177 chamadas para F(10), 21 891 para F(20) e mais de 331 milhões para F(40). Subproblemas sobrepostos como estes são exatamente aquilo para que serve a programação dinâmica.

Perguntas frequentes

O que é a programação dinâmica?

Uma forma de resolver um problema dividindo-o em problemas mais pequenos que se sobrepõem, resolvendo cada um apenas uma vez e guardando a sua resposta numa tabela. Os números de Fibonacci são o exemplo mais simples: cada termo é construído a partir dos dois anteriores.

Qual é a diferença entre memoização e tabulação?

A memoização mantém o código recursivo e guarda cada resposta na primeira vez que é calculada, para que as chamadas seguintes apenas a leiam. A tabulação preenche a tabela por uma ordem que garante que cada resposta de que uma célula precisa já lá está. Ambas fazem as mesmas adições; a tabulação evita a pilha de chamadas, e a memoização só calcula as células que são realmente necessárias.

Quantas adições são precisas para F(n)?

n − 1 com uma tabela: uma para cada termo de F(2) a F(n). Só os dois últimos termos são lidos, por isso um programa também pode guardar apenas dois números em vez da tabela inteira.

Porque é que a aplicação para em n = 40?

F(40) = 102 334 155 ainda cabe facilmente no ecrã, e a recursão simples já precisaria de 331 160 281 chamadas para o calcular. Os termos maiores crescem depressa: F(78) é o maior que um número JavaScript guarda com exatidão.

Alguma coisa é enviada para algum lado?

Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor