Newsgroup: it.comp.lang.c++
Titolo: AIUTO ESAMI!!!! VI PREGO !!!! (lunghetto)

Putroppo l'esame di informatica si avvicina ... non che non abbia studiato
... ma il modo in cui lo facciamo non valorizza veramente chi ha studiato
oppure no (test a risposta multipla con 5 min a domanda in cui bisogna
trovare l'errore oppure dire cosa produce un frammento di programma).
Poichè presuppongo di non passare l'esame oppure di non prendere un voto
alto il professore ci dà la possibilità di arrotondare il voto facendo un
progetto .... con la iella che ho mi è capitato l'unico che non so dove
metterci le mani!!!!Eccolo:
PROGETTO 2
Progettare e codificare una classe per calcolare gli anagrammi di una
stringa.
Particolare credito verrà data a chi utilizzerà un dizionario per generare
solo anagrammi di senso compiuto.
COSA DEVO FARE? AIUTO VI PREGO NON SO COME COMINCIARE, COME FACCIO A FARE UN
DIZIONARIO PER GENERARE ANAGRAMMI DI SENSO COMPIUTO??

DIZIONARIO PER GENERARE ANAGRAMMI DI SENSO COMPIUTO??
L'algoritmo per il calcolo degli anagrammi (ricorsivo) e' abbastanza
semplice, per cui ci sorvoliamo.
Per ottenere i soli di senso compiuto, basta creare tutti gli
anagrammi della parola e filtrarli con il dizionario. 
Non ci vedo tutta questa difficolta'.
--
Andrea Laforgia (ICQ 87230455)
http://www.geocities.com/AndreaLaforgia
"ci sono tre tipi di persone nel mondo : quelli che
 sono bravi in matematica e quelli che non lo sono."

Non ci vedo tutta questa difficolta'.
Io credo che invece indicizzerei il dizionario in base ad una
chiave ottenuta ordinando i caratteri della stringa.
In questo modo data la parola si trovano immediatamente tutti
gli anagrammi (senza doverli generare e dover fare una ricerca
per ogni anagramma trovato).
Fra l'altro la cosa in C++ richiederebbe solamente di usare
std::sort sui caratteri della stringa e leggere il dizionario
in una std::map<std::string,std::string> (chiave => parola).
std::map<std::string,std::string> e' forse un po' uno
spreco... (una hash table andrebbe benissimo per questo
scopo e occuperebbe poco piu' del solo dizionario) ma visto
che e' gia' bella e pronta...
Impressionante il fatto che una cosa simile sia classificata
come "progetto".
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 in una std::map<std::string,std::string> (chiave => parola).
Scusa, ma così ad ogni chiave corrisponderebbe una sola parola e non
sarebbero possibili doppioni... e anche usando una std::multimap,
occorrerebbe ogni volta trovare tutte le occorrenze della chiave e le
relative parole associate... a questo punto, sarebbe meglio qualcosa come
std::map<std::string,std::vector<std::string> > // chiave -> serie di parole
Oppure, nel caso l'overhead di std::vector e std::string risultasse troppo
pesante, e comunque considerando la staticità di questa struttura, che viene
creata una sola volta (alla lettura del dizionario), non dovrebbero esserci
problemi nell'utilizzare una soluzione come
std::map<char[],char[][]>
Anche se questa sarebbe certamente più difficile da implementare dato il
livello più basso, sicuramente sarebbe un'eccellente ottimizzazione, data la
completa inutilità in questo particolare caso delle funzioni offerte da
std::string.
Massimo

std::string.
Non credo che le funzioni in piu' di std::string siano
un problema. Con scarsa efficienza intendevo il fatto
che std::multimap deve tenere le chiavi ordinate e
deve tenere separatamente sia la chiave che il valore:
questo porta ad usare algoritmi piu' pesanti e una
occupazione come minimo doppia per ogni parola.


come "progetto".
Gia' :)
Tra l'altro, cercare anagrammi delle parole nel mondo reale puo'
salvarti la vita ;)


 Gia' :)
Mi hanno detto che molte universita' americane hanno progetti semestrali del
tipo "OS kernel" e chicche simili.
Se non sbaglio un certo Torval estese l'idea e ne fece una tesi. E qualche cosa
di piu'. E non era in USA: Helsinki on europalainen kaupungi. Se on Suomessa.
Trad: Helsinki e' una citta' europea. Si trova in Finlandia.
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 per ogni anagramma trovato).
Però, bell'idea.

 wrote in message news:3A884934...@libero.it...

E' un algoritmo abbastanza classico, in realta'. E un ottimo esempio di come sia
assolutamente inutile impazzire per ottimizzare il codice che esegue le varie
permutazioni e la successiva ricerca nel dizionario quando un cambio di
algoritmo, anche se il nuovo algoritmo e' implementato in maniera "lenta" porta
comunque ad un aumento di prestazioni di molti ordini di grandezza!


 
Come ho chiesto ad Andrea Laforgia, potresti farmi un'esempio?
Se ad es. la stringa è "per" come dovrei fare per trovare solo gli
anagrammi di senso compiuto senza usare std::map o algoritmi già pronti
come il sort?
Grazie
Luigi
-- 
Posted from 
smtp6.libero.it
 [193.70.192.127] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG