Pillole di Python - Calcoliamo gli Happy Numbers

Post Views: 21

Oggi parleremo degli happy numbers, numeri facilmente riproducibili in Python, e cercheremo di presentare ai lettori un algoritmo ottimizzato

Prendiamo un numero
eleviamo al quadrato tutte le sue cifre, e sommiamole tra loro
continuiamo sin quando il vecchio ed il nuovo numero sono diversi
al termine, se ottieniamo 1, il numero è un numero felice.

Sembrerebbe un algoritmo semplice, ma occorre fare attenzione ad alcune peculiarità. Analizziamo assieme il codice sorgente in Python.

Il programma

# Metodo che ritorna la somma dei quadrati delle cifre di n
def numSquareSum(n):
    squareSum = 0;
    while(n):
        squareSum += (n % 10) * (n % 10);        
        n = int(n / 10);
    return squareSum;
 
# Metodo che ritorna True se n è un Happy Number
def isHappynumber(n):
    # initializza slow e fast con n
    slow = n;
    fast = n;
    while(True):
        # Sposta il primo numero n di una iterazione
        slow = numSquareSum(slow);
        
        # sposta il secondo numero di DUE iterazioni
        # attraverso una chiamata telescopica al metodo
        fast = numSquareSum(numSquareSum(fast));
        
        if(slow != fast):
            continue;
        else:
            break;
 
    # Se entrambi i numeri si incontrano a 1 ritorna True, altrimenti ritorna False
    return (slow == 1);
 
# Codice di lancio
n = 49 # 9986;
if (isHappynumber(n)):
    print(n , "is a Happy number")
else:
    print(n , "is not a Happy number")

# Metodo che ritorna la somma dei quadrati delle cifre di n

def numSquareSum(n):

squareSum = 0;

while(n):

squareSum += (n % 10) * (n % 10);

n = int(n / 10);

return squareSum;

# Metodo che ritorna True se n è un Happy Number

def isHappynumber(n):

# initializza slow e fast con n

slow = n;

fast = n;

while(True):

# Sposta il primo numero n di una iterazione

slow = numSquareSum(slow);

# sposta il secondo numero di DUE iterazioni

# attraverso una chiamata telescopica al metodo

fast = numSquareSum(numSquareSum(fast));

if(slow != fast):

continue;

else:

break;

# Se entrambi i numeri si incontrano a 1 ritorna True, altrimenti ritorna False

return (slow == 1);

# Codice di lancio

n = 49 # 9986;

if (isHappynumber(n)):

print(n , "is a Happy number")

else:

print(n , "is not a Happy number")

Il programma non richiede alcuna libreria o modulo esterno.

Il codice centrale definisce un n (49, per restare coerenti con l’immagine). Il metodo isHappyNumber() restituisce True se il numero è “felice”, False altrimenti. Lo richiamiamo come parametro di una if() valutandone il risultato: se il metodo ritorna True scriviamo “n is a Happy number”, altrimenti scriviamo “n is not a Happy numoer”.

Il metodo isHappynumber(), a sua volta, definisce per prima cosa due variabili, alle quali assoceremo inizialmente il valore di n. Quindi entra in un loop infinito. All’interno del loop la prima variabile viene assegnata come parametro alla chiamata del metodo ausiliario numSquareSum(). Quest’ultimo metodo non fa altro che azzerare la variabile squareSum, e sommarvi ciascuna cifra di n moltiplicata per sé stessa. Per i più pigri, l’operatore modulo (“%“) restituisce il resto della divisione intera del dividendo per il divisore. Nel nostro caso (49) avremo il seguente pseudocodice:

squareSum = squareSum + il resto della divisione intera 49 / 10 (quindi 9) al quadrato (81)

n = n / 10 (divisione intera) quindi 4

n diverso da zero, quindi cicla di nuovo

squareSum = squareSum + il resto della divisione intera 4 / 10 (quindi 4) al quadrato (16)

A questo punto SquareSum vale 81 + 16 = 97

n = n / 10 (divisione intera) quindi 0

esco dal ciclo restituendo 97 (la somma dei quadrati delle cifre)

Secondo passaggio

A questo punto vogliamo replicare il nostro algoritmo anche alla somma dei quadrati delle cifre di 97.

Anziché utilizzare unsistema di controlli multipli, chiamiamo il metodo numSquareSum() non su 49, ma sul risultato di numSquareSum(49), che come abbiamo visto, vale 97.

La riga 20 del codice chiama la fuzione sul risultato del numero precedente.

Infine (riga 22) confrontiamo le due variabili: se sono differenti continuiamo il nostro “ciclo infinito”, altrimenti ne usciamo con un break.

Le due variabili hanno lo stesso valore, ma il numero è “felice” solo se il risultato è 1, quindi ritorniamo il valore dell’espressione logica slow == 1, che vale True se e solo se slow vale 1.

Considerazioni finali

Il programma non è concettualmente difficile, e nell’introduzione è possibile scomporne la logica in 4 semplici passaggi. Quello che i vece volevamo mostrarvi in questo sorgente sono le tecniche di programmazione in Python. Abbiamo limitato il numero delle variabili utilizzate, e tratto un codice di uscita da un costrutto logico aritmetico. Abbiamo usato un metodo per calcolare il risultato dello stesso metodo. su un numero precedente. Abbiamo utilizzato l’operatore modulo per estrarre il resto di una divisione intera.

Insomma, abbiamo aumentato un po’ la complessità del nostro codice… Speriamo di aver fatto cosa a voi gradita, specie a chi ogni tanto ci domanda programmi un po’ più “gustosi”…

Iscriviti ai nostri gruppi Telegram

Link utili

Seguici per non perdere le prossime novità!

Luigi_Morelli

Definire ciò che si è non risulta mai semplice o intuitivo, in specie quando nella vita si cerca costantemente di migliorarsi, di crescere tanto professionalmente quanto emotivamente. Lavoro per contribuire al mutamento dei settori cardine della computer science e per offrire sintesi ragionate e consulenza ad aziende e pubblicazioni ICT, ma anche perche’ ciò che riesco a portare a termine mi dà soddisfazione, piacere. Così come mi piace suonare (sax, tastiere, chitarra), cantare, scrivere (ho pubblicato 350 articoli scientfici e 3 libri sinora, ma non ho concluso ciò che ho da dire), leggere, Adoro la matematica, la logica, la filosofia, la scienza e la tecnologia, ed inseguo quel concetto di homo novus rinascimentale, cercando di completare quelle sezioni della mia vita che ancora appaiono poco ricche.