4.1.1   Somma attraverso incremento unitario: versione con ciclo while

...
def somma(x, y):
  z = x
  i = 1
  while i <= y:
    z += 1
    i += 1
  return z
...

4.1.2   Moltiplicazione di due numeri positivi attraverso la somma

La moltiplicazione di due numeri positivi, può essere espressa attraverso il concetto della somma: n*m equivale a sommare m volte n, oppure n volte m. L'algoritmo risolutivo è banale, ma utile per apprendere il funzionamento dei cicli:

#! /usr/bin/env python
##
## moltiplica.py <x> <y>
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# moltiplica(<x>, <y>)
#
def moltiplica(x, y):
  z = 0
  for i in range(y):
    z = z+x
  return z
#
# Inizio del programma.
#
x = int(sys.argv[1])
y = int(sys.argv[2])
z = moltiplica(x, y)
print x, "*", y, "=", z

In questo caso viene mostrata una soluzione per mezzo di un ciclo for. Il ciclo viene ripetuto y volte, incrementando la variabile z del valore di x. Alla fine, z contiene il risultato del prodotto di x per y. Il frammento seguente mostra invece la traduzione del ciclo for in un ciclo while:

...
def moltiplica(x, y):
  z = 0
  i = 1
  while i <= y:
    z = z+x
    i += 1
  return z
...

4.1.3   Divisione intera tra due numeri positivi

La divisione di due numeri positivi, può essere espressa attraverso la sottrazione: n/m equivale a sottrarre m da n fino a quando n diventa inferiore di m. Il numero di volte in cui tale sottrazione ha luogo, è il risultato della divisione.

#! /usr/bin/env python
##
## dividi.py <x> <y>
## Divide esclusivamente valori positivi.
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# dividi(<x>, <y>)
#
def dividi(x, y):
  z = 0
  i = x
  while i >= y:
    i = i-y
    z += 1
  return z
#
# Inizio del programma.
#
x = int(sys.argv[1])
y = int(sys.argv[2])
z = dividi(x, y)
print "Divisione intera -> %d/%d = %d" % (x, y, z)

Si noti anche l'uso dell'operatore di formato.

4.1.4   Elevamento a potenza

L'elevamento a potenza, utilizzando numeri positivi, può essere espresso attraverso il concetto della moltiplicazione: n**m equivale a moltiplicare m volte n per se stesso.

#! /usr/bin/env python
##
## exp.py <x> <y>
## Eleva a potenza.
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# exp(<x>, <y>)
#
def exp(x, y):
  z = 1
  for i in range(y):
    z = z*x
  return z
#
# Inizio del programma.
#
x = int(sys.argv[1])
y = int(sys.argv[2])
z = exp(x, y)
print "%d ** %d = %d" % (x, y, z)

In questo caso viene mostrata una soluzione per mezzo di un ciclo for. Il ciclo viene ripetuto y volte; ogni volta la variabile z viene moltiplicata per il valore di x, a partire da uno. Alla fine, z contiene il risultato dell'elevamento di x a y. Il frammento seguente mostra invece la traduzione del ciclo for in un ciclo while:

...
def exp(x, y):
  z = 1
  i = 1
  while i <= y:
    z = z*x
    i += 1
  return z
...

Il frammento seguente mostra una soluzione ricorsiva:

...
def exp(x, y):
  if x == 0:
    return 0
  elif y == 0:
    return 1
  else:
    return x*exp(x, y-1)
...

4.1.5   Radice quadrata

Il calcolo della parte intera della radice quadrata di un numero si può fare per tentativi, partendo da 1, eseguendo il quadrato fino a quando il risultato è minore o uguale al valore di partenza di cui si calcola la radice.

#! /usr/bin/env python
##
## radice.py <x>
## Radice quadrata.
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# radice(<x>)
#
def radice(x):
  z = 0
  t = 0
  while True:
    t = z*z
    if t > x:
      #
      # E` stato superato il valore massimo.
      #
      z -= 1
      return z
    z += 1
  #
  # Teoricamente, non dovrebbe mai arrivare qui.
  #
#
# Inizio del programma.
#
x = int(sys.argv[1])
z = radice(x)
print "radq(%d) = %d" % (x, z)

4.1.6   Fattoriale

Il fattoriale è un valore che si calcola a partire da un numero positivo. Può essere espresso come il prodotto di n per il fattoriale di n-1, quando n è maggiore di 1, mentre equivale a 1 quando n è uguale a 1. In pratica, n! = n * (n-1) * (n-2)... * 1.

#! /usr/bin/env python
##
## fatt.py <x>
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# fatt(<x>)
#
def fatt(x):
  i = x-1
  while i > 0:
    x = x*i
    i -= 1
  return x
#
# Inizio del programma.
#
x = int(sys.argv[1])
fatt = fatt(x)
print "%d! = %d" % (x, fatt)

La soluzione appena mostrata fa uso di un ciclo while in cui l'indice i, che inizialmente contiene il valore di x-1, viene usato per essere moltiplicato al valore di x, riducendolo ogni volta di un'unità. Quando i raggiunge lo zero, il ciclo termina e x contiene il valore del fattoriale. L'esempio seguente mostra invece una soluzione ricorsiva che dovrebbe risultare più intuitiva:

def fatt(x):
  if x == 1:
    return 1
  else:
    return x*fatt(x-1)

4.1.7   Massimo comune divisore

Il massimo comune divisore tra due numeri può essere ottenuto sottraendo a quello maggiore il valore di quello minore, fino a quando i due valori sono uguali. Quel valore è il massimo comune divisore.

#! /usr/bin/env python
##
## mcd.py <x> <y>
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# mcd(<x>, <y>)
#
def mcd(x, y):
  while x != y:
    if x > y:
      x = x-y
    else:
      y = y-x
  return x
#
# Inizio del programma.
#
x = int(sys.argv[1])
y = int(sys.argv[2])
z = mcd(x, y)
print "Il massimo comune divisore di %d e %d e` %d" %  (x, y, z)

4.1.8   Numero primo

Un numero intero è numero primo quando non può essere diviso per un altro intero diverso dal numero stesso e da 1, generando un risultato intero.

#! /usr/bin/env python
##
## primo.py <x>
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# primo(<x>)
#
def primo(x):
  primo = True
  i = 2
  while i < x and primo:
    j = x/i
    j = x-(j*i)
    if j == 0:
      primo = False
    else:
      i += 1
  return primo
#
# Inizio del programma.
#
x = int(sys.argv[1])
if primo(x):
  print x, "e` un numero primo"
else:
  print x, "non e` un numero primo"

4.2.1   Ricerca sequenziale

La ricerca di un elemento all'interno di un array disordinato può avvenire solo in modo sequenziale, cioè controllando uno per uno tutti gli elementi, fino a quando si trova la corrispondenza cercata. Segue la descrizione delle variabili più importanti che appaiono nei programmi Python successivi:

Ecco un esempio di programma Python che risolve il problema in modo iterativo:

#! /usr/bin/env python
##
## ricercaseq.py <elemento-cercato> <valore>...
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# ricercaseq(<lista>, <elemento>, <inizio>, <fine>)
#
def ricercaseq(lista, x, a, z):
  for i in range(a, z+1):
    if x == lista[i]:
      return i
  return -1
#
# Inizio del programma.
#
x = sys.argv[1]
lista = sys.argv[2:]
i = ricercaseq(lista, x, 0, len(lista)-1)
if i != -1:
  print "L'elemento", x, "si trova nella posizione", i
else:
  print "L'elemento", x, "non e` stato trovato"

L'algoritmo usato dovrebbe risultare abbastanza chiaro. Per quanto concerne le caratteristiche del linguaggio usato, si noti che Python supporta nativamente le liste, le quali sono strutture dati più complesse degli array, ma che ovviamente possono essere utilizzate per simularli, proprio come nell'esempio; le liste hanno gli indici che vanno da 0 a len(<lista>)-1, ove la funzione len restituisce il numero di elementi della lista <lista>; per accedere ai singoli elementi di una lista si usa la notazione <lista>[<indice>], inoltre è possibile estrarre una sottolista mediante la notazione <lista>[<indice_iniz>:<indice_fin>], eventualmente tralasciando uno dei due indici, che quindi assume valori predefiniti (rispettivamente 0 e len(<lista>)); si tenga presente che in tale notazione l'elemento corrispondente all'indice finale si intende da escludersi.

Esiste anche una soluzione ricorsiva che viene mostrata nel frammento seguente:

...
def ricercaseq(lista, x, a, z):
  if a > z:
    return -1
  elif x == lista[a]:
    return a
  else:
    return ricercaseq(lista, x, a+1, z)
...

4.2.2   Ricerca binaria

La ricerca di un elemento all'interno di un array ordinato può avvenire individuando un elemento centrale: se questo corrisponde all'elemento cercato, la ricerca è terminata, altrimenti si ripete nella parte di array precedente o successiva all'elemento, a seconda del suo valore e del tipo di ordinamento esistente.

Il problema posto in questi termini è ricorsivo. Il programma mostrato utilizza le stesse variabili già descritte per la ricerca sequenziale.

#! /usr/bin/env python
##
## ricercabin.py <elemento-cercato> <valore>...
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# ricercabin(<lista>, <elemento>, <inizio>, <fine>)
#
def ricercabin(lista, x, a, z):
  #
  # Determina l'elemento centrale.
  #
  m = (a+z)/2
  if m < a:
    #
    # Non restano elementi da controllare: l'elemento cercato
    # non c'e`.
    #
    return -1
  elif x < lista[m]:
    #
    # Si ripete la ricerca nella parte inferiore.
    #
    return ricercabin(lista, x, a, m-1)
  elif x > lista[m]:
    #
    # Si ripete la ricerca nella parte superiore.
    #
    return ricercabin(lista, x, m+1, z)
  else:
    #
    # m rappresenta l'indice dell'elemento cercato.
    #
    return m
#
# Inizio del programma.
#
x = sys.argv[1]
lista = sys.argv[2:]
i = ricercabin(lista, x, 0, len(lista)-1)
if i != -1:
  print "L'elemento", x, "si trova nella posizione", i
else:
  print "L'elemento", x, "non e` stato trovato"

4.3.1   Bubblesort

Il Bubblesort è un algoritmo relativamente semplice per l'ordinamento di un array, in cui ogni scansione trova il valore giusto per l'elemento iniziale dell'array stesso. Una volta trovata la collocazione di un elemento, si ripete la scansione per il segmento rimanente di array, in modo da collocare un altro valore. Il testo del programma dovrebbe chiarire il meccanismo.

Viene mostrata una soluzione iterativa:

#! /usr/bin/env python
##
## bsort.py <valore>...
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# bsort(<lista>, <inizio>, <fine>)
#
def bsort(lista, a, z):
  #
  # Inizia il ciclo di scansione dell'array.
  #
  for j in range(a, z):
    #
    # Scansione interna dell'array per collocare nella posizione
    # j l'elemento giusto.
    #
    for k in range(j+1, z+1):
      if lista[k] < lista[j]:
        #
        # Scambia i valori
        #
        scambio = lista[k]
        lista[k] = lista[j]
        lista[j] = scambio
#
# Inizio del programma.
#
lista = sys.argv[1:]
bsort(lista, 0, len(lista)-1)
for elemento in lista:
  print elemento,

Vale la pena di osservare nelle ultime due righe alcuni aspetti idiomatici di Python: avendo a disposizione una lista è possibile utilizzare i suoi elementi come indici di un ciclo for utilizzando la consueta parola chiave in; inoltre, se si intende che l'output non vada a capo ma prosegua sulla medesima riga, si può usare il simbolo , in coda all'istruzione print.

Segue la funzione bsort in versione ricorsiva:

def bsort(lista, a, z):
  if a < z:
    #
    # Scansione interna dell'array per collocare nella posizione
    # a l'elemento giusto.
    #
    for k in range(a+1, z+1):
      if lista[k] < lista[a]:
        #
        # Scambia i valori
        #
        scambio = lista[k]
        lista[k] = lista[a]
        lista[a] = scambio
    bsort(lista, a+1, z)

$ ./bsort.py 3 5 8 2 9 4512 7 67431 3 6 3
2 3 3 3 4512 5 6 67431 7 8 9

lista = sys.argv[1:]

lista = map(int, sys.argv[1:])

$ ./bsort.py 3 5 8 2 9 4512 7 67431 3 6 3
2 3 3 3 5 6 7 8 9 4512 67431

4.3.2   Torre di Hanoi

La torre di Hanoi è un gioco antico: si compone di tre pioli identici conficcati verticalmente su una tavola e di una serie di anelli di larghezze differenti. Gli anelli sono più precisamente dei dischi con un foro centrale che permette loro di essere infilati nei pioli.

Il gioco inizia con tutti gli anelli collocati in un solo piolo, in ordine, in modo che in basso ci sia l'anello più largo e in alto quello più stretto. Si deve riuscire a spostare tutta la pila di anelli in un dato piolo muovendo un anello alla volta e senza mai collocare un anello più grande sopra uno più piccolo.

Ecco la situazione iniziale della torre di Hanoi all'inizio del gioco:

Nella figura precedente gli anelli appaiono inseriti sul piolo 1; si supponga che questi debbano essere spostati sul piolo 2. Si può immaginare che tutti gli anelli, meno l'ultimo, possano essere spostati in qualche modo corretto, dal piolo 1 al piolo 3, come nella situazione della figura successiva:

A questo punto si può spostare l'ultimo anello rimasto (l'n-esimo), dal piolo 1 al piolo 2; quindi, come prima, si può spostare in qualche modo il gruppo di anelli posizionati attualmente nel piolo 3, in modo che finiscano nel piolo 2 sopra l'anello più grande.

Pensando in questo modo, l'algoritmo risolutivo del problema deve essere ricorsivo e potrebbe essere gestito da un'unica funzione che può essere chiamata opportunamente hanoi.

Segue il programma Python con funzione ricorsiva per la soluzione del problema:

#! /usr/bin/env python
##
## hanoi.py <n-anelli> <piolo-iniziale> <piolo-finale>
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# hanoi(<n-anelli>, <piolo-iniziale>, <piolo-finale>)
#
def hanoi(n, p1, p2):
  if n > 0:
    hanoi(n-1, p1, 6-p1-p2)
    print "Muovi l'anello %d dal piolo %d al piolo %d" % (n, p1, p2)
    hanoi(n-1, 6-p1-p2, p2)
##
## Inizio del programma.
##
(n, p1, p2) = map(int, sys.argv[1:4])
hanoi(n, p1, p2)

Si colga l'occasione per osservare un'ulteriore aspetto idiomatico di Python, ossia la possibilità di assegnare «in parallelo» gli elementi di una lista a più variabili (o, come si dice in gergo Python, una tupla) con una singola istruzione di assegnazione.

Tornando al problema, ecco l'analisi dell'algoritmo risolutivo: se n, il numero degli anelli da spostare, è minore di 1, non si deve compiere alcuna azione. Se n è uguale a 1, le istruzioni controllate dalla struttura if vengono eseguite, ma nessuna delle chiamate ricorsive fa alcunché, dato che n-1 è pari a zero. In questo caso, supponendo che n sia uguale a 1, che p1 sia pari a 1 e p2 pari a 2, il risultato è semplicemente:

Muovi l'anello 1 dal piolo 1 al piolo 2

Il risultato è quindi corretto per una pila iniziale consistente di un solo anello.

Se n è uguale a 2, la prima chiamata ricorsiva sposta un anello (n-1 = 1) dal piolo 1 al piolo 3 (ancora assumendo che i due anelli debbano essere spostati dal primo al terzo piolo) e si sa che questa è la mossa corretta. Quindi viene stampato il messaggio che dichiara lo spostamento del secondo piolo (l'n-esimo) dalla posizione 1 alla posizione 2. Infine, la seconda chiamata ricorsiva si occupa di spostare l'anello collocato precedentemente nel terzo piolo, nel secondo, sopra a quello che si trova già nella posizione finale corretta.

In pratica, nel caso di due anelli che devono essere spostati dal primo al secondo piolo, appaiono i tre messaggi seguenti.

Muovi l'anello 1 dal piolo 1 al piolo 3
Muovi l'anello 2 dal piolo 1 al piolo 2
Muovi l'anello 1 dal piolo 3 al piolo 2

Nello stesso modo si potrebbe dimostrare il funzionamento per un numero maggiore di anelli.

4.3.3   Quicksort (ordinamento non decrescente)

L'ordinamento degli elementi di un array è un problema tipico che si può risolvere in tanti modi. Il Quicksort è un algoritmo sofisticato, ottimo per lo studio della gestione degli array, oltre che per quello della ricorsione. Il concetto fondamentale di questo tipo di algoritmo è rappresentato dalla figura seguente:

Una sola scansione dell'array è sufficiente per collocare definitivamente un elemento (per esempio il primo) nella sua destinazione finale e allo stesso tempo per lasciare tutti gli elementi con un valore inferiore a quello da una parte, anche se disordinati, e tutti quelli con un valore maggiore, dall'altra.

In questo modo, attraverso delle chiamate ricorsive, è possibile elaborare i due segmenti dell'array rimasti da riordinare.

L'algoritmo può essere descritto grossolanamente come:

1. localizzazione della collocazione finale del primo valore, separando in questo modo i valori;
2. ordinamento del segmento precedente all'elemento collocato definitivamente;
3. ordinamento del segmento successivo all'elemento collocato definitivamente.

Viene qui indicato con part la funzione che esegue la scansione dell'array, o di un suo segmento, per determinare la collocazione finale (indice cf) del primo elemento (dell'array o del segmento in questione).

Sia lista l'array da ordinare. Il primo elemento da collocare corrisponde inizialmente a lista[a] e il segmento di array su cui intervenire corrisponde a lista[a:z+1] (cioè a tutti gli elementi che vanno dall'indice a all'indice z).

Alla fine della prima scansione, l'indice cf rappresenta la posizione in cui occorre spostare il primo elemento, cioè lista[a]. In pratica, lista[a] e lista[cf] vengono scambiati.

Durante la scansione che serve a determinare la collocazione finale del primo elemento, part deve occuparsi di spostare gli elementi prima o dopo quella posizione, in funzione del loro valore, in modo che alla fine quelli inferiori o uguali a quello dell'elemento da collocare si trovino nella parte inferiore e gli altri dall'altra. In pratica, alla fine della prima scansione, gli elementi contenuti in lista[a:cf] devono contenere valori inferiori o uguali a lista[cf], mentre quelli contenuti in lista[cf+1:z+1] devono contenere valori superiori.

Indichiamo con qsort la funzione che esegue il compito complessivo di ordinare l'array. Il suo lavoro consisterebbe nel chiamare part per collocare il primo elemento, continuando poi con la chiamata ricorsiva di se stessa per la parte di array precedente all'elemento collocato e infine alla chiamata ricorsiva per la parte restante di array.

Assumendo che part e le chiamate ricorsive di qsort svolgano il loro compito correttamente, si potrebbe fare un'analisi informale dicendo che se l'indice z non è maggiore di a, allora c'è un elemento (o nessuno) all'interno di lista[a:z+1] e inoltre, lista[a:z+1] è già nel suo stato finale. Se z è maggiore di a, allora (per assunzione) part ripartisce correttamente lista[a:z+1]. L'ordinamento separato dei due segmenti (per assunzione eseguito correttamente dalle chiamate ricorsive) completa l'ordinamento di lista[a:z+1].

Le figure seguenti mostrano due fasi della scansione effettuata da part all'interno dell'array o del segmento che gli viene fornito:

In pratica, l'indice i, iniziando dal valore a+1, viene spostato verso destra fino a che viene trovato un elemento maggiore di lista[a], quindi è l'indice cf a essere spostato verso sinistra, iniziando dalla stessa posizione di z, fino a che viene incontrato un elemento minore o uguale a lista[a]. Questi elementi vengono scambiati e lo spostamento di i e cf riprende. Ciò prosegue fino a che i e cf si incontrano, momento in cui lista[a:z+1] è stata ripartita e cf rappresenta la collocazione finale per l'elemento lista[l].

Segue il programma Python che include le due funzioni.

#! /usr/bin/env python
##
## qsort.py <valore>...
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# part(<lista>, <inizio>, <fine>)
#
def part(lista, a, z):
  #
  # Viene preparata una variabile che serve per scambiare due valori.
  #
  scambio = 0
  #
  # Si assume che a sia inferiore a z.
  #
  i = a+1
  cf = z
  #
  # Inizia il ciclo di scansione dell'array.
  #
  while True:
    while True:
      #
      # Sposta i a destra.
      #
      if lista[i] > lista[a] or i >= cf:
        break
      else:
        i += 1
    while True:
      #
      # Sposta cf a sinistra.
      #
      if lista[cf] <= lista[a]:
        break
      else:
        cf -= 1
    if cf <= i:
      #
      # E` avvenuto l'incontro tra i e cf.
      #
      break
    else:
      #
      # Vengono scambiati i valori.
      #
      scambio = lista[cf]
      lista[cf] = lista[i]
      lista[i] = scambio
      i += 1
      cf -= 1
  #
  # A questo punto lista[a:z+1] e` stata ripartita e cf e` la
  # collocazione di lista[a].
  #
  scambio = lista[cf]
  lista[cf] = lista[a]
  lista[a] = scambio
  #
  # A questo punto, lista[cf] e` un elemento (un valore) nella
  # giusta posizione.
  #
  return cf
#
# quicksort(<lista>, <inizio>, <fine>)
#
def quicksort(lista, a, z):
  #
  # Viene preparata la variabile cf.
  #
  cf = 0
  #
  if z > a:
    cf = part(lista, a, z)
    quicksort(lista, a, cf-1)
    quicksort(lista, cf+1, z)
##
## Inizio del programma.
##
lista = sys.argv[1:]
#
quicksort(lista, 0, len(lista)-1);
#
for elemento in lista:
  print elemento,
#

$ python
Python 2.3.4 (#2, Jul  5 2004, 09:15:05) 
[GCC 3.3.4 (Debian 1:3.3.4-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> lista = [1, 3, 7, 0, 10]
>>> altra_lista = lista
>>> altra_lista[3] = 1000
>>> print lista
[1, 3, 7, 1000, 10]
>>> [Ctrl-D]
$

4.3.4   Permutazioni

La permutazione è lo scambio di un gruppo di elementi posti in sequenza. Il problema che si vuole analizzare è la ricerca di tutte le permutazioni possibili di un dato gruppo di elementi.

Se ci sono n elementi in un array, allora alcune delle permutazioni si possono ottenere bloccando l'n-esimo elemento e generando tutte le permutazioni dei primi n-1 elementi. Quindi l'n-esimo elemento può essere scambiato con uno dei primi n-1, ripetendo poi la fase precedente. Questa operazione deve essere ripetuta finché ognuno degli n elementi originali è stato usato nell'n-esima posizione.

Segue il programma python:

#! /usr/bin/env python
##
## permuta.py <valore>...
##
#
# Importa il modulo sys, per usare sys.argv
#
import sys
#
# permuta(<lista>, <inizio>, <fine>)
#
def permuta(lista, a, z):
  #
  # Se il segmento di array contiene almeno due elementi, si
  # procede.
  #
  if z-a >= 1:
    #
    # Inizia un ciclo di scambi tra l'ultimo elemento e uno degli
    # altri contenuti nel segmento di array.
    #
    for k in range (z, a-1, -1):
      #
      # Scambia i valori.
      #
      scambio = lista[k]
      lista[k] = lista[z]
      lista[z] = scambio
      #
      # Esegue una chiamata ricorsiva per permutare un segmento
      # piu` piccolo dell'array.
      #
      permuta(lista, a, z-1)
      #
      # Scambia i valori.
      #
      scambio = lista[k]
      lista[k] = lista[z]
      lista[z] = scambio
  else:
    #
    # Visualizza la situazione attuale dell'array.
    #
    for elemento in lista:
      print elemento,
    print
##
## Inizio del programma.
##
lista = sys.argv[1:]
#
permuta(lista, 0, len(lista)-1)
#

Si colga l'occasione per notare un paio di aspetti idiomatici di Python. Per prima cosa, è possibile usare la funzione range per costruire un ciclo for decrescente, poiché range accetta un terzo argomento che in pratica rappresenta il passo con cui viene generata la successione di valori che popola la lista; ecco alcuni esempi:

$ python
Python 2.3.4 (#2, Jul  5 2004, 09:15:05) 
[GCC 3.3.4 (Debian 1:3.3.4-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(1, 11)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> range(0, 30, 5)
[0, 5, 10, 15, 20, 25]
>>> range(0, 10, 3)
[0, 3, 6, 9]
>>> range(0, -10, -1)
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
>>> range(0)
[]
>>> range(1, 0)
[]
>>> [Crtl-D]
$

si noti in particolare che, al solito, il secondo argomento denota il primo valore escluso dalla successione. Si noti infine l'uso dell'istruzione print isolata, allo scopo di andare a capo (ciò è necessario poiché nel ciclo for precedente si era usato il simbolo , in coda, il quale sopprime il carattere di newline).