1votos

Escalera en Haskell

por josejuan hace 6 años

Pensando un rato en el problema, veo una estrategia de partición que hace al algoritmo con coste lineal O(N), por lo que calcula en milésimas lo que antes calculaba en minutos. Además, me da que podría calcularse más rápidamente, cuando no con coste O(1). Calcula N=100.000 y k=1.000 en menos de 7 segundos (a la versión de C le lleva 3 minutos).

Describe el numero de combinaciones que tiene la rana para subir una escalera (C)

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
47
48
49
50
51
52
53
escalera' :: Integer -> Integer -> Integer 
escalera' n k = g n 
  where g = memoFix $ \f x -> if x == 0 
                              then 1 
                              else 
                                if x <= k 
                                then 2^(x - 1) 
                                else 2 * g (x - 1) - g (x - k - 1) 
 
{-- 
 
La explicación requiere índices, así que los indicaré entre llaves, por ejemplo 
 
    S{n-1},{k-2} 
 
sería el elemento de S con doble subíndice, siendo el primer subínice n-1 y el segundo k-2. 
 
La estrategia utiliza cuatro resultados: 
 
Primero (obvio) 
 
    S{0},{0} = 1 
 
Segundo (obvio), para todo N <= k, es 
 
    S{N},{k} = S{N},{N} 
 
Tercero, para todo N = k, es 
 
    S{N},{k} = S{N},{N} = 2^(N - 1) 
 
podemos verlo desarrollando la sucesión 
 
    S{0},{0} = 1 
    S{1},{1} = S{0},{0} = 2^0 
    S{2},{2} = S{0},{0} + S{1},{1} = 2 S{0},{0} = 2^1 
    S{3},{3} = S{0},{0} + S{1},{1} + S{2},{2} = 2 S{2},{2} = 2^2 
    ... 
 
Cuarto, para todo N > k se cumple la identidad 
 
    S{N},{k} = 2 S{N - 1},{k} - S{N - k - 1}, {k} 
 
que se ve directamente desarrollando los términos S{N},{k} y S{N - 1},{k} pues es 
 
    S{N},{k} = S{N - 1},{k} + S{N - 2},{k} + ... + S{N - k}, {k} 
    S{N - 1},{k} = S{N - 2},{k} + ... + S{N - k}, {k} + S{N - k - 1},{k} 
 
que reemplazando sale la identidad indicada. 
 
En cuanto a la complejidad, está claro que el cuarto resultado indica que se iterará desde N, N-1, N-2, ... hasta k, por lo que se iterará N-k veces la función del cuarto resultado, k veces la del tercer resultado y una vez la del primer resultado. 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.