0votos

Factorion en Haskell

por josejuan hace 6 años

Esta versión de haskell es muy eficiente, sólo revisa aquellos números que son imágen de la actuación (suma de factoriales de dígitos). Curiosamente, no alcanza la velocidad de la versión de C (posteo luego) ni aunque lo paralelice (es demasiado poco trabajo para sacar ventaja paralelizando).

Sabiendo que no hay factoriones mayores que 2.500.000, encontrarlos a todos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
{-- 
en un AMD Phenom X6 a 2,7: 11 milisegundos 
en un Atom D510 1,6: 52 milisegundos  
--} 
 
import Data.List 
 
isFactorion n = n == (sum.map fact.show) n 
 
-- si hay 7 dígitos, revisamos, no puede tener más 
zom 7 _ sf = if isFactorion sf then [sf] else [] 
 
-- si hemos añadidos de todos los dígitos (0 veces) 
zom _ 10 sf = if isFactorion sf then [sf] else [] 
 
-- del dígito 0 al dígito 9 va revisando grupos 
zom ndt n sf = concatMap (\x -> zom (ndt + x) (n + 1) (sf + x * fn)) [0..lim] 
 where fn = fact' n 
       lim = (if n == 1 || n == 2 then 7 else 6) - ndt 
 
-- forma de obtener el factorial del dígito sin convertir a Int 
fact :: Char -> Int 
fact '0' = 1  
fact '1' = 1  
fact '2' = 2  
fact '3' = 6  
fact '4' = 24  
fact '5' = 120  
fact '6' = 720  
fact '7' = 5040  
fact '8' = 40320  
fact '9' = 362880  
 
fact' :: Int -> Int 
fact' 0 = 1  
fact' 1 = 1  
fact' 2 = 2  
fact' 3 = 6  
fact' 4 = 24  
fact' 5 = 120  
fact' 6 = 720  
fact' 7 = 5040  
fact' 8 = 40320  
fact' 9 = 362880  
 
main = putStrLn $ show $ nub $ zom 0 0 0 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.