Padroneggiare Massimo e Minimo in Python: Esercizi Pratici a Difficoltà Crescente (2)

Esercizi Intermedi

Esercizio 1 Trovare il secondo massimo in una lista:

Questo esercizio richiede di trovare il secondo valore più grande in una lista di numeri.

def secondo_massimo(numeri):
    if len(numeri) < 2:
        return "La lista deve contenere almeno due elementi."

    numeri_ordinati = sorted(list(set(numeri)), reverse=True) # Rimuove duplicati e ordina
    if len(numeri_ordinati) < 2: #gestisce il caso in cui ci sono solo elementi uguali
        return "Non esiste un secondo massimo distinto."
    return numeri_ordinati[1]

numeri1 = [10, 5, 20, 8, 15]
numeri2 = [10, 10, 10]
numeri3 = [5]

print(f"Secondo massimo di {numeri1}: {secondo_massimo(numeri1)}") # Output: Secondo massimo di [10, 5, 20, 8, 15]: 15
print(f"Secondo massimo di {numeri2}: {secondo_massimo(numeri2)}") # Output: Secondo massimo di [10, 10, 10]: Non esiste un secondo massimo distinto.
print(f"Secondo massimo di {numeri3}: {secondo_massimo(numeri3)}") # Output: Secondo massimo di [5]: La lista deve contenere almeno due elementi.

Spiegazione:

Usiamo set() per rimuovere eventuali duplicati, poi ordiniamo la lista in ordine decrescente con sorted(..., reverse=True). Il secondo elemento della lista ordinata è il secondo massimo. Gestiamo anche i casi in cui la lista ha meno di due elementi o contiene solo elementi uguali.

Esercizio 2 Trovare il massimo di una funzione in un intervallo discreto:

Supponiamo di avere una funzione matematica e vogliamo trovare il suo valore massimo in un determinato intervallo discreto.

def funzione(x):
    return x**2 - 4*x + 3

intervallo = range(-10, 11) # Intervallo da -10 a 10

massimo = max(intervallo, key=funzione)
valore_massimo = funzione(massimo)

print(f"Il massimo della funzione si trova in x = {massimo} e vale {valore_massimo}") # Output: Il massimo della funzione si trova in x = -10 e vale 143

Spiegazione:

Usiamo max() con l’argomento key per applicare la funzione a ogni valore nell’intervallo e trovare l’x che produce il valore massimo della funzione.

Esercizio 3 Trovare il massimo in una matrice:

Dato una matrice (lista di liste), trovare l’elemento massimo.

def massimo_matrice(matrice):
    if not matrice:
        return "La matrice è vuota."
    massimo = matrice[0][0]  # Inizializza con il primo elemento
    for riga in matrice:
        for elemento in riga:
            if elemento > massimo:
                massimo = elemento
    return massimo

matrice = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
matrice_vuota = []

print(f"Il massimo nella matrice è: {massimo_matrice(matrice)}") # Output: Il massimo nella matrice è: 9
print(f"Il massimo nella matrice vuota è: {massimo_matrice(matrice_vuota)}") # Output: Il massimo nella matrice vuota è: La matrice è vuota.

#Versione più concisa con list comprehension e max
def massimo_matrice_conciso(matrice):
    if not matrice:
        return "La matrice è vuota."
    return max([max(riga) for riga in matrice])

print(f"Il massimo nella matrice è: {massimo_matrice_conciso(matrice)}") # Output: Il massimo nella matrice è: 9
print(f"Il massimo nella matrice vuota è: {massimo_matrice_conciso(matrice_vuota)}") # Output: Il massimo nella matrice vuota è: La matrice è vuota.

Spiegazione:

Iteriamo attraverso ogni elemento della matrice e aggiorniamo il valore massimo se troviamo un elemento più grande. La versione concisa usa list comprehension per estrarre il massimo di ogni riga e poi calcolare il massimo tra questi massimi di riga.

Python: esercizi svolti sulle liste. La list comprehension ( parte III)

Esercizio 4 Trovare il massimo e il minimo di una funzione con ricerca esaustiva:

Questo esercizio introduce un concetto di ottimizzazione più avanzato, la ricerca esaustiva (o forza bruta).

Cos’è la ricerca esaustiva (forza bruta)?

La ricerca esaustiva, nota anche come ricerca per forza bruta, è una tecnica di risoluzione dei problemi che consiste nel provare sistematicamente tutte le possibili soluzioni candidate fino a trovare quella corretta. In altre parole, si esplora l’intero spazio delle soluzioni possibili, una per una, verificando se ciascuna di esse soddisfa i criteri del problema.

Come funziona?

Il funzionamento è concettualmente semplice:

