0votos

Por 3 ó Mas 5 en Haskell

por josejuan hace 4 años

El algoritmo trivial es exponencial O(2^n) pero memoizando el árbol y dado que no se consideran más de n valores se reduce a "casi" O(n).

Encontrar si un numero pueder ser obtenido con solo sumarle 5 a 1 ó multiplicarlo por 3

1
2
3
4
5
6
7
8
import Data.Function.Memoize 
 
search :: Integer -> Bool 
search n = s 1 
  where s z | z == n = True 
            | z >  n = False 
            | z <  n = s' (3 * z) || s' (5 + z) 
        s' = memoize s 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.