0votos

La sucesión de Golomb en C#

por josejuan hace 6 años

Creo que este problema es difícil, no normal. Además me ha costado entender como se generaba la serie, sugiero mirar en Wolfram para entenderlo.

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
He realizado un par de intentos "directos" pero no eran lo suficientemente rápidos. 
Luego me he fijado que: 
 
* Un número 'n' aparece en la serie, por última vez, en la posición SUM(g(n), 1, n). 
* Un número 'n' aparece en la serie, por primera vez, en la posición SUM(g(n-1), 1, n-1) + 1. 
 
Así, sumando los términos que se van calculando se alcanza mucho antes el objetivo. 
 
En lugar de la forma "tosca" que he usado, supongo que se podrá resolver por recurrencia, 
pero es viernes y estoy cansado... 
 
 
 
class GolombInterval { 
    public int n; 
    public int t; 
    public GolombInterval( int n, int t ) { 
        this.n = n; 
        this.t = t; 
 
static int Golomb( int n ) { 
    if( n == 1 || n == 2 ) 
        return n; 
    var q = new List<GolombInterval>(); 
    q.Add(new GolombInterval(2, 1)); 
    int S = 3; 
    var k = 3; 
    while( S < n ) { 
        S += q [ 0 ].n; 
        q.Add(new GolombInterval(k++, q [ 0 ].n)); 
        if( --( q [ 0 ].t ) <= 0 ) 
            q.RemoveAt(0); 
    return k-1; 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.