0votos

La sucesión de Golomb en C

por josejuan hace 5 años

Aún se puede exprimir un poco más (x20) puesto que los intervalos son contiguos sólo hace falta almacenar una cota. Ahora g(1e12) en 1 segundo.

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
#include <stdio.h> 
#include <stdlib.h> 
 
#define LONG long int 
 
int bs(LONG *i, int a, int b, LONG z) { 
    int m = (a + b) >> 1; 
    if(z <= i[m - 1]) return bs(i, a, m - 1, z); 
    if(z >  i[m    ]) return bs(i, m + 1, b, z); 
    return m; 
 
void main(int argc, char **argv) { 
    int nDIV1e6 = atoi(argv[1]);          // n / 1e6 
    LONG n = nDIV1e6 * 1000000L; 
    int maxI = atoi(argv[2]);       // máx intervalos a generar 
    LONG *i = (LONG *) malloc(sizeof(LONG) * maxI); 
    i[1] = 1; 
    i[2] = 3; 
    int z = 2; 
    while(n > i[z]) { 
        int zz = z + 1; 
        i[zz] = i[z] + bs(i, 1, z, zz); 
        z = zz; 
    printf("%i\n", z); 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.