Esercizi Iterazione su vettore:
- Intervallo di Somma Massima (versione $$O(n^3$$).
- Ottimizzazione versione $$O(n^2)$$, idea: non calcolare le somme da zero.
- Ottimizzazione versione lineare. idea: gli estremi dell’intervallo rispettano specifiche relazioni.
Esercizi Ricorsione:
- Calcolo del Coefficiente Binomiale $$n \choose m$$. Perche la versione con i fattoriali non è ideale.
- Versione Ricorsiva del Coefficiente Binomiale.
- Problemi con la ricorsione, valutazioni ripetute della stessa espressione, soluzione:
- Triangolo di Tartaglia: versione “programmazione dinamica = ricorsione + memorizzazione” della relazione ricorsiva.
Esercizi:
- Completare l’esercizio sulla somma massima nel vettore.
- Data una matrice $$M = m_ij$$ dove esiste un indice di colonna $$k$$ tale che $$m_{ij} = 1$$ se $$j < k$$ e $$m_{ij} = 2$$ se $$j \geq k$$, e date le coordinate di un elemento di M, start = $(p,q)$, riempire la sottomatrice composta dagli elementi di M con valore uguale a quello in M[p][q] con il valore 0.
- Data una stringa (vettore di caratteri terminato con ‘\0’), che contiene un espressione composta da parentesi tonde, scrivere una funzione ricorsiva che verifica se tale espressione ha le parentesi bilanciate e se è ben-formata (le parentesi aperte appaiono sempre prima della corrispondente chiusa).