[python] Albero binario in Python

Riporto qui un classico dell’informatica di base: la realizzazione di un albero binario per l’ordinamento.

Quello dell’albero binario è un algoritmo che consente di ordinare dei valori in base al criterio di inserimento e successivamente di lettura.

Per far capire meglio il procedimento vediamo anzitutto come funziona.

Immaginiamo di avere la sequenza di numeri 3, 4, 1, 7, 6, 5, 8, 11, 9. L’algoritmo prevede la creazione di una struttura ad albero, composta di nodi, dove ogni nodo contiene un valore e un ramo di sinistra e uno di destra, che puntano rispettivamente al valore minore e maggiore, rispetto al valore nel nodo. La creazione dell’albero procederà quindi come nel video soprastante.

La lettura avverrà invece a partire dal primo nodo, procedendo anzitutto sul nodo di sinistra, poi stampando il valore del nodo corrente e poi procedendo sul nodo di destra. Come illustrato nella seguente animazione:

 

Procedendo in questo modo otterremo tutti i valori ordinati.

Questo algoritmo può essere scritto in Python nel modo seguente:

 

Vedi articolo

[python] Semplice esercizio per creare il gioco del campo minato in Python (da console)

In questo semplice esercizio vogliamo riprodurre in Python, in modo un po’ rudimentale, quello che era il gioco del campo minato (poi campo fiorito) per Windows.

Quello che vogliamo ottenere assomiglierà a questo all’avvio:

Mentre alla vittoria otterremo qualcosa di simile:

Il gioco sarà costruito su una griglia 10×10, di 100 caselle in totale, che faremo selezionare all’utente con un numero da 1 a 100.

Anzitutto costruiamo la griglia fatta di oggetti di tipo Casella, definiti nel modo seguente:

Per costruire il campo useremo la funzione random.randint() per distribuire le mine in modo casuale, nel modo seguente:

In questo caso la variabile difficolta viene usata per bilanciare la distribuzione casuale. Se impostiamo difficolta su 2, avremo in media il 50% di caselle con mine (1/2). Se impostiamo difficolta su 10 allora avremo circa il 10% di mine (1/10), ecc.

Fatto questo dobbiamo costruire due metodi che si occuperanno rispettivamente di conteggiare le mine e aprire le celle. All’interno di entrambi i metodi useremo due cicli for ricordandoci che rispetto alla posizione attuale quelle intorno partiranno da [-1,-1] fino a [1,1]

Riporto di seguito il codice, commentato, dell’intero giochino realizzato a partire da queste idee:

 

Vedi articolo

[python] Esercizio su funzioni ricorsive e calcolo del percorso minore possibile

Immaginiamo di avere la seguente situazione: su una griglia rettangolare abbiamo due punti, A e B e vogliamo calcolare il minore percorso possibile per arrivare da A a B, evitando degli ostacoli. Da una cella all’altra ci si può spostare solamente in verticale ed orizzontale.

Possiamo schematizzare il problema in qualcosa di simile.

Anzitutto impostiamo le variabili necessarie:

In particolare faccio notare che terremo tutti i percorsi in una lista percorsi = [] e vogliamo anche tenere traccia della minima lunghezza trovata con minlen. Questo accorgimento, come vedremo successivamente, ci servirà per ridurre notevolmente la quantità di calcoli da dover effettuare, eliminando tutti i percorsi che via via dovessero rivelarsi più lunghi del minimo percorso trovato (fino a quel momento).

A questo punto generiamo la matrice del mondo:

Adesso scriviamo la funzione per popolare il mondo di blocchi, le X del disegno precedente. Per farlo utilizzeremo la libreria random, per cui ricordiamoci di importarla all’inizio con import random

Utilizziamo random.randint per generare una posizione casuale su righe e colonne per i blocchi, verifichiamo che tale punto non sia già occupato da un blocco, in tal caso procediamo ad aggiungerlo.

In modo analogo creiamo un metodo che aggiunga la posizione iniziale A e quella finale B, registrandole nelle rispettive variabili.

Per trovare il percorso procediamo nella maniera seguente:

Faccio notare una peculiarità, legata al modo in cui Python tratta le liste. Per passare il percorso attuale, copiandolo, alla funzione medesima, dobbiamo usare un piccolo trucco scrivendo []+percorso. In questo modo evitiamo che il percorso sia passato per riferimento, forzando il programma a crearne una copia.

Fatto tutto questo aggiungiamo un metodo per la stampa della matrice:

E un metodo per prendere uno dei percorsi più corti calcolati (ricordiamoci che potrebbero esserci più percorsi):

Infine uniamo tutto quanto insieme, importando anche la libreria temporale con import time per valutare la velocità di elaborazione.

Di seguito il codice completo:

L’output finale darà qualcosa di simile a questo:

Vedi articolo