Divisiones del círculo

4 Comentarios

1. Haskell

   numeroFormas :: Integer -> Integer numeroFormas n = div (factorial (2*n)) ((factorial n)*(factorial (n+1))) factorial :: Integer -> Integer factorial n = product [1..n]

   1 2 3 4 5

   numeroFormas :: Integer -> Integer numeroFormas n = div (factorial (2*n)) ((factorial n)*(factorial (n+1)))   factorial :: Integer -> Integer factorial n = product [1..n]

   Responder

2. Una mejora notable resulta de mantener acotado el tamaño de los multiplicandos:

   Haskell

   nf :: Integer -> Integer nf n = round $ foldl1' (*) $ zipWith (%) [n + 2..n + n] [2..] {- $ for i in `seq 1 9`; do ( echo ${i}0000; for j in 0 1; do time -f "%e" ./cirdiv $j ${i}0000; done ) 2>&1 | perl -n -e 'chomp;print "$_t"'; echo ""; done n check time1 check time2 10000 6640 0.07 6640 0.02 20000 784 0.35 784 0.10 30000 5600 0.84 5600 0.24 40000 8000 1.58 8000 0.39 50000 6640 2.60 6640 0.63 60000 9600 3.87 9600 0.87 70000 720 5.57 720 1.16 80000 7040 7.66 7040 1.55 90000 3600 10.16 3600 1.90 -}

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   nf :: Integer -> Integer nf n = round $ foldl1' (*) $ zipWith (%) [n + 2..n + n] [2..]   {-   $ for i in `seq 1 9`; do ( echo ${i}0000; for j in 0 1; do time -f "%e" ./cirdiv $j ${i}0000; done ) 2>&1 | perl -n -e 'chomp;print "$_t"'; echo ""; done n      check time1 check time2 10000  6640  0.07  6640  0.02   20000  784   0.35  784   0.10   30000  5600  0.84  5600  0.24   40000  8000  1.58  8000  0.39   50000  6640  2.60  6640  0.63   60000  9600  3.87  9600  0.87   70000  720   5.57  720   1.16   80000  7040  7.66  7040  1.55   90000  3600  10.16 3600  1.90   -}

   Responder

3. Haskell

   numeroFormas :: Integer -> Integer numeroFormas n = aux ! n where aux :: Array Integer Integer aux = array (0,n) [(i,f i) | i <- [0..n]] where f 0 = 1 f 1 = 1 f i = sum [ aux ! k * aux ! (i-k-1) | k <- [0..i-1]]

   1 2 3 4 5 6 7

   numeroFormas :: Integer -> Integer numeroFormas n = aux ! n   where aux :: Array Integer Integer         aux = array (0,n) [(i,f i) | i <- [0..n]]           where f 0 = 1                 f 1 = 1                 f i = sum [ aux ! k * aux ! (i-k-1) | k <- [0..i-1]]

   Responder

4. Haskell

   numeroFormas2 :: Integer -> Integer numeroFormas2 0 = 1 numeroFormas2 1 = 1 numeroFormas2 2 = 2 numeroFormas2 n = sum [(numeroFormas (div a 2))*(numeroFormas (div (2*n-a-2) 2)) | a <- (pares (2*n))] pares n = [ x | x <- [0..(n-1)] ,even x]

   1 2 3 4 5 6 7 8

   numeroFormas2 :: Integer -> Integer numeroFormas2 0 = 1 numeroFormas2 1 = 1 numeroFormas2 2 = 2 numeroFormas2 n = sum [(numeroFormas (div a 2))*(numeroFormas (div (2*n-a-2) 2))                       | a <- (pares (2*n))]   pares n = [ x | x <- [0..(n-1)] ,even x]

   Responder