[Algoritmi] Togliere la ricorsione [c++] [RISOLTO VIC+APA!]

[apatriarca]

Consideravo \(m\) costante nell'analisi.. Direi che con una piccola modifica puoi comunque restituire anche il numero di possibili combinazioni. Devi semplicemente contare quanti percorsi diversi ti hanno portato ad un particolare stato.

[Giova411]

Questa "piccola modifica" mi sta facendo andare al manicomio APA!!! = (
Devo memorizzare i modi diversi ed ho pensato ad una DFS, cosa ne pensi?
La ricorsione la posso levare dalla cosidette o me la devo tenere?
L'array dove memorizzo il risultato, diciamo pure il C[n] per capirci, lo riempo benino (FORSE) ma poi sommo il risultato della ricorsione che "sballa" il risultato...

PS: da google me lo scordo di lavorare..... pure se gli scrivo in pseudocodice mi menano pure

[Giova411]

Testo nascosto, fai click qui per vederlo

APA non mi scrivere la soluzione in Haskell o Python o Ruby come facevi in passato se no mi butto dalla finestra!!!!

[apatriarca]

No.. ora sono al lavoro per cui non tempo di scrivere proprio alcuna soluzione.. Ripensandoci comunque, credo che in realtà il numero di stati possano anche essere maggiori del numero di stringhe. Ne sono anzi abbastanza sicuro (basta prendere un dizionario tipo "a, aa, aaa, aaaa"). Il numero massimo dovrebbe essere il numero di caratteri totali nel dizionario più due.

Considera i seguenti casi:
1. Da uno stato se ne possono creare due o più. Per esempio, nello stato iniziale potresti avere più di una sottostringa con la stessa iniziale. Se \(n\) è il numero di percorsi con cui sei arrivato allo stato precedente, allora devi copiare questo numero in ognuno degli stati figli successivi.
2. Più di uno stato si fondono allo stesso stato. Per esempio quando finisci più di una sottostringa. Questo nuovo stato sarà raggiungibile percorrendo un numero di percorsi uguale alla somma dei percorsi.
3. Se invece c'è uno stato che si trasforma in un altro che non è raggiunto da altri stati allora il numero di percorsi sarà costante. Per esempio se ti trovi all'interno di una singola sottostringa.

[vict85]

Sia

• \(\displaystyle S \) la stringa ce vuoi testare.
• \(\displaystyle D[i] \) l'elementi \(\displaystyle i \)-esimo del dizionario.
• \(\displaystyle M(i) \) il numero di modi in cui puoi scrivere la sottostringa \(\displaystyle S[0:i-1] \) con elementi del dizionario, pongo \(\displaystyle M(0)=1 \) e \(\displaystyle M(i) =0 \) per \(\displaystyle i<0 \).
• \(\displaystyle \ell[i] \) la lunghezza della parola \(\displaystyle i \)-esima del dizionario.
• \(\displaystyle D[i] \ominus_j S \) è la funzione che confronta \(\displaystyle D[i] \) con le ultime \(\displaystyle \ell[i] \) lettere di \(\displaystyle S[0:j-1] \) e restituisce \(\displaystyle 0 \) o \(\displaystyle 1 \) a seconda se sia o meno uguale.

Tu vuoi conoscere \(\displaystyle M(n) \) dove \(\displaystyle n \) è la lunghezza della parola \(\displaystyle S \). Ma risulta che \(\displaystyle M(t) = \sum_i M\bigl(t-\ell[i]\bigr)\cdot \bigl(D[i] \ominus_j S\bigr)\). Nota che se ordini adeguatamente \(\displaystyle D \) puoi limitare i calcoli (e non dimenticarti di testare se \(\displaystyle M\bigl(t-\ell[i]\bigr) \) è uguale a \(\displaystyle 0 \) )

[Giova411]

Ragazzi per "digerire" le vostre dritte mi serve un po' di tempo.
Ad esempio non capisco come poter ordinare le stringhe del dizionario..
Vic tu che sei un esperto di tutti gli standard c++ cosa mi consigli?
Riscrivere da zero quello che stavo provando? (mi riferisco al secondo scritto male)
La funzione che fa il confronto di stringhe pure era cannata?

[Giova411]

\(\displaystyle M(t) = \sum_i M\bigl(t-\ell[i]\bigr)\cdot \bigl(D[i] \ominus_j S\bigr)\)

Vic sono così . Questa è la somma delle chiamate ricorsive? Mettiamo tutto gradualmente in un vettore?
Ma t cosa dovrebbe rappresentare nel tuo ragionamento? (Un indice che muove da sx a dx?)
Mi sto impallando troppo con sto QUIZZZ!!!!

[apatriarca]

Testo nascosto, fai click qui per vederlo

se ti può essere di conforto avevo letto da qualche parte una ricerca che diceva che la capacità a svolgere quiz di questo tipo non era legata al "successo" (nel senso di essere un bravo programmatore e trovare lavoro) in ambito lavorativo.

L'idea nel mio caso era quella di scriversi una classe "Stato" fatta più o meno nel modo seguente:

Codice:

struct Stato {
    int num_stringa;
    int pos;
    int count;
};


num_stringa uguale a -1 può ad esempio rappresentare l'inizio/fine delle sottostringhe. Conviene probabilmente mantenere una stato "costante" uguale a questo inizio/fine in modo da semplificare la "fusione" degli stati. Mantieni a questo punto due vector<Stato> che rappresentano lo stato corrente e quello successivo. Scorri quindi la stringa e "aggiorni" gli stati. Lo stato iniziale si separerà negli stati relativi all'inizio di tutte le sottostringhe che iniziano con quel carattere. Gli stati interni alla sottostringa incrementano pos se il carattere successivo è uguale a quello nella stringa. Se la sottostringa finisce vanno ad incrementare il contatore dello stato iniziale, se la sottostringa continua in modo diverso dalla stringa "muoiono". Alla fine del ciclo di update scambi i due vector usando probabilmente qualcosa come std::move. Spero sia più o meno chiara la mia idea.

[Giova411]

Ragazzi grazie per come mi aprite la mente!

Testo nascosto, fai click qui per vederlo

Apa usi gli spoiler come me?!
Vorrei essere nella categoria opposta!!! Beati te e Vic che trovate la soluzione in zero/trenta nano secondi
Altro che colloquio di un'ora... Sono giorni e giorni di colloquio per il sottoscritto, vedendo quanto ci metto a fare un puzzle così!!!

Stavo seguendo l'idea di Vic che mi pare l'abbia risolto con la massima efficenza. Forse ordina pure il dizionario per lunghezza delle stringhe..
Io non ho ancora un codice buono ma diciamo che saprei "stampare" il risultato esatto grazie ad una variabile contatore ma non un vettore e non efficente per nulla...
Dopo vorrei provare l'idea di Apa che mi pare diversa...
Vic hai un codice? Ti avanza qualcosa?

[apatriarca]

Testo nascosto, fai click qui per vederlo

Considera che in quasi tre anni che lavoro non mi è mai capitato di risolvere problemi di questo tipo. Se so risolvere questi problemi è più che altro perché frequento forum in cui studenti fanno questo genere di domande da quasi 15 anni. Ovviamente all'inizio ero anche io come te, ma continuando a vedere soluzioni tutto diventa routine. E ho avuto la fortuna di incontrare buoni maestri (principalmente online). Uso lo spoiler perché tutto questo discorso è un po' OT..