Salta al contenuto
Note per Studenti Pattern algoritmici iterativi

Pattern algoritmici iterativi

In questa pagina 11

Molti problemi su sequenze si risolvono combinando pochi schemi di ciclo. Per ognuno conviene sapere inizializzazione, aggiornamento e invariante (vedi Ciclo whileCiclo while, cicli controllati da contatore, da sentinella e da condizione; break, continue, else; terminazione e invariante di ciclo.Ciclo while →).

Accumulatore

Variabile inizializzata all'elemento neutro dell'operazione e aggiornata a ogni elemento.

python
somma = 0                      # neutro della somma
prodotto = 1                   # neutro del prodotto
testo = ""                     # neutro della concatenazione
for x in valori:
    somma += x
    prodotto *= x

Invariante: dopo kk iterazioni somma è la somma dei primi kk elementi.

Contatore

python
conta = 0
for x in valori:
    if x > soglia:
        conta += 1
# equivalente: conta = sum(1 for x in valori if x > soglia)

Frequenze di più valori: un dizionario di contatori (vedi Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →).

Massimo e minimo

Si inizializza con il primo elemento, non con 0 (i valori potrebbero essere tutti negativi).

python
def indice_massimo(v):
    """Indice del massimo di una lista non vuota."""
    im = 0
    for i in range(1, len(v)):
        if v[i] > v[im]:
            im = i
    return im

> restituisce la prima occorrenza del massimo, >= l'ultima.

Ricerca con uscita anticipata (esiste?)

python
def contiene_negativo(v):
    for x in v:
        if x < 0:
            return True        # basta un esempio: esco subito
    return False               # solo dopo aver visto tutto

Verifica universale (per ogni?)

python
def tutti_positivi(v):
    for x in v:
        if x <= 0:
            return False       # basta un controesempio
    return True

Equivalenti predefiniti: any(x < 0 for x in v), all(x > 0 for x in v). Errore classico: mettere return True dentro il ciclo nel ramo else, decidendo dopo il primo elemento.

Filtro e trasformazione

python
positivi = [x for x in v if x > 0]          # filtro
doppi = [2 * x for x in v]                  # trasformazione (map)

Elementi adiacenti

Confronto di ogni elemento con il successivo: indici fino a len(v) - 2.

python
def ordinata(v):
    for i in range(len(v) - 1):
        if v[i] > v[i + 1]:
            return False
    return True

Finestra scorrevole

Somma di ogni blocco di k elementi consecutivi aggiornando invece di ricalcolare (O(n)O(n) invece di O(nk)O(nk)):

python
def max_somma_finestra(v, k):
    s = sum(v[:k])
    migliore = s
    for i in range(k, len(v)):
        s += v[i] - v[i - k]       # entra v[i], esce v[i-k]
        migliore = max(migliore, s)
    return migliore

Due indici

Due indici che si muovono da estremi opposti o a velocità diverse.

python
def palindroma(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True
python
def fusione(a, b):
    """Unisce due liste ordinate in una lista ordinata (base del merge sort)."""
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Tutte le coppie

python
# coppie i < j: n(n-1)/2 confronti
for i in range(len(v)):
    for j in range(i + 1, len(v)):
        if v[i] == v[j]:
            print("duplicato:", v[i])

Costo quadratico: con un insieme si fa in tempo lineare (vedi Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →).

Errori tipici

  • Inizializzare il massimo a 0 o l'accumulatore del prodotto a 0.
  • Decidere "per ogni" alla prima iterazione.
  • Indici fuori intervallo negli schemi con v[i + 1].
  • Reinizializzare l'accumulatore dentro il ciclo invece che prima.

Teoria collegata