1. Definizione dello spazio di ricerca: Si identifica l’insieme di tutte le possibili soluzioni al problema. Questo insieme può essere finito (ad esempio, tutte le possibili password di una certa lunghezza) o infinito (anche se in pratica si considera sempre un sottoinsieme finito).
2. Iterazione sulle soluzioni: Si scorrono tutte le soluzioni candidate nello spazio di ricerca.
3. Verifica della soluzione: Per ogni soluzione candidata, si verifica se soddisfa i requisiti del problema.
4. Restituzione della soluzione (o delle soluzioni): Se una soluzione soddisfa i requisiti, viene restituita come risultato. Se si cercano tutte le soluzioni, si continua l’iterazione.

Esempio pratico (ricerca di una password):

Immagina di voler “craccare” una password di 4 caratteri composta da lettere minuscole (a-z). Con la ricerca esaustiva, proveremmo:

• aaaa
• aaab
• aaac
• …
• aaaz
• aaba
• aabb
• …
• zzzz

e così via, fino a trovare la password corretta.

Vantaggi della ricerca esaustiva:

• Semplicità: È facile da implementare e da capire. Non richiede algoritmi complessi o conoscenze matematiche avanzate.
• Garanzia di trovare la soluzione (se esiste): Se il problema ha una soluzione e lo spazio di ricerca è finito, la ricerca esaustiva la troverà sicuramente.

Svantaggi della ricerca esaustiva:

• Inefficienza: Può essere estremamente inefficiente per problemi con spazi di ricerca molto grandi. Nell’esempio della password, ci sono 26⁴ = 456.976 possibili combinazioni. Questo numero cresce esponenzialmente con la lunghezza della password, rendendo la ricerca esaustiva impraticabile per password complesse.
• Costo computazionale elevato: Richiede una grande quantità di calcoli e quindi tempo di esecuzione, soprattutto per problemi complessi.

Quando usare la ricerca esaustiva?

La ricerca esaustiva è appropriata quando:

• Lo spazio di ricerca è piccolo.
• La semplicità dell’implementazione è più importante dell’efficienza.
• Non esistono algoritmi più efficienti per risolvere il problema.
• È necessario trovare tutte le possibili soluzioni.

Ottimizzazioni (per ridurre la complessità):

Anche se la ricerca esaustiva in sé non è un algoritmo di ottimizzazione, ci sono alcune tecniche che possono essere utilizzate per ridurre la dimensione dello spazio di ricerca e quindi migliorare le prestazioni:

• Potatura (Pruning): Se si possono identificare delle parti dello spazio di ricerca che sicuramente non contengono la soluzione, queste possono essere escluse dalla ricerca.
• Euristiche: Si possono utilizzare delle euristiche per guidare la ricerca verso le aree più promettenti dello spazio di ricerca, senza doverle esplorare completamente.

La ricerca esaustiva è una tecnica fondamentale per la risoluzione di problemi, soprattutto quando non si conoscono algoritmi più efficienti. Tuttavia, è importante essere consapevoli dei suoi limiti in termini di efficienza e costo computazionale. Quando lo spazio di ricerca è troppo grande, è necessario ricorrere a tecniche di ottimizzazione più avanzate.

Torniamo al nostro esercizio:

import math

def funzione_complessa(x, y):
    return math.sin(x) + math.cos(y) + x*y

def ricerca_esaustiva(funzione, intervallo_x, intervallo_y, passo):
    massimo = -math.inf
    minimo = math.inf
    x_massimo, y_massimo = None, None
    x_minimo, y_minimo = None, None

    for x in range(intervallo_x[0], intervallo_x[1] + 1, passo):
        for y in range(intervallo_y[0], intervallo_y[1] + 1, passo):
            valore = funzione(x, y)
            if valore > massimo:
                massimo = valore
                x_massimo, y_massimo = x, y
            if valore < minimo:
                minimo = valore
                x_minimo, y_minimo = x, y

    return massimo, (x_massimo, y_massimo), minimo, (x_minimo, y_minimo)

intervallo_x = (-5, 5)
intervallo_y = (-5, 5)
passo = 1

massimo, (x_massimo, y_massimo), minimo, (x_minimo, y_minimo) = ricerca_esaustiva(funzione_complessa, intervallo_x, intervallo_y, passo)

print(f"Massimo: {massimo} in (x={x_massimo}, y={y_massimo})")
print(f"Minimo: {minimo} in (x={x_minimo}, y={y_minimo})")

Massimo: 26.242586460126365 in (x=-5, y=-5)
Minimo: -25.67526208919991 in (x=5, y=-5)

Spiegazione:

Questo esempio cerca il massimo e il minimo di una funzione di due variabili x e y in un’area definita dagli intervalli intervallo_x e intervallo_y. Il parametro passo determina la granularità della ricerca. Questa è una ricerca esaustiva perché valuta la funzione per ogni combinazione di x e y nell’intervallo specificato.

In questo esercizio, la ricerca esaustiva viene utilizzata per trovare il massimo e il minimo di una funzione di due variabili (x e y) in un’area definita. L’intervallo di x e y, insieme al passo, definisce lo spazio di ricerca. Il codice itera su tutte le combinazioni di x e y in questo spazio, calcola il valore della funzione per ogni combinazione e tiene traccia del massimo e del minimo trovati.

 

(98)

PubblicitàPubblicità