Matrici e Ricorsione

Esercizi.

1. Scrivere una funzione ricorsiva che calcoli la lunghezza massima di una "catena di numeri" in una lista. Una "catena" è una sequenza di numeri consecutivi nella lista in cui il numero successivo è uguale al precedente più 1.

Esempio. Se la lista fosse: [1, 2, 3, 5, 6, 7, 8, 10, 11, 12] la funzione dovrebbe restituire 4, data dalla sequenza di numeri 5, 6, 7, 8. Le altre sequenze sono 1, 2, 3 e 10, 11, 12.

Bonus: Scrivere anche la versione iterativa della funzione.

2. Scrivere una funzione ricorsiva chiamata anchestor che, dato una lista con l'elenco di coppie padre-figlio e due stringhe rappresentanti un potenziale antenato (person1) e un potenziale discendente (person2), determini se il primo è un antenato del secondo. Si può assumere che la lista in input rispetti le seguenti condizioni:

• Il nome identifica univocamente ciascuna persona presente nella lista.

• Ogni figlio ha al massimo un padre.

• Non sono presenti cicli nella relazione padre-figlio (ad esempio, non può verificarsi il caso in cui Mario è il padre di Antonio, che è il padre di Giovanni, che a sua volta è il padre di Mario).

Esempio. Se la lista fosse: father_son = [("antonio", "alberto"), ("francesco", "simone"), ("francesco", "mario"), ("angelo", "andrea"), ("antonio", "marco"), ("marco", "gabriele"), ("gabriele", "eugenio")] la funzione anchestor(father_son, "antonio", "eugenio")) restituirebbe True perché antonio è il padre di alberto e di marco, marco è il padre di gabriele e gabriele è il padre di eugenio. Quindi, antonio è un antenato di eugenio.

Bonus: Scrivere anche la versione iterativa della funzione.

3. Data una matrice n x m di numeri interi, una valle è una cella il cui valore è minore di quello di tutte le celle adiacenti (sopra, sotto, sinistra e destra, se esistono). La profondità di una valle si calcola come la somma di tutte le celle adiacenti (sopra, sotto, sinistra e destra, se esistono). Scrivere una funzione greatest_valley che restituisca gli indici della valle con la profondità più alta. Se non ci sono valli, restituisce None.

Esempio:

matrice = [

    [5, 3, 4, 7],

    [2, 1, 6, 8],

    [7, 3, 2, 5],

    [9, 3, 5, 1],

]

La funzione restituirebbe (2, 2) perché l'elemento in posizione 2, 2 (cioè 2) è più piccolo di tutti gli elementi adiacenti (sopra si trova il 6, sotto il 5, a sinistra il 3 e a destra il 5) e la somma degli elementi adiacenti è pari a 19 (che è la massima tra tutte le altre valli nella matrice).

4. Data una matrice n x n contenente solo valori 0 e 1. Un'isola è definita come un gruppo di celle adiacenti contenenti 1 che possono essere collegate orizzontalmente o verticalmente (non diagonalmente). Scrivere una funzione find_largest_island che trova la dimensione dell’isola più grande presente nella matrice.

Esempio:

matrice = [

    [1, 1, 0, 0],

    [1, 0, 0, 1],

    [0, 0, 1, 1],

    [0, 1, 1, 1]

]

La funzione find_largest_island(matrice) restituirebbe 6, che è la dimensione dell'isola in basso a destra.