(void *) blog

Posted on by fortytwo_de


Otros 3 problemas de Project Euler. Cada vez se van complicando más, pero de momento son asequibles.

Problema 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

En este problema lo complicado es comprobar si un número es un palíndromo. La función que he programado para comprobar si un número es un palíndromo no es del todo trivial:

bool palindrome(int target) {
        int pos, reversed = 0, original = target;

        while(target > 0) {
                pos = target % 10; 
                reversed *= 10;
                reversed += pos;
                target /= 10;
        }

        return original == reversed;
}

Nota: a % b es el operador módulo, es decir, el resto después de dividir a entre b.

Por ejemplo, para el número 1223:

  • Primera iteración.
    • target = 1223
    • target % 10 = 3
    • reversed = 0*10 + 1 = 3
    • target = 1223 / 10 = 122
  • Segunda iteración.
    • target = 122
    • target % 10 = 2
    • reversed = 3 * 10 + 2 = 32
    • target = 122 / 10 = 12
  • Tercera iteración.
    • target = 12
    • target % 10 = 2
    • reversed = 32 * 10 + 2 = 322
    • target = 12 / 10 = 1
  • Cuarta iteración.
    • target = 1
    • target % 10 = 1
    • reversed = 322 * 10 + 1 = 3221
    • target = 1/10 = 0
  • Quinta iteración. !(target > 0), se sale del bucle.

Cuando el bucle termina, reversed contiene el número original al revés, y la función devuelve la true si el número original es igual al número al revés. Es decir, si es un palíndromo.

Y main:

int main(int argc, char** argv) {
        if(argc != 2) return -1;
        int target = atoi(string(atoi(argv[1]), '9').c_str());
        int start = atoi(string(atoi(argv[1]) -1, '9').c_str());
        int candidate = 0;

        for(size_t i = start; i <= target; i++) {
                for(size_t ii = start; ii <= target; ii++) {
                        int product = i * ii;
                        if(palindrome(product) && product > candidate)
                                candidate = product;
                }
        } 

        cout << candidate << endl;

        return 0;
}

Mi método para calcular el inicio y el final del bucle es un poco hack, pero estoy sorprendentemente orgulloso de ello. El programa acepta un argumento por la línea de comandos, que es el número de dígitos que van a tener los factores.

Aprovecho el constructor string ( size_t n, char c );, con argumentos atoi(argv[1]), que es el argumento de línea de comandos y '9'. Para poder pasar esto a atoi, primero es necesario convertir el string a C-style string, que se puede hacer fácilmente utilizando el método miembro string.c_str().

Problema 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Mi aproximación inicial a este problema fue tirar por programación, pero hay una solución mucho más elelegante: factorizar todos los números en el intervalo 1..n y calcular el mínimo común múltiplo de ellos. Esto se podría hacer con la función de factorización que programé para el problema 3 (disponible aquí).

Pero como esto no se me ocurrió cuando lo programé, esta es mi solución poco elegante, que consiste en un bucle infinito del que se sale cuando se encuentra el primer número divisible entre todos los números de un intervalo, asumiendo que el primer número es el más pequeño.

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char** argv) {
        if(argc != 2) return -1;
        int target = atoi(argv[1]);
        int candidate = 1;
        while(true) {
                bool found = true;
                for(size_t i = 1; i < target; i++) {
                        if(candidate % i != 0) {
                                found = false;
                                break;
                        }
                }

                if(found == true)
                        break;
                candidate++;
        }

        cout << candidate << endl;
}

Es horrible, ya lo sé.

Problema 6

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Este problema es muy sencillo, imagino que sólo sirve para enseñar por inducción que la suma de los cuadrados no es lo mismo que el cuadrado de la suma.

La implementación es completamente directa, quizás se pueda optimizar con un sumatorio pero ni me molesté en hacerlo.

#include <iostream>
#include <cstdlib>

using namespace std;

int sum_sq_f(int start, int end) {
        int sum = 0;

        for(size_t i = start; i <= end; i++) {
                sum += i*i;
        }

        return sum;
}

int sq_sum_f(int start, int end) {
        int sum = 0;

        for(size_t i = start; i <= end; i++) {
                sum += i;
        }

        return sum * sum;
}

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

        cout << sq_sum - sum_sq << endl;
        return 0;
}

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


3 Responses to Project Euler – II

  1. Dirbaio says:


    La “manera C++” de hacer atoi() es usar un stringstream;

    #include <stringstream>
    (...)
    string s = "10";
    stringstream ss(s);
    int i;
    ss>>i;
    

    • fortytwo_de says:


      Ya me imaginaba que habría alguna forma “C++ style” de hacerlo, pero en realidad yo soy C for evah.

      Además, si hacen lo mismo, seguro que atoi es más rápido. xD


  2. Cash Advance Online says:


    heavenly see this page


Leave a Reply to Dirbaio Cancel 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>