Visualizza sorgente di Esempi in Python per la didattica

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:

<pre>
#!/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))
</pre>

Ma il Python ha anche il tipo insieme (set) che e' meglio indicato per questo esempio:
<pre>
#!/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))
</pre>

Lo stesso esempio con la Set Comprehension (come si traduce? si traduce?):
<pre>
#!/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))
</pre>

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:
<pre>
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)
</pre>

=== 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':
<source lang=python>
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()
</source>

Passando alla programmazione a oggetti,
la versione migliore e' quella con un attributo nascosto "lista", perche' una coda ''ha'' una lista, non ''&egrave; '' una lista
<source lang=python>
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)
</source>

<!--
Ma le code e le pile possono venir viste anche come classi derivate della classe liste.
La prima versione chiama i metodi della classe lista esplicitamente:
<pre>
class queue(list):
    def __init__(self):
        list.__init__(self)

    def queue(self,x):
        list.append(self,x)

    def dequeue(self):
        return list.pop(self,0)

    def empty(self):
        return not list(self)

class stack(list):
    def __init__(self):
        list.__init__(self)

    def push(self,x):
        list.append(self,x)

    def pop(self):
        return list.pop(self)

    def empty(self):
        return not list(self)
</pre>
Questa versione e' per me elegante perche' tutte le funzioni vengono richiamate in modo uniforme. L'unico neo e' la necessita' di usare nomi di classi come prefisso dei metodi (di solito si usano i nomi degli oggetti e si omette self come parametro).

La seconda versione usa la ereditarieta': i metodi vengono richiamati semplicemente per nome, assumendo che si faccia riferimento alla prima definizione utile presente in una delle classi "ave" (anchestor).

<pre>
class queue(list):
    def __init__(self):
        super().__init__()

    def queue(self,x):
        self.append(x)

    def dequeue(self):
        return self.pop(0)

    def empty(self):
        return not self

class stack(list):
    def __init__(self):
        super().__init__()

    def push(self,x):
        self.append(x)

    def pop(self):
        return super().pop()

    def empty(self):
        return not self
</pre>
Purtroppo si rende necessario talvolta l'uso di ''super'' per fare riferimento a metodi con lo stesso nome,
-->

=== 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.
<pre>
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]
</pre>

=== 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:
<pre>
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]
</pre>

Sort per inserzione:
<pre>
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))
</pre>

Bubblesort:
<pre>
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]
</pre>

Una implementazione del quicksort molto compatta e elegante si ottiene con la List Comprehension (copia il vettore come il metodo standard ''sorted''):
<pre>
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 []
</pre>

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:
<pre>
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
</pre>

La seconda versione del mergesort copia il vettore. Anche la funzione rmerge e' ricorsiva.
<pre>
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:]))
</pre>
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.