Laboratorio 4

ESERCIZIO XII

Scrivere un programma in grado di generare un triangolo di Tartaglia di altezza n, dove n è un intero inserito da tastiera. Ad esempio, per n = 5 si avrà:

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1

Soluzione


# Alternativa con indici:
def tartaglia_indici(n):
    triangolo = []
    triangolo.append([0]*n)    
    triangolo[0][0] = 1
    

    for i in range(1,n):
        
        triangolo.append([0]*n)    
        triangolo[i][0] = 1
        
        for c in range(1,n):

            triangolo[i][c]= triangolo[i-1][c-1]+triangolo[i-1][c]
        
    return triangolo

# Alternativa con zip
def tartaglia_zip(n):
    triangolo = []
    #inserisco il vertice del triangolo
    triangolo.append([1])
    for k in range(1, n):
        
        riga = [sum(k) for k in zip([0]+triangolo[-1], triangolo[-1]+[0])]

        triangolo.append(riga)

    return triangolo


def stampa_tartaglia(triangolo):
    """
    Parametro triangolo: list of lists [[], [], [], ...]
    
    """

    n_len = len(triangolo)
    print n_len
    #iterazione sulle righe del tirangolo (i.e. le liste)
    for i, line in enumerate(triangolo):
        print " "*(n_len-i)*3,

        #iterazione su ciascuna colonna
        for col in range(0, i+1):
            print "%5d" %triangolo[i][col],
        print 



print tartaglia_zip(5)
stampa_tartaglia(tartaglia_zip(5))

ESERCIZIO XIII

  1. Scrivere un programma che definisca la funzione dh(s,t), che implementi il calcolo della distanza di Hamming tra due stringhe s e t.

  2. Aggiungere la funzione dhplus(s,t), che generalizzi dh(s,t) al caso di stringhe di diversa lunghezza. Visto che molte generalizzazioni della distanza di Hamming sono possibili e’ richiesta l’implementazione di questo primo modo: estendere la stringa di lunghezza minore con una serie di caratteri non validi (ad esempio ’-’) in modo da ottenere stringhe di lunghezza uguale.

  3. Aggiungere una funzione dhplus2(s,t) che implementa un modo diverso per generalizzare la distanza di Hamming: prolungare le due stringhe con caratteri non validi fino ad una lunghezza pari alla somma delle due, iterare sulla lunghezza delle stringhe prolungate ogni volta ruotando una stringa spostando un carattere dal fondo alla testa e calcolare la distanza di Hamming, ritornare come valore della distanza di Hamming il minimo valore tra quelli calcolati.

    prova.......
    .....provola
    prova.......
    a.....provol
    prova.......
    la.....provo
    prova.......
    ola.....prov

Soluzione

# Punto I:
def dh(s,t):
    if len(s) != len(t):
        return -1        
    ones = [ es != et for es, et in zip(s,t) ]
    return sum(ones)    
    
s1 = 'prova'
s2 = 'privo'
print dh(s1,s2)

# Punto II

def dhplus(s,t):
    max_len = max(len(s), len(t))
    s_prime = s + '-'*(max_len - len(s))
    t_prime = t + '-'*(max_len - len(t))
    
    return dh(s_prime, t_prime)
    
s3 = 'prova'
s4 = 'provola'

print dhplus(s3,s4)

# Punto III ???

Published: October 31 2019