Specificare un problema: input, output e passi
Prima di scrivere codice, descrivi il problema in modo preciso. Questa è la specifica.
- Input: quali dati riceviamo, il loro tipo e i limiti (per esempio "n numeri interi, 1 ≤ n ≤ 1000").
- Output: che cosa dobbiamo restituire (per esempio "il più grande tra loro").
- Condizioni: che cosa è vero prima (precondizione) e dopo (postcondizione).
Scrivere i passi
Un algoritmo è un elenco finito di passi chiari che trasforma qualsiasi input valido nell'output giusto. Lo puoi scrivere come:
- linguaggio naturale: "Guarda ogni numero; se è più grande del migliore finora, ricordalo."
- elenco numerato di passi: 1. migliore ← primo numero. 2. Per ogni numero successivo x: se x > migliore allora migliore ← x. 3. Restituisci migliore.
- pseudocodice o diagramma di flusso per essere più precisi.
Provalo a mano su input piccoli, anche quelli difficili (tutti uguali, numeri negativi, un solo numero).
Progettazione top-down e bottom-up
Top-down (raffinamento per passi): parti dall'intero compito, dividilo in pochi passi grandi, poi dividi ancora ogni passo finché ogni parte è facile da programmare. Esempio: "Fare la pagella" → leggere i voti → calcolare le medie → assegnare i giudizi → stampare.
Bottom-up: prima costruisci e collauda piccoli pezzi riutilizzabili (una funzione che trova il massimo, una che ordina), poi li unisci nel programma completo.
I progetti veri usano entrambi: si pianifica top-down, si costruisce e si collauda bottom-up.
Divide et impera e il metodo del dimezzamento
Divide et impera ha tre mosse: dividi il problema in parti più piccole dello stesso tipo, risolvi ogni parte (spesso con la ricorsione), combina le risposte.
- Ricerca binaria (dimezzamento): in una lista ordinata, confronta con l'elemento di mezzo e butta via metà. n elementi richiedono circa log₂ n controlli: 16 → 4, 1 000 000 → 20.
- Merge sort: dividi la lista in due, ordina ogni metà, poi fondile: O(n log n).
- Potenza veloce: a⁸ = ((a²)²)²: 3 moltiplicazioni invece di 7.
- Trovare una radice con la bisezione: dimezza un intervallo in cui la funzione cambia segno.
Algoritmi greedy
Un algoritmo greedy ("goloso") fa la scelta che sembra migliore adesso e non la cambia mai.
- Dare il resto con 50, 20, 10, 5, 2, 1: prima la moneta più grande. È ottimale per questo tipo di sistema di monete.
- Scegliere più attività possibili in un giorno: prendi sempre quella che finisce prima. Ottimale.
- Zaino frazionario: prendi prima gli oggetti con il miglior valore per kg. Ottimale.
Ma il greedy non è sempre giusto: con monete 1, 3, 4, pagare 6 in modo greedy dà 4 + 1 + 1 (3 monete), mentre 3 + 3 ne usa 2. Per fidarti di un metodo greedy devi dimostrarlo, oppure confrontarlo con un metodo sicuro.
Programmazione dinamica e backtracking
Programmazione dinamica (DP)
Quando gli stessi problemi più piccoli si ripetono, risolvi ciascuno una volta sola e salva la risposta in una tabella. Minimo di monete per la somma a: best[a] = 1 + min(best[a - c]) sulle monete c ≤ a, partendo da best[0] = 0. Per monete 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. Riempire la tabella dal piccolo al grande è bottom-up; la ricorsione con una memoria è top-down (memoizzazione). Vedi la lezione separata sulla programmazione dinamica per saperne di più.
Backtracking
Costruisci una soluzione una scelta alla volta. Se una scelta rompe una regola o porta a un vicolo cieco, annullala e prova l'opzione successiva. Si usa per labirinti, Sudoku, il problema delle N regine e per elencare tutti i sottoinsiemi. È una forza bruta attenta: salta interi rami che non possono funzionare.
Forza bruta
Prova ogni risposta possibile. È sempre corretta, ma spesso molto troppo lenta (2ⁿ sottoinsiemi, n! ordinamenti).
Scegliere una tecnica: correttezza, efficienza e strutture dati
| Tecnica | Si usa quando | Esempio | Tempo tipico |
|---|---|---|---|
| Forza bruta | l'input è piccolissimo | provare tutte le password di 3 cifre | spesso 2ⁿ o n! |
| Divide et impera | le parti sono indipendenti | ricerca binaria, merge sort | O(log n), O(n log n) |
| Greedy | una buona scelta locale è dimostrata sicura | scelta di attività, resto | O(n log n) |
| Programmazione dinamica | i sottoproblemi si ripetono | resto con monete, cammini minimi | dimensione della tabella |
| Backtracking | ricerca con regole | labirinto, Sudoku | esponenziale, ma con potatura |
Giustificala
Correttezza: mostra che l'algoritmo si ferma sempre e dà l'output giusto (un invariante di ciclo, una dimostrazione o test sui casi limite). Efficienza: conta i passi al crescere di n (Big O) e confrontali con altri metodi.
Le strutture dati aiutano
Array per le tabelle (DP), pile per il backtracking (ricordano dove tornare), code per la ricerca livello per livello. Un albero binario memorizza i dati in modo che ogni nodo abbia al massimo due figli; in un albero binario di ricerca le chiavi più piccole vanno a sinistra e quelle più grandi a destra, così la ricerca dimezza il lavoro a ogni livello, proprio come la ricerca binaria.
Prova tu: monete e gioco dell'indovino
- Gioca con un amico a indovinare un numero da 1 a 100. Chiedi sempre del numero a metà. Riesci a vincere sempre in 7 domande? (2⁷ = 128.)
- Con monete 1, 3, 4, scrivi su carta la tabella DP per le somme da 0 a 10. Dove sbaglia il greedy?
- Apri l'ultimo passo 3D. Prova monete 1, 7, 10 e somma 14. Il greedy dà 10 + 1 + 1 + 1 + 1; la DP dà 7 + 7.
- Scrivi un elenco di passi per "trovare il numero più piccolo di una lista" e provalo su 5, 5, 5 e su un solo numero.
Formule e definizioni chiave
- Specifica = input + output + condizioni
- Dimezzamento: circa log₂ n passi (16 → 4, 1024 → 10)
- DP del resto: best[0] = 0; best[a] = 1 + min best[a - c]
- Divide et impera = dividi + risolvi + combina
- Il greedy è veloce ma va dimostrato ottimale
Esempi svolti
1. Scrivi una specifica e un elenco di passi per trovare il più grande di n numeri.
Input: n ≥ 1 numeri. Output: il più grande. Passi: 1. migliore ← primo numero. 2. Per ogni altro numero x: se x > migliore, migliore ← x. 3. Restituisci migliore. Per 4, 9, 2, 7, 12, 5, 10, 3 l'output è 12 dopo 7 confronti.
2. Quante domande servono con il dimezzamento per trovare un numero da 1 a 1000?
Ogni domanda dimezza l'intervallo: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Sono 10 domande (2¹⁰ = 1024 ≥ 1000).
3. Paga 87 in modo greedy con monete 50, 20, 10, 5, 2, 1.
50 (restano 37), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 monete.
4. Riempi la tabella DP per monete 1, 3, 4 fino alla somma 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Attività (inizio-fine): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Scegli il maggior numero di attività che non si sovrappongono.
Greedy per fine più vicina: A (finisce alle 11), poi C (inizia alle 11, finisce alle 13), poi E (inizia alle 13). 3 attività: A, C, E.
6. Pianifica top-down: un programma che dice a una classe la media dei voti e lo studente migliore.
Livello 1: leggere i dati → calcolare → stampare. Livello 2: leggere nomi e voti in liste; calcolare totale e media; trovare il voto massimo e il suo nome; stampare entrambi. Poi ogni pezzo si programma e si collauda bottom-up.
Errori comuni
- Iniziare a programmare prima di dichiarare input e output. Molti 'bug' sono in realtà una specifica poco chiara.
- Credere che il greedy sia sempre ottimale. Funziona solo se lo puoi dimostrare (le monete 1, 3, 4 lo smentiscono).
- Usare la ricerca binaria su una lista non ordinata. Il dimezzamento richiede dati ordinati.
- Confondere la DP con il divide et impera. La DP serve per sottoproblemi che si sovrappongono e si salvano; il divide et impera divide in parti indipendenti.