Slinky "arco-íris"
Problem
Slinky< /strong> — um brinquedo de mola criado em 1943 nos EUA por Richard James No nosso país chamava-se simplesmente Rainbow. Todas as crianças adoravam lançá-la escada abaixo, contando quem a derrubaria.
Normalmente "arco-íris" nas mãos das crianças, descia para o próximo degrau, para o degrau após um ou após 2. (Por exemplo, se o Rainbow foi lançado a partir do 10º degrau, ele poderia parar no 9º, 8º ou 7º. )< br />
Digamos que haja N degraus na escada. Determine o número de "rotas" possíveis Arco-íris do topo da escada até o chão.
Entrada
Um único número é inserido \(0 < N < 31\).
Saída
Imprimir um único número — número de "rotas" Arco-íris.
Exemplos