(void *) blog

Posted on by fortytwo_de


Ya he terminado todos los exámenes de evaluación, así que me he propuesto dedicar una parte del día a resolver problemas, porque quiero clasificarme en la Olimpiada Informática el año que viene. La mayoría de los posts en el blog han estado relacionados con problemas de la Olimpiada, y es posible (que no probable) que en próximos posts comente soluciones de los problemas de Project Euler.

Por si alguien no lo conoce, Project Euler es una página con problemas de programación con un toque matemático muy interesante. Ellos mismos dicen que muchos problemas se pueden optimizar utilizando matemáticas, pero casi todos se pueden resolver con conocimientos de programación:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Interesante? Interesante.

Problema 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Mi solución:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char** argv) {
        int sum = 0;
        if(argc != 2) return -1;

        for(size_t i = 0; i < atoi(argv[1]); i++)
        {
                if(i % 3 == 0 || i % 5 == 0)
                        sum += i;
        }

        cout << sum << endl;
        return 0;
}

No tiene ninguna dificultad; tampoco se me ocurren optimizaciones.

Problema 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

El típico problema de programación dinámica. Ya me conozco este tipo de problemas de la Olimpiada Informática, así que implementarlo ha sido muy fácil:

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

#define INFINITY -1

int nth_fib(vector<int>& mem, int n) {
        if(mem[n] != INFINITY) return mem[n];
        mem[n] = nth_fib(mem, n-1) + nth_fib(mem, n-2);
        return nth_fib(mem, n);
}               

int main(int argc, char** argv) {
        if(argc != 2) return 0;

        int target = atoi(argv[1]), sum = 0;
        vector<int> mem(target, INFINITY);
        mem[0] = 1;
        mem[1] = 2;

        int i = 0;
        while(true) {
                int last = nth_fib(mem, i);
                if(last > target) 
                        break;
                if(last % 2 ==0) 
                        sum += last;
                i++;
        }

        cout << sum << endl;
        return 0;
}

Mi implementación de este problema sí que tiene su aquel, no es el método directo. Uso programación dinámica, es decir, almaceno en un vector<int> los valores de la sucesión de Fibonacci que ya he calculado; el algoritmo se ejecuta en tiempo linear.

Problema 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Un problema de factorización. Este problema me ha costado un poco más de lo que me tendría que haber costado, porque al principio intenté generar una lista de primos en el intervalo 1..n y luego comprobar cuáles de ellos eran factores de n.

Obviamente, esta solución con complejidad algorítmica de tiempo exponencial es completamente inútil para factorizar un número tan grande. Mi primera aproximación a este problema:

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

bool check_prime(int number) {
        if(number == 1) return false; // lol conventions 
        for(size_t i = 2; i < number; i++) 
                if(number % i == 0) return false; 

        return true;
}                       

vector<int> primes(int start, int end) {
        vector<int> result;
        for(size_t i = start; i < end; i++) {
                if(check_prime(i)) 
                        result.push_back(i);
        }
        return result;
}       

vector<int> factors(int target, vector<int> primes) {
        vector<int> result;
        for(size_t i = 0; i < primes.size(); i++) {
                if(target % primes[i] == 0)
                        result.push_back(primes[i]);
        }       
        return result;
}

int main(int argc, char** argv) {
        if(argc != 2) return -1;
        int target = atoi(argv[1]);

        vector<int> v_primes = primes(1, target);
        vector<int> v_factors = factors(target, v_primes);

        cout << *max_element(v_factors.begin(), v_factors.end()) << endl;
}

Como he dicho, completamente inútil para factorizar números grandes.

Después de darle un par de vueltas se me ocurrió que había un método muchísimo más sencillo para calcular factores primos: el método que se aprende en el colegio.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

