Interactive code snippets not yet available for SoH 2.0, see our Status of of School of Haskell 2.0 blog post

Fila do ruback

Para que a solução seja válida, o elemento 1 só pode estar na posição 1 ou 2

  • Se estiver na posição 1, o primeiro elemento está fixo e o número de soluções restantes é: nsol(n - 1)
  • Se estiver na posição 2, o elemento 2 tem que estar na posição 1, então temos dois elementos fixos e o número de soluções restantes é nsol(n - 2)

Logo, nsol(n) = nsol(n - 1) + nsol(n - 2)

Vulgo fib(n + 1)

import Data.List

valid l = all (<= 1) [abs (a - b) | (a, b) <- zip [1..] l]

bruteForce n = length . filter valid . permutations $ [1..n]

nsol 1 = 1
nsol 2 = 2
nsol n = nsol (n - 1) + nsol (n - 2) -- AKA Fibonacci

main = print [(bruteForce n, nsol n) | n <- [1..7]]