Mensajes

Totalmente de acuerdo con lo que has dicho, aunque yo iría más lejos e incluso diría que para programar en C/C++ lo ideal es usar Linux. Yo por ejemplo uso Kate como editor y compilo en la terminal con el g++.

Antes no había leído que eran tres números. Ignora pues la parte de mi mensaje anterior donde hacía referencia a la solución para una cantidad arbitraria de números. Ya que tu problema es más sencillo, te dejo un código que he picado ahora para el caso general, suponiendo que los operadores son + o -, por si te interesa el tema para mirarlo.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

void imprime(vector<int>& v, int x) {
    for (int i = 0; i < v.size(); ++i) {
        if ((x >> i)&1) cout << "+";
        else cout << "-";
        cout << v[i];
    }
    cout << endl;
}

int main() {
    //Cantidad de numeros, resultado
    int n, m;
    cin >> n >> m;
   
    //Lectura de los numeros
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
   
    //Solucion
    for (int i = 0; i < (1 << n); ++i) {
        int res = 0;
        for (int j = 0; j < n; ++j) {
            if ((i >> j)&1) res += v[j];
            else res -= v[j];
        }
        if (res == m) imprime(v, i);
    }
}

Es equivalente a una solución por backtracking, sólo que lo he hecho iterativo mediante máscaras de bits puesto que es mucho más corto y simple el código.

Si la cantidad de números puede ser arbitraria, tienes que hacer un backtracking. Si la cantidad de números es fija, puedes simular el backtracking a base de bucles. En todo caso, si tienes n números, la complejidad resultante es O(2ⁿ).

Puedes también hacer una dinámica, si los números y el resultado están acotados será mucho más eficiente.

Respecto a lo de elevar a exponentes reales, si soy sincero no me lo había planteado y no sé la mejor manera de hacerlo. Si tuviera que programarlo ahora lo haría en términos de la definición usando variable compleja de la potencia, que es términos de la exponencial y del logaritmo y que por tanto implican (sin usar esas dos funciones) series de Taylor. Pero si tienes 14 años, entrar en series de Taylor puede ser algo duro, necesitarías probablemente mucha base matemática de cosas que no conoces.

Respecto a lo que comenta Ferno, no sé por qué dices que está mal. Es lo mismo hacer

Código (cpp) [Seleccionar] Expandir

for (int i = 1; i < n; ++i)
que

Código (cpp) [Seleccionar] Expandir

for (int i = 1; i < n; i++)

El postincremento difiere del preincremento si se usa combinándolo con algo más, si no el resultado es equivalente. Como prueba simplemente hace falta considerar el siguiente código:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

int factorial1(int n) { // Version iterativa
    int result = 1;
    for (int i = 2; i <= n; ++i) result *= i;
    return result;
}

int factorial2(int n) { // Version iterativa
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

int main() {
    int n;
    while (cin >> n) cout << factorial1(n) << " " << factorial2(n) << endl;
}
Por ejemplo, la entrada

Código [Seleccionar] Expandir

0
1
2
3
4
5
6
7
8

Produce la siguiente salida:

Código [Seleccionar] Expandir

1 1
1 1
2 2
6 6
24 24
120 120
720 720
5040 5040
40320 40320

Minimax lo que hace informalmente es considerar todos los casos que se pueden dar desde donde estás y en base a esto, elegir el movimiento que te lleve a un resultado mejor asumiendo que el contrario hará el movimiento que más te perjudique.

El problema de minimax es que el árbol de estados que crea es muy grande para juegos más complejos, pero con el 3 en raya hay pocos y lo puede calcular entero, de manera que el ordenador juega de forma perfecta, por eso he programado un minimax.

A la hora de programarlo no es complicado, es un pequeño backtracking. La idea es probar todos tus posibles movimientos y recursivamente hacer que haga lo mismo tu rival. En función de lo que retorne tu rival, elegirás la opción que mejor te vaya.

Si se deja acabar minimax, la jugada es perfecta. El problema es que no todos los juegos como ya he dicho lo permiten (puesto que necesitaría demasiado tiempo, por ejemplo con el ajedrez) y lo que se hace cuando se usa minimax en estos juegos es realizar diferentes tipos de podas para así conseguir un movimiento suficientemente bueno.

[ganar]

Esta tarde con un amigo ha salido el tema por cosas de la conversación y le he desafiado a ganar al 3 en raya (Tic-tac-toe) a una IA que hiciera para el ordenador. Tras unos 15 minutos, os dejo el código que he hecho, puesto que considero que puede ser interesante la parte del minimax para aquellos que no hayan hecho nunca uno. Los gráficos son cutres y por consola, puesto que no era el objetivo del programa hacer una interfaz bonita.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int M[3][3];


int fila[] = {0, 2, 2, 2, 1, 1, 1, 0, 0, 0};
int col[] = {0, 0, 1, 2, 0, 1, 2, 0, 1, 2};

int incf[] = {0, 1, 1, -1};
int incc[] = {1, 1, 0, 1};

int check() {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int d = 0; d < 4; ++d) {
                string s;
                int f = i, c = j;
                for (int h = 0; h < 3; ++h) {
                    if (f < 0 or f >= 3 or c < 0 or c >= 3) break;
                    s += char(M[f][c] + '0');
                    f += incf[d];
                    c += incc[d];
                }
                if (s == "111") return 1;
                else if (s == "222") return 2;
            }
        }
    }
    return -1;
}

void draw() {
    for (int i = 0; i < 50; ++i) cout << endl;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (M[i][j] == 0) cout << "  ";
            else if (M[i][j] == 1) cout << " X";
            else cout << " O";
            if (j != 2) cout << " |";
        }
        cout << endl;
        if (i != 2) cout << "------------" << endl;
    }
}

int rec(int &x, int &y, int torn) {
    int best = -2;
    int z, t;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (M[i][j] != 0) continue;
            M[i][j] = torn;
            if (check() == torn) {
                x = i;
                y = j;
                M[i][j] = 0;
                return 1;
            }
            int aux = rec(z, t, (torn == 1)?2:1);
            if (aux == -2 or aux == 0) {
                if (best < 0) {
                    best = 0;
                    x = i;
                    y = j;
                }
            }
            else if (aux == -1) {
                if (best < 1) {
                    best = 1;
                    x = i;
                    y = j;
                    M[i][j] = 0;
                    return best;
                }
            }
            else if (aux == 1) {
                if (best < -1) {
                    best = -1;
                    x = i;
                    y = j;
                }
            }
            M[i][j] = 0;
        }
    }
    return best;
}

void tira_pc() {
    int x, y;
    int aux = rec(x, y, 1);
    M[x][y] = 1;
}

void tira_jug() {
    int pos = -1;
    while (pos < 1) {
        cin >> pos;
        if (pos < 1 or pos > 9) pos = -1;
        else if (M[fila[pos]][col[pos]] != 0) pos = -1;
    }
    M[fila[pos]][col[pos]] = 2;
}

int main() {
    memset(M, 0, sizeof(M));
    int win = -1, torn = 0;
    int qtt = 0;
    draw();
    while ((win = check()) < 0 and qtt < 9) {
        if (torn == 1) tira_pc();
        else tira_jug();
        torn = 1 - torn;
        draw();
        ++qtt;
    }
    if (win == 1) cout << "Gana el ordenador" << endl;
    else if (win == 2) cout << "Ganas tu" << endl;
    else cout << "Empate" << endl;
}

Se juega con los números:
7 8 9
4 5 6
1 2 3

El ordenador juega con X, el jugador humano con O. Empieza jugando el humano, aunque todo esto son detalles que se arreglan cambiando una o dos líneas.

Como veo que no hay dudas ni preguntas, pongo mi solución del problema planteado para dejar el tema acabado.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <set>
#include <string.h>
using namespace std;

int nimber[105][3][3];

int grundy(int n, int a, int b) {
    if (n == 0) return 0;
    if (n == 1) {
        if (not (a + b == 3)) return 1;
        return 0;
    }
    if (nimber[n][a][b] == -1) {
        set<int> A;
        for (int i = 1; i < n - 1; ++i) {
            A.insert(grundy(i, a, 1)^grundy(n - i - 1, 1, b));
            A.insert(grundy(i, a, 2)^grundy(n - i - 1, 2, b));
        }
        if (a != 1) A.insert(grundy(n - 1, 1, b));
        if (a != 2) A.insert(grundy(n - 1, 2, b));
        if (b != 1) A.insert(grundy(n - 1, a, 1));
        if (b != 2) A.insert(grundy(n - 1, a, 2));
        nimber[n][a][b] = 0;
        while (A.count(nimber[n][a][b])) ++nimber[n][a][b];
    }
    return nimber[n][a][b];
}

int main() {
    memset(nimber, -1, sizeof(nimber));
    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        int ant = 0, res = 0, qtt = 0, turno = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'X') {
                res ^= grundy(qtt, ant, 1);
                ant = 1;
                qtt = 0;
                ++turno;
            }
            else if (s[i] == 'O') {
                res ^= grundy(qtt, ant, 2);
                ant = 2;
                qtt = 0;
                ++turno;
            }
            else ++qtt;
        }
        res ^= grundy(qtt, ant, 0);
        if (turno&1) cout << ((res == 0)?"Possible.":"Impossible.") << endl;
        else cout << ((res != 0)?"Possible.":"Impossible.") << endl;
    }
}

