Esempi didattici in Python
Questa pagina contiene alcuni esempi di codice Python usati durante le lezioni (e non solo)
Divisori
Esempio sui divisori. Il primo programma ha uno stile Pascal o C:
#!/usr/bin/env python3
def divisori(x):
s=[]
for i in range(2,x):
if x%i == 0:
s.append(i)
return s;
def primo(x):
if divisori(x):
return False
else:
return True
def divisoriprimi(x):
s=[]
for i in divisori(x):
if (primo(i)):
s.append(i)
return s
if __name__ == '__main__':
n=int(input("dammi n "))
if primo(n):
print(n ,"e' primo")
else:
print("i divisori di ", n, "sono", divisori(n))
print("i divisori primi di ", n, "sono", divisoriprimi(n))
Ma il Python ha anche il tipo insieme (set) che e' meglio indicato per questo esempio:
#!/usr/bin/env python3
def divisori(x):
s=set()
for i in range(2,x):
if x%i == 0:
s.add(i)
return s;
def primo(x):
if divisori(x):
return False
else:
return True
def divisoriprimi(x):
s=set()
for i in divisori(x):
if (primo(i)):
s.add(i)
return s
if __name__ == '__main__':
n=int(input("dammi n "))
if primo(n):
print(n ,"e' primo")
else:
print("i divisori di ", n, "sono", divisori(n))
print("i divisori primi di ", n, "sono", divisoriprimi(n))
Lo stesso esempio con la Set Comprehension (come si traduce? si traduce?):
#!/usr/bin/env python3
def divisori(x):
return {y for y in range(2,x) if x%y == 0}
def primo(x):
return not divisori(x)
def divisoriprimi(x):
return {y for y in divisori(x) if primo(y)}
if __name__ == '__main__':
n=int(input("dammi n "))
if primo(n):
print(n ,"e' primo")
else:
print("i divisori di ", n, "sono", divisori(n))
print("i divisori primi di ", n, "sono", divisoriprimi(n))
Il primo e' piu' algoritmico, passo a passo, ma anche piu' contorto. Il secondo e' piu' elegante ma puo' apparire magico-misterioso.
Fattorizzazione, mcm e MCD
Il metodo migliore per calcolare il massimo comun divisore e' l'algoritmo di Euclide:
def gcd(x, y):
while True:
if x < y:
x, y = y, x
x -= y
if x == 0:
return y
def lcm(x, y):
return x * y // gcd(x, y)
Coda/Pila e programmazione a oggetti
Le code e le pile (queue e stack) possono essere implementate a partire dalle liste. Le funzioni enqueue/dequeue per le code e push/pop per le pile possono essere implementate cosi':
def enqueue(s,x):
s.append(x)
def dequeue(s):
return s.pop(0)
def push(s,x):
s.append(x)
def pop(s):
return s.pop()
Passando alla programmazione a oggetti, la versione migliore e' quella con un attributo nascosto "lista", perche' una coda ha una lista, non è una lista
class queue:
def __init__(self):
self._list=[]
def enqueue(self, x):
self._list.append(x)
def dequeue(self):
return self._list.pop(0)
def empty(self):
return not self._list
def head(self):
return self._list[0]
def __str__(self):
return str(self._list)
class stack:
def __init__(self):
self._list=[]
def push(self, x):
self._list.append(x)
def pop(self):
return self._list.pop()
def empty(self):
return not self._list
def __str__(self):
return str(self._list)
Il setaccio di Eratostene
Ai miei tempi si chiamava crivello!
Puo' essere interessante per introdurre gli insiemi in Python. La definizione appare naturale e descrittiva.
def sieve(n):
sv={x for x in range(1,n)}
for i in range(2,n//2):
if i in sv:
sv -= {x for x in range(2*i,n,i)}
return [x for x in range(n) if x in sv]
Ordinamento
Ecco una carrellata di funzioni per l'ordinamento... Le prime sono funzioni per l'ordinamento di vettori/liste sul posto, modificando la sequenza degli elementi.
Sort per selezione:
def selection_sort(v):
for i in range(len(v)):
for j in range(i+1,len(v)):
if v[j] < v[i]:
v[i],v[j]=v[j],v[i]
Sort per inserzione:
def insertion_sort(v):
for i in range(1,len(v)):
for j in range(i):
if v[j] > v[i]:
v.insert(j, v.pop(i))
Bubblesort:
def bubblesort(v):
for i in range(1,len(v)):
for j in range(len(v)-i):
if v[j+1] < v[j]:
v[j+1],v[j]=v[j],v[j+1]
Una implementazione del quicksort molto compatta e elegante si ottiene con la List Comprehension (copia il vettore come il metodo standard sorted):
def rqsorted(v):
if v:
pivot=v[0]
lesser=[x for x in v[1:] if x <= pivot]
greater=[x for x in v[1:] if x > pivot]
return rqsorted(lesser) + [pivot] + rqsorted(greater)
else:
return []
Il mergesort e' un po' piu' macchinoso. La prima versione prevede l'ordinamento del vettore stesso, vengono copiati temporaneamente i vettori parziali e poi le sequenze vengono reinserite nel vettore originale:
def merge(v1,v2):
v=[]
while True:
if not v1:
return v+v2
elif not v2:
return v+v1
else:
if v1[0] < v2[0]:
v.append(v1.pop(0))
else:
v.append(v2.pop(0))
def mergesort(v):
lv=len(v)
ls=1;
while v[ls:]:
for i in range(0,lv,2*ls):
v[i:i+2*ls]=merge(v[i:i+ls],v[i+ls:i+2*ls])
ls *= 2
La seconda versione del mergesort copia il vettore. Anche la funzione rmerge e' ricorsiva.
def rmerge(v1,v2):
if not v1:
return v2
elif not v2:
return v1
elif v1[0] < v2[0]:
return v1[0:1]+rmerge(v1[1:],v2)
else:
return v2[0:1]+rmerge(v1,v2[1:])
def rmergesorted(v):
half=len(v)//2
if half == 0:
return v
else:
return rmerge(rmergesorted(v[:half]),rmergesorted(v[half:]))
Le definizioni delle funzioni merge e rmerge non sono state inserite nella definizione delle funzioni mergesort e rmergesorted (rispettivamente) perche' hanno una funzionalita' specifica di fusione di vettori ordinati e possono essere usate anche indipendentemente dal mergesort.