giovedì 23 maggio 2013

Problema di Eulero 4


Il quarto problema del Progetto Eulero e' cosi' formulato
------------------------------------------------------
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.
------------------------------------------------------

Francamente non sono riuscito a trovare un metodo per capire se un numero e' palindromo senza utilizzare le proprieta' delle stringhe o comunque la posizione del carattere nella stringa

Il programma per il calcolo e' stato il seguente (utilizza una funzione per l'inversione dell'ordine della stringa)
Ovviamente la soluzione e' sovrabbondante in quanto vengono trovati tutti i risultati palindromi per due fattori a tre cifre.
Se si usano come limite 100-999 il tempo di calcolo e' di circa 5 secondi mentre utilizzando  900-999 (senza modificare il risultato finale) il calcolo e' di 0.2 secondi

------------------------------------------------------
#include <iostream>

#include <sstream>
#include <string>

using namespace std;

string reverse(string src) { return string(src.rbegin(), src.rend()); }

int main()
{
    double max = 0;
    for (int t=100;t<1000;t++)
    {
        for (int s=100;s<1000;s++)
        {
            double prodotto = t*s;
            std::ostringstream os;
            os << prodotto;
            std::string str = os.str();
            string rovescia = reverse(str);
            if ((rovescia.compare(str) == 0) && (prodotto > max))
            {
                    max = prodotto;
            }
        }
    }
    cout << "Massimo : " << max << endl;
    return 0;
------------------------------------------------------

La soluzione e' 906609