0votos

Escalera en Haskell

por josejuan hace 6 años

Se refuerza mi hipótesis de que existe una expresión única para el cálculo del problema. En esta solución doy una expresión O(1) para n <= 2k+1 y queda indicada que existe una expresión para n <= qk+1 para cualquier q. Por tanto, puede calcularse la expresión con coste constante (realmente el coste no es constante debido al coste de las operaciones con precisión arbitraria que no son constantes).

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
escalera' :: Integer -> Integer -> Integer 
escalera' n k = 
  if n <= k 
  then 2^(n - 1) 
  else 
    if n <= 2 * k + 1 
    then 2^(k + i - 1) - ((i + 1) * 2^(i - 1)) `div` 2 
    else 0 -- habría que seguir con el desarrollo 
  where i = n - k 
 
{-- 
 
Por ejemplo, calcula en menos de dos segundos para N = 100.000.000 y k = 54.000.000 
 
*Main> escalera' 100000000 54000000 `mod` 10^10 
9582777344 
(1.94 secs, 350642072 bytes) 
 
 
La "explicación" sería algo como: 
 
Sabemos de forma trivial que es 
 
    S{n, k} = 2^(n - 1)         para todo n <= k 
 
Por otro lado, desarrollando los términos S{k+i, k} para i = 1, 2, 3, ... tenemos 
 
    S{k + 1, k} = 2^k - 1 
    S{k + 2, k} = 2^k - 1 + 2^k - 2 = 2^(k + 1) - 3 
    S{k + 3, k} = 2^(k + 1) + 2^k - 2 + 2^k - 4 - 2 = 2^(k + 2) - 8 
    S{k + 4, k} = 2^(k + 1) + 2^(k + 2) - 4 + 2^k - 4 + 2^k - 8 - 4 = 2^(k + 3) - 20 
 
con un poco de vista, se ve que la sucesión 1, 3, 8, 20, ... corresponde con A001792 y la expresión general queda 
 
    S{k + i, k} = 2^(k + i - 1) - (i + 1) * 2^(i - 2) 
 
Se puede ver que esta segunda expresión S{k + i, k} es un caso más general de la primera S{n, k} teniendo en cuenta que los exponentes negativos van a cero. 
 
La segunda expresión es válida para n <= 2 * k + 1 (momento en que aparecen términos del siguiente desarollo). 
 
*** PROBABLEMENTE *** desarrollando otra vez para S{2 * k + i, k} y luego para S{4 * k + i, k} encontraremos una expresión general que las incluya todas. 
 
En la implementación de haskell hay dos cuestiones: 
 
1. no se usa la expresión general porque es más sencillo que verificar exponente negativo. 
 
2. en la expresión S{k + i, k} aparece el operador `div` porque ese exponente aparece negativo en los primeros términos y así es más sencillo. 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.