2votos

Escalera en C

por josejuan hace 6 años

Cabría fácilmente hacer una versión de suma adhoc que hiciera realmente rápido el algoritmo (que es el mismo), pero es más cómodo usar una librería para ello como GMP. El rendimiento neto (con ser el mismo algoritmo) es bestialmente mejor que mi versión de Haskell.

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h> 
#include <stdlib.h> 
#include <gmp.h> 
 
// NOTA: es una solución adhoc no reutilizable (encapsular al gusto) 
 
mpz_t *m;   // tabla de memoización 0..N 
int k;      // máximo salto de la rana 
 
void escalera(mpz_t res, int N);       // función NO memoizada 
void escalera_mem(mpz_t res, int N);   // función SI memoizada 
 
void escalera(mpz_t res, int N) { 
    mpz_t t, a; 
    mpz_init(t); 
    mpz_init(a); 
    mpz_set_ui(res, 0); 
    int _k = k < N ? k : N; 
    while(_k > 0) { 
        escalera_mem(t, N - _k); 
        mpz_add(a, res, t); 
        mpz_set(res, a); 
        _k--; 
    mpz_clear(t); 
    mpz_clear(a); 
 
void escalera_mem(mpz_t res, int N) { 
    if(mpz_cmp_ui(m[N], 0) == 0) 
        escalera(m[N], N); 
    mpz_set(res, m[N]); 
 
 
int main(int argc, char **argv) { 
 
    if(argc != 3) { 
        fprintf(stderr, "USAGE: %s <N> <k>\n", argv[0]); 
        return 1; 
 
    int N = atoi(argv[1]); 
    k = atoi(argv[2]); 
   m = (mpz_t *) malloc(sizeof(mpz_t) * (N + 1)); 
 
    { // como siempre contiene valores positivos, inicializamos a cero 
        int i; 
        for(i = 0; i <= N; i++) { 
            mpz_init(m[i]); 
            mpz_set_ui(m[i], 0); 
        mpz_set_ui(m[0], 1); 
 
    mpz_t res; 
    mpz_init(res); 
    escalera_mem(res, N); 
 
    gmp_printf ("%Zd\n", res); 
 
    return 0; 
 
/* 
 
Lo que en haskell lleva 1 segundo y 21 megas a la versión en C sólo 0,16 segundos y 7 megas. 
 
La de haskell en 42 segundos y 253 megas lo que la versión en C hace en 10 segundos y 101 megas. 
 
[josejuan@centella solveet]$ time -f "%E, %M" ./a.out 10000 100 > /dev/null  
0:00.16, 7324 
[josejuan@centella solveet]$ time -f "%E, %M" ./a.out 40000 400 > /dev/null  
0:09.77, 101372 
 
Incluso calcular para N = 100.000 y k = 1.000 no toma mucho tiempo, 3 minutos y 625 megas. 
 
[josejuan@centella solveet]$ time -f "%E, %M" ./a.out 100000 1000 > /dev/null  
3:08.20, 625692 
 
*/ 
7 comentarios
0votos

Escrito por Raul GM hace 6 años

Hola, ole con ole!

Que distribución usas? Ubuntu Server parece que no. Llebo un año con el server apagado, pero viéndote a ti le voy a sacar el polvo y me pongo a hacer lo mismo. Lo que yo uso un Pentium 4 con 256MB de RAM y hace nada me llegó por correo un Giga así que triunfante. Para Katas más que sobrao.

Todavía no he mirado la kata a fondo ahora mismo no tengo las tools, pero ya te consultaré las dudas.

Gracias,
0votos

Escrito por josejuan hace 6 años

Archlinux, pero si estás cómodo con Ubuntu no lo cambies, aunque probablemente Arch pudieras tunearlo para aprovechar mejor esa RAM (Ubuntu probablemente tenga servicios que no necesitas).

;)
0votos

Escrito por Raul GM hace 6 años

Hola josejuan... C me cuesta, estoy intentando compilar tu programa y no hay forma. Me imagino que tiene que ver con lo de encapsular al gusto y con mi nivel mierder.

Me sale esto:

D:\Datos\Varios\Solveet\escalera.c:5:18: gmp.h: No such file or directory
D:\Datos\Varios\Solveet\escalera.c:13: error: syntax error before "int"
D:\Datos\Varios\Solveet\escalera.c:19: error: syntax error before "res"
D:\Datos\Varios\Solveet\escalera.c:21: error: syntax error before "res"
D:\Datos\Varios\Solveet\escalera.c:25: error: syntax error before "res"
D:\Datos\Varios\Solveet\escalera.c: In function `escalera':
D:\Datos\Varios\Solveet\escalera.c:27: error: `mpz_t' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:27: error: (Each undeclared identifier is reported only once
D:\Datos\Varios\Solveet\escalera.c:27: error: for each function it appears in.)
D:\Datos\Varios\Solveet\escalera.c:27: error: syntax error before "t"
D:\Datos\Varios\Solveet\escalera.c:29: error: `t' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:31: error: `a' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:33: error: `res' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:35: error: `N' undeclared (first use in this function)

D:\Datos\Varios\Solveet\escalera.c: At top level:
D:\Datos\Varios\Solveet\escalera.c:57: error: syntax error before "res"
D:\Datos\Varios\Solveet\escalera.c: In function `escalera_mem':
D:\Datos\Varios\Solveet\escalera.c:59: error: `N' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:63: error: `res' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c: In function `main':
D:\Datos\Varios\Solveet\escalera.c:89: error: `mpz_t' undeclared (first use in this function)
D:\Datos\Varios\Solveet\escalera.c:89: error: syntax error before ')' token
D:\Datos\Varios\Solveet\escalera.c:111: error: syntax error before "res"
D:\Datos\Varios\Solveet\escalera.c:113: error: `res' undeclared (first use in this function)
0votos

Escrito por josejuan hace 6 años

Ufff... ve más despacio, practica y cuando tengas más soltura vuelve aquí. ;)
0votos

Escrito por Raul GM hace 6 años

Esperaba otra respuesta. Realmente tampoco quería que dieras solución a todo, hay cosas triviales. Sin embargo, que me dieras una idea de porque me falla.

Anyway, me meto a otra cosa mariposa.
0votos

Escrito por josejuan hace 6 años

A veeeeeeeer, el problema es que son tantas las cosas y conceptos que faltan ahí, que no es práctico ni puedo dedicar tanto tiempo como haría falta.

Por ejemplo, es obvio que hace falta tener acceso a la librería GMP, y que el compilador te está diciendo que no tiene acceso a ella, de lo que se deduce que o no te has dado cuenta, o no la has instalado bien, etc...

Vete despacio, que tengo prisa. ;)
0votos

Escrito por Raul GM hace 6 años

Sí en cuanto a lo gmp.h he entendido que no me hacía bien el import. Voy a ver como conseguir la librería y paso a paso iré resolviendo. Lo que pasa es que a veces hay que cambiar el compilador y cosas raras las cuales cada vez que busco eso me pego un tiro antes de encontrar nada.

Es lo que tiene tener nivel mierder.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.