Vogliamo scrivere un algoritmo in Python che, dato un lato n-esimo arbitrario, disegni una matrice di valori concentrici. Il risultato che vogliamo ottenere è il seguente:
Questo problema ha molteplici soluzioni e Python ne permette un’estrema sintesi.
Cominciamo dalla soluzione più semplice, ma che richiede il maggior numero di cicli.
Anzitutto calcoliamo la dimensione del quadrato:
|
1 2 |
n = int(input("lato: ")) dim = n*2-1 |
Adesso prepariamo una matrice di dimensione dim fatta di soli 0
|
1 |
m = [[0 for j in range(dim)] for i in range(dim)] |
Il procedimento che seguiremo ora sarà quello di stringere la matrice sempre di più, ridisegnando i vari quadrati all’interno della matrice di 0 appena creata.
|
1 2 3 4 |
for k in range(n): for i in range(k,dim-k): for j in range(k,dim-k): m[i][j] = n - k |
In questo modo disegneremo ad ogni passaggio un quadrato di numeri n-k
Stampiamo infine a video la matrice:
|
1 2 3 4 |
for r in m: for c in r: print(c,end=" ") print() |
Possiamo misurare il tempo di calcolo necessario (questo tempo dipende principalmente dal processore in uso, quindi varia da macchina a macchina) utilizzando la libreria time
Il codice diventerebbe il seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import time n = int(input("lato: ")) dim = n*2-1 start = time.time() m = [[0 for j in range(dim)] for i in range(dim)] for k in range(n): for i in range(k,dim-k): for j in range(k,dim-k): m[i][j] = n - k end = time.time() print("%s secondi" %(end-start)) |
Nel mio caso l’operazione per un lato di dimensione 1000 impiega circa 131.700 ms. Su questo torneremo successivamente.
Possiamo però riscrivere l’algoritmo in un altra forma più sintetica.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import time n = int(input("lato: ")) dim = n*2-1 start = time.time() def v(i,j): i = i if i < dim / 2 else dim - i - 1 j = j if j < dim / 2 else dim - j - 1 return n - (j if j <= i else i) m = [[v(i,j) for j in range(dim)] for i in range(dim)] end = time.time() |
Questa volta l’algoritmo impiega 1.250 ms circa, sempre per lato di dimensione 1000.
Il risultato è il medesimo, ma il tempo di calcolo è decisamente inferiore.
Un’altra versione potrebbe essere la seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import time n = int(input("lato: ")) dim = 2*n-1 start = time.time() m = [[0 for i in range(dim)] for j in range(dim)] for i in range(n): for j in range(i, dim-i): m[i][j] = n m[dim-i-1][j] = n m[j][i] = n m[j][dim-i-1] = n n -= 1 end = time.time() |
Questa volta il tempo di calcolo, per dimensione 1000 di lato, è di circa 490 ms.
Confrontando i tre algoritmi su range di calcoli da 50 a 1000, otteniamo le seguenti performance (il primo algoritmo lo chiamiamo A, l’ultimo lo chiamiamo C):
Che possiamo mettere in un grafico (con scala logaritmica) come il seguente:
