Gioco "Le Scienze" (Maggio 2013)
Sicuramente qualcuno di voi seguirà il mensile "Le Scienza", l'edizione italiana di Scientific American.
Ogni mese viene proposto un gioco, la cui soluzione viene pubblicata il mese successivo.
Il problema di questo mese si riduce a trovare un algoritmo che dati due valori possibili, non generi mai più di tre volte la setessa sequenza.
Considerando i valori F ed M, vi faccio qualche esempio di sequenze accettabili e non.
FFF non accettabile
FFM accettabile
MMF MMF MMF non accettabile
MMF MMF MFF accettabile
MMF MMF MMM non accettabile (Tripla ripetizione finale della M)
FMF FMF FMF FMM non accettabile, se la riscriviamo diversamente infatti: (F MFF MFF MFF MM) c'e una tripla ripetizione
La regola deve essere una regola generale, ed indipendente dalla lunghezza delle sequenze. Qualche idea su come approcciare il problema? Gli informatici saranno a loro agio con questo problema.
Ogni mese viene proposto un gioco, la cui soluzione viene pubblicata il mese successivo.
Il problema di questo mese si riduce a trovare un algoritmo che dati due valori possibili, non generi mai più di tre volte la setessa sequenza.
Considerando i valori F ed M, vi faccio qualche esempio di sequenze accettabili e non.
FFF non accettabile
FFM accettabile
MMF MMF MMF non accettabile
MMF MMF MFF accettabile
MMF MMF MMM non accettabile (Tripla ripetizione finale della M)
FMF FMF FMF FMM non accettabile, se la riscriviamo diversamente infatti: (F MFF MFF MFF MM) c'e una tripla ripetizione
La regola deve essere una regola generale, ed indipendente dalla lunghezza delle sequenze. Qualche idea su come approcciare il problema? Gli informatici saranno a loro agio con questo problema.
Risposte
Potresti spostarla nella sezione "informatica" se lo ritieni più opportuno.
Ciao,
potresti riportare il testo esatto scritto sulla rivista? Perchè gli esempi che hai proposto per me non sono corretti.
questo non è vero, perchè mai più di tre, vuol dire che la sequenza di tre elementi uguali è valida.
FFFF non è accettabile.
FFF invece sì.
Poi anche le definizione di sequenza è ambigua nei tuoi esempi.
potresti riportare il testo esatto scritto sulla rivista? Perchè gli esempi che hai proposto per me non sono corretti.
"Flamber":
considerando i valori F ed M, vi faccio qualche esempio di sequenze accettabili e non.
FFF non accettabile
FFM accettabile
questo non è vero, perchè mai più di tre, vuol dire che la sequenza di tre elementi uguali è valida.
FFFF non è accettabile.
FFF invece sì.
Poi anche le definizione di sequenza è ambigua nei tuoi esempi.
no, ok allora ho sbalgiato, il massimo sono 2 sequenza uguali consecutive.
Cosa c'è di ambiguo?
Cosa c'è di ambiguo?
Il modo in cui viene generata la sequenza deve in qualche modo dipendere da un input oppure, ad esempio, basta che generi una sequenza avente una lunghezza (qualunque) data che rispetti il requisito di non avere nessuna sequenza di 4 o più caratteri uguali e consecutivi ?
Deve essere un algoritmo che generi casualmente una sequenza, ed analizzi, dopo l'aggiunta di ogni lettera, che non ci sia ripetizione di una stessa sequenza, lunga per quanto sia.
Il numero di iterazioni, non è noto a prescindere, quindi deve aggiungere lettere, controllando ogni volta che il criterio sia rispettato, finchè non lo ai ferma.
Il numero di iterazioni, non è noto a prescindere, quindi deve aggiungere lettere, controllando ogni volta che il criterio sia rispettato, finchè non lo ai ferma.
Non capisco perché negli esempi che hai fatto hai raggruppato le lettere a 3 a 3.
Adesso ti dico come ho interpretato il problema, così mi dici se è giusto:
Abbiamo due "cifre", diciamo M ed F.
Dobbiamo costruire un algoritmo che, fissata la lunghezza totale della stringa, restituisca una stringa in cui ho la seguente proprietà: ogni sua sottostringa non è ripetuta per tre volte consecutive (cioè senza altre lettere in mezzo).
Ad esempio:
MFMMFM è ok
FFMFMMFMMFMM no, perché la sottostringa MFM si ripete per tre volte consecutive
FFMFMMFMFMFMFM no, perché la sottostringa FM si ripete per tre (anche quattro) volte consecutive.
FFMMMF no, perché la sottostringa M si ripete per tre volte consecutive.
Ultimo dubbio: l'algoritmo deve restituire una sola stringa, oppure tutte le stringhe valide possibili, oppure un certo numero di stringhe valide?
Adesso ti dico come ho interpretato il problema, così mi dici se è giusto:
Abbiamo due "cifre", diciamo M ed F.
Dobbiamo costruire un algoritmo che, fissata la lunghezza totale della stringa, restituisca una stringa in cui ho la seguente proprietà: ogni sua sottostringa non è ripetuta per tre volte consecutive (cioè senza altre lettere in mezzo).
Ad esempio:
MFMMFM è ok
FFMFMMFMMFMM no, perché la sottostringa MFM si ripete per tre volte consecutive
FFMFMMFMFMFMFM no, perché la sottostringa FM si ripete per tre (anche quattro) volte consecutive.
FFMMMF no, perché la sottostringa M si ripete per tre volte consecutive.
Ultimo dubbio: l'algoritmo deve restituire una sola stringa, oppure tutte le stringhe valide possibili, oppure un certo numero di stringhe valide?
Se si ragiona per sottostringhe di numerosità qualunque, tale esempio non è valido:
le sottostringhe di dimensione $1$ di $M$ sono $4$ quindi non accettabile.
Per questo penso abbia suddiviso a tre a tre.
Se non si riporta il testo esatto, si possono interpretare in troppi modi.
Si potrebbe anche pensare che non si possa generare una sequenza non più di tre volte sia in sottosequenza che in iterazione.
Cioè che creata una sequenza sia controllato che ogni sottosequenza sia valida, che ogni sequenza sia controllata ad ogni generazione che quelle passate non siano mai state create. Quindi fare un controllo in due dimensioni.
"milizia96":
MFMMFM è ok
le sottostringhe di dimensione $1$ di $M$ sono $4$ quindi non accettabile.
Per questo penso abbia suddiviso a tre a tre.
Se non si riporta il testo esatto, si possono interpretare in troppi modi.
Si potrebbe anche pensare che non si possa generare una sequenza non più di tre volte sia in sottosequenza che in iterazione.
Cioè che creata una sequenza sia controllato che ogni sottosequenza sia valida, che ogni sequenza sia controllata ad ogni generazione che quelle passate non siano mai state create. Quindi fare un controllo in due dimensioni.
"hamming_burst":
le sottostringhe di dimensione $1$ di $M$ sono $4$ quindi non accettabile.
Per questo penso abbia suddiviso a tre a tre.
Allora anche l'esempio che fa lui:
MMF MMF MFF accettabile
sarebbe in realtà non accettabile.
Io dico sottostringhe consecutive nel senso che in mezzo tra loro non compare nient'altro, sono ripetute una dopo l'altra senza interruzioni.
Comunque aspettiamo Flamber e vediamo che dice.
Appena posso domani prendo il giornale e lo scrivo precisamente, riportare tutto il testo è impossibile perchè è lungo due pagine, dato che è inserito all'interno di un contesto di una storiella.
"Flamber":
Appena posso domani prendo il giornale e lo scrivo precisamente, riportare tutto il testo è impossibile perchè è lungo due pagine, dato che è inserito all'interno di un contesto di una storiella.
bene....
il testo effettivamente è molto "vago",
lo si puo' interpretare in tanti modi diversi...
Visto che ho avuto un po' di tempo ho letto la rivista presente in biblioteca. Il problema è il seguente:
trovare la regola per costrutire la massima sequenza che non abbia mai tre sottosequenze ripetute successive.
La storiella fa un esempio di una sequenza già creata e che una regola trova la sottosequenza sbagliata e flippa il valore o meno.
es. ho in input 110110011_ la sottosequenza 110 è presente due volte, nel trattito posso mettere $0$ o $1$. Se $0$ avrò una terza sottosequenza 110, quindi non valida, se invece $1$ avrò la sottosequenza 111, composta dalla tripla $1$ quindi non valida. Il problema sta di trovare la sequenza più lunga di scelte. In questo caso 110110011 è la più lunga (ipotesi).
Quindi non è troppo diverso dal problema scritto da Flamber. L'interpretazione è di generarne una, non validarne mille, ma di trovarne la regola chiusa ed una sua limitazione superiore.
Quindi raggruppare come ha fatto lui è corretto, perchè se ne fissa una tripla valida e si va avanti.
trovare la regola per costrutire la massima sequenza che non abbia mai tre sottosequenze ripetute successive.
La storiella fa un esempio di una sequenza già creata e che una regola trova la sottosequenza sbagliata e flippa il valore o meno.
es. ho in input 110110011_ la sottosequenza 110 è presente due volte, nel trattito posso mettere $0$ o $1$. Se $0$ avrò una terza sottosequenza 110, quindi non valida, se invece $1$ avrò la sottosequenza 111, composta dalla tripla $1$ quindi non valida. Il problema sta di trovare la sequenza più lunga di scelte. In questo caso 110110011 è la più lunga (ipotesi).
Quindi non è troppo diverso dal problema scritto da Flamber. L'interpretazione è di generarne una, non validarne mille, ma di trovarne la regola chiusa ed una sua limitazione superiore.
Quindi raggruppare come ha fatto lui è corretto, perchè se ne fissa una tripla valida e si va avanti.
"hamming_burst":
Se $0$ avrò una terza sottosequenza 110, quindi non valida
Quindi queste sequenze possono apparire anche intervallate da qualche altro carattere? Perché in effetti tra il secondo $110$ e il terzo c'è un carattere $0$ di troppo.
Ma allora anche 110110011 sarebbe sbagliata, perché la sottosequenza $1$ si ripete per ben 6 volte... (e la sottosequenza $0$ per 3 volte).
Ancora non riesco a capire...
EDIT: per favore scrivete cosa intendete per sequenza e per sottosequenza, altrimenti non concludiamo niente.
Inoltre non ho ancora capito l'utilità nel dividere 3 a 3. Per caso le sottosequenze devono avere lunghezza 3?
"milizia96":
[quote="hamming_burst"]Se $0$ avrò una terza sottosequenza 110, quindi non valida
Quindi queste sequenze possono apparire anche intervallate da qualche altro carattere? Perché in effetti tra il secondo $110$ e il terzo c'è un carattere $0$ di troppo.
Ma allora anche 110110011 sarebbe sbagliata, perché la sottosequenza $1$ si ripete per ben 6 volte... (e la sottosequenza $0$ per 3 volte).[/quote]
sai che non l'avevo visto!
vabbè stasera rileggo sta storiella, cmq è ambigua e non c'è chissà che spiegazione od interpretazione che si sperava. Il testo riportato da me o da Flamber è tutto ciò che si conosce.
no, ovviamente le sottosequenze possono ripetersi intervallate da un numero, altrimenti sarebbe impossibile mettere più di 6 cifre.
E' uscita la soluzione?
si la soluzione c'è, appena posso la copio, sono un paio di righe
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo