2.2. Array di interi Cosa fare con vettori di numeri interi. Prerequisiti funzioni con parametri, funzioni che restituiscono un valore, struttura di selezione: if, struttura di iterazione: for, Sequenze di dati: liste.

Argomenti trattati Lettura di numeri da tastiera, inizializzazione di una lista con valori casuali, somma di una sequenza di numeri, ricerca del minimo, verifica della presenza di un elemento in una sequenza, ordinamento di una sequenza.

Problema Leggere numeri e inserirli in una lista, visualizzare i numeri contenuti in una lista, svolgere alcune operazioni di base su una lista di interi: somma, prodotto, ricerca del minimo, ricerca del del massimo, ordinamento. Soluzione Una struttura di dati importante in informatica è costituita dagli array. Gli array sono sequenze indicizzabili di elementi. In Python gli array possono essere emulati dall’oggetto list e lo si può costruire racchiudendo tra parentesi quadre una sequenza di oggetti separati da virgole: >>> a=[1, 3, 5, 7, 9, 11] Dopo questo comando, l’oggetto a contiene i primi 6 numeri dispari. Si può ottenere l’ennesimo elemento di una lista scrivendo il nome della lista seguito dall’indice posto tra parentesi quadre. In Python, il primo elemento di ogni lista ha sempre indice 0. >>> print a[0] 1 >>> print a[3] 7 Ci proponiamo di scrivere alcune funzioni di base per l’elaborazione delle liste di numeri. Per incominciare ci serve una funzione che restituisca un array, di numeri interi, letto da tastiera. La funzione deve continuare a leggere numeri fnquando viene introdotto un valore particolare detto sentinella. In metalinguaggio: per leggilistainteri(sentinella) fa:

prepara una lista vuota avvia un ciclo infinito che:

leggi un valore se è uguale alla sentinella: termina il ciclo altrimenti: aggiungi il valore alla lista

restituisci la lista.

Possiamo partire: menu File - New Window, solite intestazioni, menu File - Save. Scriviamo questa prima funzione: import random

def leggilistainteri(sentinella=”0”):

result=[] while True:

e=raw_input(“introduci un numero (%s per finire): ” %

sentinella)

if e==sentinella: break else: result.append(int(e))

return result

Alcune osservazioni: 1. Il comando import random servirà per la prossima funzione, ma io preferisco metterlo all’inizio del programma. 2. Il parametro sentinella ha come valore di default “0”. ciò vuol dire che le due chiamate di funzione seguenti sono equivalenti: leggilistainteri() leggilistainteri(“0”) 3. Quando Python incotra il comando break esce dal ciclo, questo permette di eseguire un ciclo while True: che altrimenti sarebbe infinito.

Per le prove seguenti sarà utile avere una funzione che restituisca una lista di enne valori casuali. per listacasuale(n, mi=0, ma=100) fa:

prepara una lista vuota per n volte:

aggiungi alla lista un numero casuale tra mi e ma

restituisci la lista.

Questa volta, poiché il numero di elementi è già noto prima di avviare il ciclo, conviene usare un ciclo for: def listacasuale(n, mi=0, ma=100):

result=[] for i in xrange(n):

result.append(random.randrange(mi, ma))

return result

prima di procedere conviene verificare le due funzioni. <F5> per far valutare a Python il nostro programma, poi nell’ambiente IDLE proviamo le due nuove funzioni. Nel mio caso, dopo la correzione di un po’ di errori, hanno mostrato il seguente funzionamento: >>> a=leggilistainteri() introduci un numero (0 per finire): 34 introduci un numero (0 per finire): 65 introduci un numero (0 per finire): 2 introduci un numero (0 per finire): 0 >>> a [34, 65, 2] >>> b=listacasuale(10) >>> b [20, 1, 88, 77, 25, 62, 43, 60, 20, 42] >>> b=listacasuale(10, 0, 1000) >>> b [117, 266, 960, 567, 39, 122, 581, 289, 759, 73] Bene, messi a punto questi due strumenti, passiamo a risolvere alcuni tipici problemi sui vettori di numeri. Il primo consiste nel trovare il minimo valore contenuto nell’array. Il trucco consiste nel far finta che il minimo sia il primo elemento e, poi, confrontare questo valore con gli altri cambiandolo se se ne trova uno più piccolo. In metalinguaggio: per minimo(lista) fa:

metti in minimo il primo elemento della lista per ogni elemento della lista:

se l’elemento è più piccolo del minimo metti in minimo l’elemento

restituisci il minimo.

La traduzione risulta abbastanza semplice: ricordiamoci di mettere una stringa di commento come prima riga della funzione: def minimo(lista):

“”“Restituisce l’elemento minimo di una lista.”“” mi=lista[0] for e in lista:

if e<mi: mi=e

return mi

In qualche (raro) caso può interessare non l’elemento minimo, ma la posizione dell’elemento minimo. La funzione in questo caso è un po’ più complicata perché dobbiamo confrontare gli elementi della lista, ma dobbiamo memorizzare e restituire un indice. In metalinguaggio: per indiceminimo(lista) fa:

metti in minimo il primo indice della lista (0) per ogni indice della lista:

se (l’elemento con questo indice è più piccolo

dell’elemento che ha per indice minimo) allora:

metti in minimo questo indice

restituisci il minimo.

Accidenti, è più difficile da scrivere in metalinguaggio che in Python: def indiceminimo(lista):

“”“Restituisce l’indice dell’elemento min. di lista.”“” indmin=0 for indice in range(len(lista)):

if lista[indice]<lista[indmin]: indmin=indice

return indmin

Un’altra funzione utile è quella che calcola la somma degli elementi di una lista: per somma(lista) fa:

poni a 0 la somma parziale per ogni elemento della lista:

aggiungi il suo valore alla somma parziale

restituisci la somma parziale che, ora, è il totale.

La traduzione in Python non presenta sorprese: def somma(lista):

“”“Restituisce la somma degli elementi di una lista.”“” somma=0 for elemento in lista:

somma+=elemento

return somma

A volte è utile una funzione che controlla se un certo elemento è contenuto oppure no in un array, oppure che ci restituisce l’indice di un determinato elemento. Due funzioni che risolvono questi problemi possono essere scritte così: def appartiene(elemento, lista):

“”“Restituisce True se elemento appartiene a lista.”“” for e in lista:

if e==elemento: return True

return False

def indicedi(elemento, lista):

“”“Restituisce l’indice della prima occorrenza di

elemento in lista, retituisce -1 se l’elemento non è presente nella lista.”“”

for ind, ele in enumerate(lista):

if ele==elemento: return ind

return -1

Alcune osservazioni: 1. Il comando return termina il ciclo, la funzione e restituisce come risultato il valore che lo segue. 2. Poiché gli indici degli array iniziano da 0, per indicare che un elemento non è presente nell’array possiamo usare un numero negativo. 3. La funzione enumerate restituisce le coppie formate da un indice e il corrispondente elemento. 4. La funzione indicedi restituisce l’indice del primo elemento uguale a quello cercato presente nell’array.

Per provare le funzioni appena aggiunte, possiamo creare una lista e chiamarle con diversi argomenti: >>> a=[3,6,2,8,6,4,1] >>> print appartiene(6, a) True >>> print appartiene(23, a) False >>> print indicedi(4, a) 5 >>> print indicedi(6, a) 1 Un altro importante problema relativo agli array è quello dell’ordinamento. si parte con un array disordinato e si vuole ottenere uno ordinato. È un problema importante, perché è facile scrivere algoritmi poco efficienti, ma quelli efficienti risultano piuttosto complicati. Nei problemi pratici è facile dover ordinare array di migliaia o milioni di elementi e quindi non è secondario avere a disposizione un algoritmo più efficiente. Possiamo realizzare una prima soluzione nella quale la funzione cerca l’elemento più piccolo della lista, lo toglie e lo mette in fondo ad una nuova lista, procedendo così fin quando la prima lista è vuota. Per questa funzione useremo un altro metodo delle liste, metodo che restituisce un elemento togliendolo dalla lista: <lista>.pop(<indice>): per insertionsort(lista) fa:

il risultato è la lista vuota finquando la lista di partenza non è vuota:

trova l’indice dell’elemento minimo togli questo ele. dalla lista e mettilo nel risulato

restituisci il risultato

In Python: def insertionsort(lista):

“”“Rest. una lista con gli ele. di lista ordinati.”“” elementi=lista[:] result=[] while elementi!=[]:

im=indiceminimo(elementi) result.append(elementi.pop(im))

return result

Il bubblesort confronta ogni elemento con tutti quelli che lo seguono scambiando, gli elementi quando non sono in ordine. Questa funzione non produce un nuovo array disfando quello dato come argomento, ma ordina direttamente l’array passato come argomento. def bubblesort(lista):

“”“Ordina “sul posto” una lista.”“” for i in xrange(len(lista)-1):

for j in xrange(i+1, len(lista)):

if lista[j]<lista[i]:

lista[j], lista[i] = lista[i], lista[j]

Riassumendo Quando si devono elaborare degli array spesso si usa il ciclo for applicato direttamente agli elementi dell’array. Le funzioni che abbiamo scritto forniscono degli strumenti di base utilissimi in tutti i programmi che operano con array. Sono così utili che Python le fa già tutte senza bisogno di programmarle... il comando help(list) ci mostra tutto quello che le liste sanno già fare senza bisogno del nostro intervento. Come dicono gli hacker “due settimane di sperimentazione in laboratorio possono far risparmiare due buone ore di studio dei manuali in biblioteca”...