Esempi didattici in Python

Questa pagina contiene alcuni esempi didattici di codice Python

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.