0votos

Capicúa con muchos saltos en C

por josejuan hace 4 años

La única optimización asintótica es eliminar del cálculo aquellos números cuyo recíproco es menor que él mismo. Por lo demás, mucho mejor usar aritmética decimal para no tener que convertir de base 2 a 10. En unos 10 minutos se obtiene que el número buscado es el 1.005.499.526 que genera el palíndromo 6633...3366

Buscar el "número capicúa" (según la definición de Antonio Medina) más pequeño, tal que hagan falta más de 100 saltos para estabilizarlo (y quede estabilizado, no sirve el 196 que no estabiliza nunca).

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
void print(int digits, char *digit) { 
    int i = digits - 1; 
    while (i > 0 && digit[i] == 0) i--; 
    while (i >= 0) { putchar('0' + digit[i]); i--; } 
    printf("\n"); 
 
int main(int argc, char **argv) { 
 
    long long int N, maxN; 
    int inc, digits, maxSums, search4; 
 
    N = strtoll(argv[1], NULL, 0);            // from number 
    inc = atoi(argv[2]);                    // increment step (N, N + inc, N + 2 * inc, N + 3 * inc, ...) 
    maxN = strtoll(argv[3], NULL, 0);        // to number 
    digits = atoi(argv[4]);                    // max possible digits growing numbers 
    maxSums = atoi(argv[5]);                // max jumps to check (discard number if jump more than that) 
    search4 = atoi(argv[6]);                // search for *FIRST* number stopping with *MORE* than this jump number 
 
    char *digit; 
    char buffer[200]; 
 
    digit = (char *) malloc(sizeof(char) * digits); 
 
    // precomputed (digit + digit + carry) `divMod` Base 
    char sD [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    char sC [] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; 
 
    { // set digits to 0 
        int i; 
        for (i = 0; i < digits; i++) 
            digit[i] = 0; 
 
    while (N <= maxN) { 
 
        sprintf(buffer, "%lld", N); 
 
        int maxIndex = strlen(buffer) - 1; 
 
        // is precomputed if (flip A) < A  --> Eg. 90341 is equal to 14309 then no recomputation is needed 
        char skip = 0; 
        if (buffer[maxIndex] > '0') { 
            int fromMax = maxIndex, fromMin = 0; 
            while (fromMax >= 0) { 
                if (buffer[fromMax] > buffer[fromMin]) { 
                    break; 
                else { 
                    if (buffer[fromMax] < buffer[fromMin]) { 
                        skip = 1; 
                        break; 
                    else { 
                        fromMax--; 
                        fromMin++; 
 
        if (skip) { 
            if (search4 == 0) 
                printf("N: %lld, already computed!\n", N); 
        else { 
 
            { // copy digits 
                int i; 
                for (i = 0; i <= maxIndex; i++) 
                    digit[maxIndex - i] = buffer[i] - '0'; 
 
            char capi = 0; 
            int jumps = 0, sums = 0; 
            while (!capi && sums++ < maxSums) { 
                jumps++; 
                    // add from max and from min >>> ... <<< 
                    int fromMax = maxIndex, fromMin = 0; 
                    char carryMin = 0; 
                    while (fromMax >= fromMin) { 
                        char ss = digit[fromMax] + digit[fromMin]; 
                        digit[fromMax] = ss; 
                        ss += carryMin; 
                        carryMin = sC[ss]; 
                        digit[fromMin] = sD[ss]; 
                        fromMax--; 
                        fromMin++; 
                    // adjust fromMax carries 
                    while (fromMin <= maxIndex) { 
                        char ss = digit[fromMin] + carryMin; 
                        digit[fromMin] = sD[ss]; 
                        carryMin = sC[ss]; 
                        fromMin++; 
                    // if overflow grow used digits 
                    if (carryMin > 0) { 
                        maxIndex++; 
                        digit[maxIndex] = carryMin; 
                { // palindrome? 
                    capi = 1; 
                    int fromMax = maxIndex, fromMin = 0; 
                    while (fromMax >= fromMin) { 
                        if (digit[fromMax] != digit[fromMin]) { 
                            capi = 0; 
                            break; 
                        fromMax--; 
                        fromMin++; 
            if (capi == 0) { 
                if (search4 == 0) 
                    printf("N: %lld, not found! (maxIndex := %i)\n", N, maxIndex); 
            else { 
                if (search4 == 0 || jumps > search4) { 
                    printf("N: %lld, J: %i, C: ", N, jumps); 
                    print(digits, digit); 
                    if (search4 > 0 && jumps > search4) 
                        exit(0); 
            { // reset used digits 
                int i; 
                for (i = 0; i <= maxIndex; i++) 
                    digit[i] = 0; 
 
 
        N += inc; 
 
    return 0; 
 
 
 
/* 
 
    Para lanzar en paralelo múltiples instancias simplemente cada una se encarga de los 
    números, módulo CPUs. 
 
    Por ejemplo en un BAT: 
 
    @ECHO OFF 
    SET FROM_DIV_10=%1 
    SET NUMPROCS=%2 
    SET TO_NUMBER=%3 
    SET MAX_DIGITS=%4 
    SET MAX_JUMPS=%5 
    SET SEARCH_FOR=%6 
    FOR /L %%i IN (1, 1, %NUMPROCS%) DO ( 
        ECHO Launching process %%i 
        START /LOW cmd.exe /c \ 
            "timeit capic.exe %FROM_DIV_10%%%i %NUMPROCS% %TO_NUMBER% %MAX_DIGITS% %MAX_JUMPS% %SEARCH_FOR% > Out%%i.txt 2>&1" 
 
    Usando un In 
2 comentarios
0votos

Escrito por Homero hace 4 años

ay! me duelen los ojos.
http://es.wikipedia.org/wiki/Modularidad_%28inform%C3%A1tica%29
0votos

Escrito por josejuan hace 4 años

Para mí no tiene ningún sentido modularizar nada aquí, siempre en mi opinión, sería overkill.

De todos modos, si aportas tu solución me resultará más fácil entender a que te refieres.

Un saludo.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.