Angella Andrea - Italian Blog

Infinita passione per lo sviluppo software !
posts - 133, comments - 216, trackbacks - 9

My Links

News

MIT OpenCourseWare: I'm invested Wikipedia Affiliate Button


Sto leggendo:

Archives

Post Categories

Siti web realizzati

Siti web tecnici

Algoritmica

Algoritmi – Rimuovere i duplicati da un lista

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 ...

posted @ Tuesday, September 7, 2010 12:50 AM | Feedback (2) | Filed Under [ Algoritmica ]

Algoritmi – Determinare il sottoinsieme più grande di intervalli mutuamente non sovrapposti

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...

posted @ Sunday, September 5, 2010 3:33 AM | Feedback (0) | Filed Under [ Algoritmica ]

Algoritmi – Dire se due parole sono anagrammi

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...

posted @ Saturday, September 4, 2010 4:48 PM | Feedback (6) | Filed Under [ Algoritmica ]

Algoritmi – Rimuovere i caratteri duplicati in una stringa

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...

posted @ Saturday, September 4, 2010 3:16 PM | Feedback (39) | Filed Under [ Algoritmica ]

Algoritmi – Invertire una stringa

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...

posted @ Friday, September 3, 2010 12:39 AM | Feedback (5) | Filed Under [ Algoritmica ]

Algoritmi – Determinare dal testo di una rivista se e’ possibile creare una ransom note

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...

posted @ Thursday, September 2, 2010 12:51 AM | Feedback (9) | Filed Under [ Algoritmica ]

DSA and BCL - Unordered List Stress Test

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...

posted @ Sunday, September 28, 2008 12:34 AM | Feedback (3) | Filed Under [ Algoritmica DSA ]

L'importanza di realizzare algoritmi polinomiali

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 ^...

posted @ Saturday, July 12, 2008 12:52 AM | Feedback (0) | Filed Under [ Algoritmica ]

Powered by:
Powered By Subtext Powered By ASP.NET