Esempi didattici in Python - Revision history

Renzo at 09:48, 28 October 2019

2019-10-28T09:48:38Z

Renzo: /* Divisori */

2019-10-28T09:47:43Z

Divisori

Renzo: /* Divisori */

2019-10-28T09:45:55Z

Divisori

Renzo: /* Divisori */

2019-10-28T09:44:28Z

Divisori

Renzo at 09:43, 28 October 2019

2019-10-28T09:43:53Z

Renzo at 09:41, 28 October 2019

2019-10-28T09:41:25Z

Renzo at 09:36, 28 October 2019

2019-10-28T09:36:27Z

Renzo: Created page with "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:..."

2019-10-28T09:36:05Z

Created page with "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:..."

New page

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 ''è '' 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>



=== 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.

← Older revision		Revision as of 09:36, 28 October 2019
Line 1:		Line 1:
−	Questa pagina contiene alcuni esempi di codice Python ~~usati durante le lezioni (e non solo)~~	+	Questa pagina contiene alcuni esempi didattici di codice Python

	=== Divisori ===		=== Divisori ===

@@ Line 169: / Line 169: @@
 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:
-<source lang=pyhton>
+<source lang=python>
 class queue(list):
      def __init__(self):
@@ Line 200: / Line 200: @@
 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).
-<source lang=pyhton>
+<source lang=python>
 class queue(list):
      def __init__(self):
@@ Line 235: / Line 235: @@
 Puo' essere interessante per introdurre gli insiemi in Python. La definizione appare naturale e descrittiva.
-<source lang=pyhton>
+<source lang=python>
 def sieve(n):
      sv={x for x in range(1,n)}
@@ Line 250: / Line 250: @@
 Sort per selezione:
-<source lang=pyhton>
+<source lang=python>
 def selection_sort(v):
      for i in range(len(v)):
@@ Line 259: / Line 259: @@
 Sort per inserzione:
-<source lang=pyhton>
+<source lang=python>
 def insertion_sort(v):
      for i in range(1,len(v)):
@@ Line 268: / Line 268: @@
 Bubblesort:
-<source lang=pyhton>
+<source lang=python>
 def bubblesort(v):
      for i in range(1,len(v)):
@@ Line 277: / Line 277: @@
 Una implementazione del quicksort molto compatta e elegante si ottiene con la List Comprehension (copia il vettore come il metodo standard ''sorted''):
-<source lang=pyhton>
+<source lang=python>
 def rqsorted(v):
      if v:
@@ Line 289: / Line 289: @@
 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:
-<source lang=pyhton>
+<source lang=python>
 def merge(v1,v2):
      v=[]
@@ Line 313: / Line 313: @@
 La seconda versione del mergesort copia il vettore. Anche la funzione rmerge e' ricorsiva.
-<source lang=pyhton>
+<source lang=python>
 def rmerge(v1,v2):
      if not v1:

@@ Line 37: / Line 37: @@
 Ma il Python ha anche il tipo insieme (set) che e' meglio indicato per questo esempio:
-<source lang=pyhton>
+<source lang=python>
 #!/usr/bin/env python3
@@ Line 71: / Line 71: @@
 Lo stesso esempio con la Set Comprehension (come si traduce? si traduce?):
-<source lang=pyhton>
+<source lang=python>
 #!/usr/bin/env python3

@@ Line 3: / Line 3: @@
 === Divisori ===
 Esempio sui divisori. Il primo programma ha uno stile Pascal o C:
+<source lang=python>
 #!/usr/bin/env python3
@@ Line 95: / Line 95: @@
 Il metodo migliore per calcolare il massimo comun divisore e' l'algoritmo di Euclide:
-<source lang=pyhton>
+<source lang=python>
 def gcd(x, y):
    while True:

@@ Line 4: / Line 4: @@
 Esempio sui divisori. Il primo programma ha uno stile Pascal o C:
 #!/usr/bin/env python3
@@ Line 34: / Line 33: @@
          print("i divisori di ", n, "sono", divisori(n))
          print("i divisori primi di ", n, "sono", divisoriprimi(n))
-</pre>
+</source>
 Ma il Python ha anche il tipo insieme (set) che e' meglio indicato per questo esempio:
-<pre>
+<source lang=pyhton>
 #!/usr/bin/env python3
@@ Line 67: / Line 66: @@
          print("i divisori di ", n, "sono", divisori(n))
          print("i divisori primi di ", n, "sono", divisoriprimi(n))
-</pre>
+</source>
 Lo stesso esempio con la Set Comprehension (come si traduce? si traduce?):
-<pre>
+<source lang=pyhton>
 #!/usr/bin/env python3
@@ Line 89: / Line 88: @@
          print("i divisori di ", n, "sono", divisori(n))
          print("i divisori primi di ", n, "sono", divisoriprimi(n))
-</pre>
+</source>
 Il primo e' piu' ''algoritmico, passo a passo'', ma anche piu' contorto. Il secondo e' piu' elegante ma puo' apparire ''magico-misterioso''.
@@ Line 96: / Line 95: @@
 Il metodo migliore per calcolare il massimo comun divisore e' l'algoritmo di Euclide:
-<pre>
+<source lang=pyhton>
 def gcd(x, y):
    while True:
@@ Line 107: / Line 106: @@
 def lcm(x, y):
    return x * y // gcd(x, y)
-</pre>
+</source>
 === Coda/Pila e programmazione a oggetti ===
@@ Line 168: / Line 167: @@
 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>
+<source lang=pyhton>
 class queue(list):
      def __init__(self):
@@ Line 194: / Line 193: @@
      def empty(self):
          return not list(self)
-</pre>
+</source>
 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>
+<source lang=pyhton>
 class queue(list):
      def __init__(self):
@@ Line 225: / Line 224: @@
      def empty(self):
          return not self
-</pre>
+</source>
 Purtroppo si rende necessario talvolta l'uso di ''super'' per fare riferimento a metodi con lo stesso nome,
 -->
@@ Line 234: / Line 233: @@
 Puo' essere interessante per introdurre gli insiemi in Python. La definizione appare naturale e descrittiva.
-<pre>
+<source lang=pyhton>
 def sieve(n):
      sv={x for x in range(1,n)}
@@ Line 241: / Line 240: @@
              sv -= {x for x in range(2*i,n,i)}
      return [x for x in range(n) if x in sv]
-</pre>
+</source>
 === Ordinamento ===
@@ Line 249: / Line 248: @@
 Sort per selezione:
-<pre>
+<source lang=pyhton>
 def selection_sort(v):
      for i in range(len(v)):
@@ Line 255: / Line 254: @@
              if v[j] < v[i]:
                  v[i],v[j]=v[j],v[i]
-</pre>
+</source>
 Sort per inserzione:
-<pre>
+<source lang=pyhton>
 def insertion_sort(v):
      for i in range(1,len(v)):
@@ Line 264: / Line 263: @@
              if v[j] > v[i]:
                  v.insert(j, v.pop(i))
-</pre>
+</source>
 Bubblesort:
-<pre>
+<source lang=pyhton>
 def bubblesort(v):
      for i in range(1,len(v)):
@@ Line 273: / Line 272: @@
              if v[j+1] < v[j]:
                  v[j+1],v[j]=v[j],v[j+1]
-</pre>
+</source>
 Una implementazione del quicksort molto compatta e elegante si ottiene con la List Comprehension (copia il vettore come il metodo standard ''sorted''):
-<pre>
+<source lang=pyhton>
 def rqsorted(v):
      if v:
@@ Line 285: / Line 284: @@
      else:
          return []
-</pre>
+</source>
 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>
+<source lang=pyhton>
 def merge(v1,v2):
      v=[]
@@ Line 309: / Line 308: @@
              v[i:i+2*ls]=merge(v[i:i+ls],v[i+ls:i+2*ls])
          ls *= 2
-</pre>
+</source>
 La seconda versione del mergesort copia il vettore. Anche la funzione rmerge e' ricorsiva.
-<pre>
+<source lang=pyhton>
 def rmerge(v1,v2):
      if not v1:
@@ Line 329: / Line 328: @@
      else:
          return rmerge(rmergesorted(v[:half]),rmergesorted(v[half:]))
-</pre>
+</source>
 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.