Follow

Questo problema recita:

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.

Risolviamo questo problema prima concettualmente e poi passiamo alla sua implementazione in Python.

A livello concettuale dobbiamo inanzitutto definire che cosa è un numero palindromo. Come bene potete intuire un numero è palindromo se è uguale al numero formato dalle cifre lette in ordine inverso.

Dopo di che dobbiamo effettuare i prodotti fra tutti i numeri compresi nell’intervallo [1;999] e fra i prodotti selezionare il palindromo maggiore.

Realizzare questo in python non richiede grossi cambiamenti perchè come al solito si rivela un linguaggio molto simile al concetto.

Innanzitutto scriviamo un metodo che dato un intero ci dice se è palindromo.

def estPalindromo(num) :
    stringa = str(num)
    lunghezza = len(stringa)
    i = 0
    while i<(lunghezza/2) :
        if stringa[i]!=stringa[lunghezza-i-1] :
            return False
        i+=1
    return True

Questo metodo è di facile interpretazione. Inannzitutto converte l’intero in una stringa con il cast esplicito str(…). Dopodichè scandisce la stringa e controlla se il primo carattere è uguale all’ultimo, se il secondo è uguale al penultimo e cosi via.

Dopodichè facciamo la funzione che si occupa di fare i prodotti, controllare se palindromi e selezionare il massimo.

def largestPalindromo() :
    num1 = 999
    num2 = 999
    max = 0
    while num1>99 :
        while num2>99 :
            numero = num1*num2
            if estPalindromo(numero) :
                if max<=numero : max = numero
                break
            num2-=1
        num2 = 999
        num1-= 1
    return max

Questa funzione può apparire poco intuitiva. In pratica esegue i prodotti partendo da 999×999; 999×998…. e cosi via. Se il risultato del prodotto è palindromo controlla se è più grande della variabile max e in caso affermativo la aggiorna con il nuovo massimo.

La penultima e la terzultima riga servono ad effettuare il decremento circolare, ovvero dopo 999×1 toccherà a 998×999.

Ovviamente questo non è l’algoritmo ottimo. Solo per fare un esempio, in questo modo ogni possibile prodotto viene analizzato due volte ( 999×998 e 998×999 tanto per fare un esempio ) ma è più che suficente per ricavare il risultato che ci porta ad affrontare il problema 005.