2votos

Problema de las Olimpiadas rusas en C

por josejuan hace 6 años

Ésta es eficiente (no como las anteriores XD XD), el único inconveniente es que la serie que enumera la cantidad de dígitos no es reducible (no hay una ecuación explícita) y hay que iterarla, por lo demás, se podría obtener una fórmula explícita.

Calcular el elemento n-ésimo de la sucesión 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, ...

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
/* la versión "gore" quedaría así: 
 
int digitoRuso(int N) { 
    int g,p,a,b; 
    g=p=a=1; 
    while(1) { if(N < (b=a+9*p*g)) break; a=b; p*= 10; g++; } 
    b=N-a; a=b%g; p+=b/g; 
    while(--g>a) p/=10; 
    return p%10; 
 
pero como es un poco especial la "verboseo" abajo. 
*/ 
 
 
 
#include <stdio.h> 
#include <stdlib.h> 
 
int digitoRuso(int N) { 
    // primer paso, buscamos el grupo en el que está el dígito (dentro de los de 1 dígito, de los de 2 dígitos, ...) 
    // esta primera parte, realmente es el cálculo de la serie: 
    // 
    //        9 * sum { 10^(k-1) * k } 
    // 
    // que no tiene expresión directa. 
 
    int g = 1; // número de grupo #1 de un dígito, #2 de dos dígitos, ... 
    int p = 1; // potencias de 10 asociadas a cada grupo, es un símple cálculo recurrente de 10^g 
    int a = 1; // el grupo actual empieza en este dígito 
    while(1) { 
        int b = a + 9 * p * g; // posición del primer dígito del siguiente grupo 
        if(N < b) break; // estamos en el grupo adecuado 
        a = b; 
        p *= 10; // p = 10^g 
        g++; 
 
    // segundo paso, dentro del grupo, buscamos el número en el que está 
    int D = (N - a) / g;    // número de números de 'g' dígitos que hay que saltar para llegar al número 
                // que contiene el dígito N 
    int r = (N - a) % g;    // una vez lo tengamos, será (por la izquierda) el dígito r-ésimo (0, 1, 2, ..., g-1) 
 
    int Q = p + D;        // éste es el número que lo contiene 
 
    // sacamos el dígito 
    while(--g > r) 
        Q /= 10; 
 
    return Q % 10; 
 
void main(int argc, char**argv) { 
    if(argc != 2) 
        fprintf(stderr, "usage: %s digito\n", *argv); 
    else 
        printf("DIGITO: %i\n", digitoRuso(atoi(argv[1]))); 
3 comentarios
0votos

Escrito por isola009 hace 6 años

Será más eficiente, pero es menos mantenible y varios órdenes mayores en tiempo de diseño. :P

Me quedo con la mía en Haskell: Concisa y elegante.
0votos

Escrito por jneira hace 6 años

Pues a mi me parece igual de elegante que la de haskell. Elegante e ingeniosa en el ambito de la programacion de bajo nivel, que es el suyo.
Sin conocer las tripas (y destripar) no puedes volar demasiado lejos.
0votos

Escrito por rchavarriat hace 6 años

Impresionante! Un ejemplo perfecto de cómo se puede optimizar un problema con un poco de matemáticas.
La pega es que no es un algoritmo que quede muy claro en el código, pero como ejercicio merece la pena.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.