No me refería a no usar funciones. Cuando he puesto pocas me refería a cosas del estilo a que no se piensa en temas de portabilidad, reutilización y otras cosas de estas que predica la Ingeniería del Software. Las funciones se suelen usar cuando son útiles para el código: se hace más corto usándola, más sencillo, más natural, etc.

Simplemente me refería a que si en algunos casos es indiferente, como por ejemplo en el código de este problema, suele ser habitual comerse la función.

A raíz del tema que se habló sobre algoritmia, he escrito este pequeño artículo sobre un tema que considero bastante interesante. Espero que se entienda bien y a ver si sirve para interesar a gente en temas algorítmicos.

En este artículo voy a presentar lo que se conoce como nimbers o números de Grundy. El nombre nimber viene del juego del Nim, que será el primero que analizaremos. No incluiré demostraciones de los resultados que vaya poniendo, dado que no creo que muchos lectores estén familiarizados con demostraciones matemáticas y éste no pretende ser un texto técnico, sino más bien divulgativo.

Presentemos ahora el juego clásico del Nim de una pila. Se trata de un juego para dos jugadores muy tonto. Consideremos una pila con n piedras en que los jugadores van por turnos alternos. Cada turno, el jugador puede retirar una cantidad arbitraria de piedras (como mínimo una y como máximo las que queden). Cuando un jugador no puede hacer nada (no quedan piedras) pierde y el otro gana. El objetivo es dictaminar quién ganará si ambos juegan de forma óptima. En este caso es evidente: gana siempre el primer jugador excepto si hay 0 piedras inicialmente. Si hay alguna piedra, la jugada óptima consiste en retirar todas las piedras, dejando 0 al segundo, que perderá.

Si bien ese caso es muy tonto, presentemos el juego del Nim estándar. Consideremos ahora n pilas diferentes, donde la i-ésima tiene a_i piedras. El juego sigue siendo por turnos para dos jugadores. En cada turno, un jugador tiene que escoger una pila que aún tenga piedras y retirar una cantidad de piedras de ella (entre 1 y la cantidad total de la pila). Si no quedan piedras, el jugador pierde. Otra vez el objetivo será estudiar quién gana en caso de que ambos jueguen óptimamente.

Teorema: Consideremos un juego del Nim con n pilas diferentes, donde la i-ésima tiene a_i piedras. Jugando óptimamente ambos jugadores, el segundo jugador ganará si y sólo si a₁^a₂^...^a_n = 0, donde ^ denota la XOR bit a bit.

Corolario: Para el caso n = 2, el segundo jugador ganará si y sólo si ambas pilas tienen la misma cantidad de piedras. La estrategia óptima consiste en imitar lo que haga el jugador en el turno anterior en la pila contraria, para mantener siempre la misma cantidad en ambas pilas.

Si bien este resultado es interesante, esto puede generalizarse a otros juegos. Consideremos un juego finito por turnos donde cada jugador puede hacer los mismos movimientos y el jugador que no puede mover pierde. Por ejemplo, el ajedrez no entra en esta categoría dado que ambos jugadores no pueden hacer los mismos movimientos (cada uno mueve sólo sus fichas). Para analizar este tipo de juegos definiremos el nimber o número de Grundy de un cierto estado del juego. Para empezar, asignamos al estado en que no se puede tirar (el jugador pierde) el nimber 0.

Definición: Sea J un juego que cumple las condiciones anteriores y w un estado de ese juego. Sea W el conjunto de estados a los que se puede llegar desde w usando un sólo movimiento (es decir, un solo turno). Consideremos el nimber de cada estado de W. Se define el nimber de w como el menor número entero no negativo que no está entre esos nimbers.

Teorema: Sea J un juego que cumple las condiciones anteriores y w un estado de ese juego. Suponiendo que ambos jugadores juegan óptimamente jugando desde w, el primer jugador ganará si y sólo si el nimber de w es diferente de 0.

Considerémos ahora el siguiente juego de ejemplo. Consideremos un juego con una pila con n piedras (como en el Nim), pero en este caso cada turno se pueden retirar 1 ó 2 piedras como mucho (si las hay). Calculemos el nimber para cada n:

- Si n = 0, por definición el nimber es 0.
- Si n = 1, con un turno sólo podemos llegar a n = 0, con nimber 0. El menor entero no negativo al que no se puede llegar es 1, luego 1 es el nimber de n = 1.
- Si n = 2, con un turno se puede llegar a n = 0 y n = 1, con nimbers 0 y 1 respectivamente, luego el nimber de n = 2 es 2.
- Si n = 3, con un turno se puede llegar n = 1 y n = 2, con nimbers 1 y 2 respectivamente. En este caso el menor nimber al que no se llega es el 0, luego el nimber de n = 3 es 0 y es un estado perdedor.

Si se sigue calculando, se ve que la secuencia de nimbers es 0, 1, 2, 0, 1, 2, 0, 1, 2... en la que el patrón es evidente, dado que el juego es muy simple.

Sin embargo, ¿qué pasa si en vez de un juego tenemos dos o más? Pues que el nimber también se puede calcular igual. Supongamos que tenemos un juego J formado por varios juegos J₁, J₂, ..., J_n en que cada turno el jugador elige uno de los juegos y hace un movimiento. En este caso un estado w está formado por los subestados w₁, w₂, ..., w_n de cada uno de los juegos.

Teorema: En el caso anterior, si N(w_i) denota el nimber del i-ésimo subestado, el nimber de w es N(w₁)^N(w₂)^...^N(w_n).

Por ejemplo, consideremos un juego en el que se tiene una circumferencia y sobre ella n puntos distintos. En cada turno, el jugador debe unir dos puntos distintos por un segmento, de forma que no se cruce con ninguno que se haya hecho anteriormente y sin usar un punto más de una vez. En este juego, es fácil ver con un pequeño dibujo que si se unen dos puntos consecutivos, se obtiene el mismo juego con n - 2 puntos. En caso contrario, se obtienen dos juegos diferentes (porque los segmentos no pueden cruzarse): uno tendrá k puntos y el otro n - k - 2. Sin embargo, podemos calcular el nimber de un estado usando el teorema anterior. Pongo un pequeño código en C++ que dada una k calcula el nimber de los juegos para todo n <= k, si no he cometido ningún error:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int grundy(int n, vector<int>& nimber) {
    if (n == 0 or n == 1) return 0; //No hay movimientos posibles
    if (nimber[n] == -1) {
        set<int> A; //Guardare aqui los nimbers a los que se puede llegar
       
        //Itero sobre la cantidad de puntos que dejo en el primer subjuego
        for (int i = 0; i <= n - 2; ++i) A.insert(grundy(i, nimber)^grundy(n - i - 2, nimber));
       
        //Busco el primero que no este, empezando por 0
        nimber[n] = 0;
        while (A.count(nimber[n])) ++nimber[n];
    }
    return nimber[n];
}

int main() {
    int k;
    cin >> k;
    vector<int> nimber(k + 1, -1);
    for (int i = 0; i <= k; ++i) cout << "N[" << i << "] = " << grundy(i, nimber) << endl;
}

Como ejercicio para practicar, probad de hacer este problema de la UVa (podéis enviarlo para su corrección automática, es un juez online):
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2529

En los comentarios no estoy del todo de acuerdo según qué busque. Si es un entreno para concursos de programación, hay muchos de esos consejos que no se suelen utilizar.

Por ejemplo, rara vez se hacen comentarios, las variables suelen tener nombres cortos poco descriptivos (para otros programadores que lo lean al menos) y a veces se usan pocas funciones. Especialmente en los nombres de las variables, yo que participo a menudo suelo utilizar para casi todo nombres de como mucho unas cinco letras, ya que se tarda menos en escribirlo y en estos concursos la velocidad es importante. Además, aunque para otros sean poco descriptivos, son nombres genéricos que utilizo siempre para los mismos conceptos y por lo tanto para mí son descriptivos.

Pongo una solución que he hecho para el problema y que me ha dado Accepted en Live Archive. La he hecho como si estuviera haciendo un concurso y he tardado menos de cinco minutos:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string c = "0123456789ABCDEF";

int main() {
    int n;
    while (cin >> n and n > 0) {
        vector<int> base;
        for (int i = 2; i <= 16; ++i) {
            string s;
            int x = n;
            while (x > 0) {
                s += c[x%i];
                x /= i;
            }
            string r = s;
            reverse(s.begin(), s.end());
            if (s == r) base.push_back(i);
        }
        if (base.size() == 0) cout << "Number " << n << " is not palindrom" << endl;
        else {
            cout << "Number " << n << " is palindrom in basis";
            for (int i = 0; i < base.size(); ++i) cout << " " << base[i];
            cout << endl;
        }
    }
}

Por eso digo que a veces uno se suele saltar esos principios para ganar velocidad. Obviamente, en códigos más largos es sin duda necesario usar funciones adecuadamente, poner nombres descriptivos, etc. Me refiero únicamente a concursos.