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

September 2010 Blog Posts

Algoritmi – Somma algebrica di due numeri naturali rappresentati come liste

Problema: Considera di rappresentare un numero attraverso una lista semplice come quella implementata in un precedente post. Ogni elemeneto della lista rappresenta una delle cifre del numero. Le cifre sono memorizzate nell’ordine inverso. Quindi il primo elemento della lista sara’ la cifra delle unita’. Prese due liste che rappresentano due numeri a e b, ritornare una nuova lista che rappresenta il risultato a + b. Inputs: Due liste semplici di interi: a e b Output: Una lista semplice di interi Esempio: Inputs:   a: 6, 5,...

posted @ Tuesday, September 7, 2010 2:51 AM | Feedback (3) |

Algoritmi – N-ultimo elemento di una Single Linked List

Problema: Considerare una Single Linked List di interi. Scrivere un metodo che ritorna il valore dell’elemento distante nth dall’ultimo elemento. Se non esiste sollevare una eccezione. Il codice della struttura dati e’ presente in un precedente post. Input: Un intero (nht) che rappresenta la distanza dall’ultimo elemento della lista Output: Un intero che rappresenta il valore dell’elemento desiderato. Esempio: Lista: 5, 7, 2, 4, 3, 9 Input: 0 Output: 9 Input: 1 Output: 3 Input: 5...

posted @ Tuesday, September 7, 2010 2:01 AM | Feedback (0) |

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 – Ruotare una immagine di 90 gradi in senso orario

Problema: Abbiamo una matrice quadrata (N x N) di interi che rappresenta una immagine. Scrivere un algoritmo che ruota l’immagine di 90 gradi in senso orario. Input: Una matrice quadrata (N x N) di interi. Output: Una matrice quadrata (N x N) di interi. Esempio: Input: 1   2   3   4   5   6   7   8  9  10  11  12  13  14  15  16 17  18  19  20  21  22  23  24 25  26  27  28  29 ...

posted @ Saturday, September 4, 2010 6:47 PM | Feedback (4) |

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 se in una stringa tutti i caratteri sono diversi tra loro

Problema 1: Determinare se in una stringa tutti i caratteri sono diversi tra loro. Problema 2: Risolvere il problema 1 senza usare strutture dati aggiuntive. Input: Una stringa Output: Un booleano Il mio ragionamento: Sfrutto un vettore di booleani con un numero di elementi pari a tutti i possibili caratteri. Itero la stringa e per ogni carattere setto il corrispondente elemento del vettore a true. Se prima di settare lo trovo gia’ a true significa che quello e’ un carattere ripetuto e restituisco subito false. Se si termina...

posted @ Thursday, September 2, 2010 11:44 PM | Feedback (2) |

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 ]

Algoritmi – Calcolare il minimo di un array ordinato ruotato

Problema: Dato un array di interi ordinato in modo crescente ma ruotato, calcolare il valore minimo. Input: Un vettore di interi. Output: Un intero che rappresenta il minimo elemento del vettore. Esempio: Dato l’array ordinato ruotato: 20, 30, 50, 108, 6, 8, 9, 19 il valore minimo e’ 6 Il mio ragionamento: Fare una scansione totale dell’array avrebbe complessita’ O(n) e non sfrutterebbe l’informazione aggiuntiva che l’array e’ ordinato e ruotato. Si puo’ allora pensare di fare una specie di ricerca binaria con complessita’ O(log(n))...

posted @ Wednesday, September 1, 2010 10:34 PM | Feedback (4) |

Powered by:
Powered By Subtext Powered By ASP.NET