Algoritmica
Problema: Considerare una semplice classe che implementa una SingleLinkedList non ordinata di interi. Realizzare un metodo per rimuovere tutti i duplicati dalla lista. Input: Niente Output: Niente. Internamente gli elementi duplicati saranno rimossi dalla lista. Esempio: Lista iniziale: 1, 1, 1, 1, 3, 4, 5, 3, 5, 1, 2, 1, 2, 3, 4 ,1 , 2, 3, 5, 1, 2, 5, 6, 7, 2, 8, 2, 9, 9 Lista finale: 1, 3, 4, 5, 2, 6, 7, 8, 9 ...
Problema: Dato un insieme I di n intervalli [a, b] con a e b interi determinare il sottoinsieme piu’ grande di intervalli mutuamente non sovrapposti che possono essere selezionati da I. Input: Due vettori di n interi che rappresentano l’insieme I. a = { a0, a1, … } b = { b0, b1, … } Ogni intervallo e’ identificato da un numero intero k. L’intervallo generico k e’ rappresentato dagli estremi a[k] e b[k]. Output: Una lista di interi ordinata (List<int>) che contiene gli identificatori degli intervalli...
Problema: Date due parole (stringhe) dire se sono anagrammi. Input: Due stringhe che rappresentano due parole (spazi esclusi) Output: Un booleano Esempio: Input: “nave” e “vena” Output: true Input: “nave” e “neve” Output: false Il mio ragionamento: Se le due parole hanno un numero di caratteri differenti non possono essere anagrammi. Calcolo il numero di occorrenze di ciascun carattere nella prima parola. Per ogni carattere della seconda parola verifico se ce...
Problema: Rimuovere tutti i caratteri duplicati da una stringa. Gli spazi devono essere preservati. Vincoli: Se si utilizza C++ modificare direttamente il parametro di input senza utilizzare buffer aggiuntivi. Se si utilizza C# ritornare una nuova stringa. In quanto le stringhe sono immutabili, e’ consentito l’utilizzo del metodo ToCharArray() per attenere un buffer su cui lavorare. Input: Una stringa Output: Una stringa Esempio: Input: “Microsoft .Net Framework” Output: “Microsft .Ne Famwk” Il mio ragionamento: Itero il buffer della stringa e costruisco all’inizio di...
Problema: Data una stringa, calcolare e ritornare una nuova stringa con gli stessi caratteri ma in ordine inverso. Esempio: ABCDE Risultato: EDCBA Input: Una stringa. Output: La stringa di input con i caratteri in ordine inverso. Il mio ragionamento: Costruisco un vettore di caratteri lungo quanto la stringa e lo riempio con un semplice ciclo for. La mia soluzione: public static string Reverse(string s) { if (s == null) throw new ArgumentNullException("s"); if (s.Length < 2) return s; char[] vc = new...
Problema 1: Fino ad ora non sapevo cosa fosse una ransom note. Praticamente si tratta di un testo realizzato utilizzando ritagli da una rivista. Dato il testo di una ransom note e il testo della rivista, dire se e’ possibile realizzare la ransom note. Problema 2: Risolvere lo stesso problema ma ritagliando parole invece che singoli caratteri. Input: Testo della ransom note che si vuole creare (stringa). Testo della rivista da cui si vuole ritagliare (stringa). Output: True se...
Come tutti sapete Granville Barnett e Luca del Tongo stanno lavorando alla realizzazione di una libreria open-source di strutture dati e algoritmi (DSA) con lo scopo di arricchire le funzionalità offerte dalla libreria di base del framework 3.5 (BCL). Sono molto interessato all'evoluzione del progetto, per questo ho scaricato l'attuale release 0.6 ed ho iniziato a studiarla attentamente (segnalo anche la presenza di un eBook scritto dagli stessi autori per meglio comprendere gli algoritmi implementati). Sono rimasto piacevolmente colpito dalla pulizia e chiarezza del codice di implementazione e soprattutto dallo sforzo impiegato a mantenere intuitivo l'utilizzo della libreria (molti metodi...
Tutti noi sappiamo quanto sia importante in alcune occasioni trovare un algoritmo polinomiale per risolvere un problema (meglio ancora se lineare o logaritmico). Vorrei sottolineare con un taglio matematico quanta rilevanza può avere questa semplice constatazione. Supponiamo di avere tre algoritmi che risolvono un medesimo problema. Il primo algoritmo ha complessità esponenziale, il secondo ha complessità quadratica e il terzo è lineare. La funzione Ti(n) indica il tempo richiesto dall'algoritmo i-esimo per trovare la soluzione di un problema di dimensione n (in poche parole la complessità dell'algoritmo). Abbiamo quindi: T1( n ) = 2 ^...