0votos

La sucesión de Golomb en C

por josejuan hace 5 años

Efectivamente, una implementación eficiente (en este caso en C) permite calcular g(5e11) en menos de un segundo. Es el mismo algoritmo O(log n) que la versión de Haskell.

Cálculo eficiente de los términos de la sucesión de Golomb: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, ...

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
#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct { long int d, h; } I; 
 
int bs(I *i, int a, int b, long int z) { 
    int m = (a + b) >> 1; 
    if(z < i[m].d) return bs(i, a, m - 1, z); 
    if(z > i[m].h) return bs(i, m + 1, b, z); 
    return m; 
 
void main(int argc, char **argv) { 
    int nDIV1e6 = atoi(argv[1]);          // n / 1e6 
    long int n = nDIV1e6 * 1000000L; 
    int maxI = atoi(argv[2]);       // máx intervalos a generar 
    I *i = (I *) malloc(sizeof(I) * maxI); 
#define SI(I, D, H) i[I].d = D; i[I].h = H; 
    SI(1, 1, 1); 
    SI(2, 2, 3); 
    long int z = 2; 
    while(n > i[z].h) { 
        long int h = i[z].h, zz = z + 1; 
        SI(zz, h + 1, h + bs(i, 1, (int) z, zz)); 
        z = zz; 
    printf("%i\n", z); 
 
 
/* 
 
$ gcc -O3 gs.c 
$ time -f "%E, %M" ./a.out 500000 100000000 
20425336 
0:00.92, 320644 
 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.