vector<unsigned long int> factors(unsigned long int target) {
        vector<unsigned long int> result;
        unsigned long int candidate = 2;
        unsigned long int partial_target = target;

        while(candidate * candidate <= partial_target) {
                if(partial_target % candidate == 0) {
                        result.push_back(candidate);
                        partial_target /= candidate;
                } else candidate++;
        }       

        if(partial_target != 1)
                result.push_back(partial_target);

        return result;
}

int main(int argc, char** argv) {
        if(argc != 2) return -1;
        unsigned long int target = strtoul(argv[1], NULL, 10);

        vector<unsigned long int> v_factor = factors(target);
        cout << *max_element(v_factor.begin(), v_factor.end()) << endl;
}

¿No es genial la librería STL de C++?

Mucho mejor así. No estoy seguro de la complejidad de este algoritmo, pero me imagino que será algo así como tiempo logarítmico.

Actualización: Me comenta Dirbaio que la factorización de primos no es en tiempo logarítmico. Realmente lo he dicho por decir, debería estar avergonzado de mí mismo :P

Posted on by fortytwo_de | Posted in Algoritmos, C, Matemáticas, Programación, Project Euler


6 Responses to Project Euler – I

  1. Dirbaio says:


    Se puede comprobar si un numero es primo MUCHO mas rapido, basta con mirar si tiene un divisor menor o igual a su raíz cuadrada. Esto funciona porque si un número N tiene un divisor D, N/D también es un divisor. Si uno es mayor que la raiz cuadrada, el otro es menor. Me parece que esto ya lo estas utliizando en tu segundo codigo…

    bool check_prime(int number) {
    if(number == 1) return false; // lol conventions
    for(size_t i = 2; i*i <= number; i++)
    if(number % i == 0) return false;

    return true;
    }

    Otra cosa:
    while(pow(candidate, 2) <= partial_target) {
    cambialo por esto, que no utiliza floating point y es mucho mas eficiente
    while(candidate*candidate <= partial_target) {

    Yo tampoco se cual es el coste de factorizar enteros, pero SEGURO que no es logaritmico. Si el tuyo lo es, felicidades, puedes romper en segundos toda la criptografía que se usa actualmente!

    Nice post! Yo también me vicié al project euler hace unos años, ahora ya no me atrae tanto, pero trae bunos ejercicios de programación.
    :)


    • fortytwo_de says:


      Menuda cagada lo del tiempo logarítmico. Nota mental: no volver a calcular complejidades algorítmicas a ojo ;)

      Cambiado también lo de candidate * candidate, no sabía que pow utilizase comas flotantes (WTF).

      Y sobre lo de la comprobación de primos, sí, en el segundo código lo hago mucho mejor, el primer intento, como puedes ver, es una caca.

      Gracias por tus consejos! :D


  2. Manu Mateos says:


    Si en el primer problema el orden no es importante (que, pidiéndote únicamente una suma, no lo es)te propongo una solución mucho más rápida.

    Tu programa da “mil vueltas” para calcular la suma de los mútiplos de 3 y 5. Si primero sumas todos los múltiplos de 3 (en este caso y para un máximo de 1000, 333) y luego todos los múltiplos de 5 (200) das muchas menos vueltas. La complejidad sigue siendo igual de lineal pero, joder, es más rápido porque das muchas menos vueltas y te ahorras comparar. Daré por supuesto que en argv[1] está almacenado el máximo, en el caso de ese enunciado, 1000.

        #include 
        #include 
         
        using namespace std;
         
        int main(int argc, char** argv) {
        int sum = 0;
        if(argc != 2) return -1;
         
        size_t i = 0;
        while(i < atoi(argv[1]))
        {
        sum += i;
        i+=3;
        }
    
        i = 0;
        while(i < atoi(argv[1]))
        {
        sum += i;
        i+=5;
        }
         
        cout << sum << endl;
        return 0;
        }
    

    P.D. No sé si esto saldrá correctamente formateado. REZA PORQUE SÍ.


  3. Pingback: Project Euler – II | (void *) blog

  4. Pingback: Project Euler – III | (void *) blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>