dal sito della Rowling
dal sito della Rowling
forse sarebbe da combinatoria, ma non so la soluzione (non ho ancora voglia di fare i conti)
per entrare in una stanza segreta devo cliccare su tutti i 5 mattoni A B C D E in sequenza continua con ordine ben definito e una sola volta, ma la sequenza non deve essere "pulita" (prima o dopo si possono cliccare altri mattoni), basta che tale ordine venga completato ad un certo punto. Ad es. se la successione e' ABCDE e clicco AABEABCDE riesco ad entrare, mentre con ABCDAE no
Quanto e' lunga la minima sequenza di click tale per cui sono sicuro di riuscire ad entrare?
edit: specificato meglio che la sequanza deve essere senza interruzioni in mezzo
per entrare in una stanza segreta devo cliccare su tutti i 5 mattoni A B C D E in sequenza continua con ordine ben definito e una sola volta, ma la sequenza non deve essere "pulita" (prima o dopo si possono cliccare altri mattoni), basta che tale ordine venga completato ad un certo punto. Ad es. se la successione e' ABCDE e clicco AABEABCDE riesco ad entrare, mentre con ABCDAE no
Quanto e' lunga la minima sequenza di click tale per cui sono sicuro di riuscire ad entrare?
edit: specificato meglio che la sequanza deve essere senza interruzioni in mezzo
Ultima modifica di SkZ il 10 apr 2009, 16:35, modificato 1 volta in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
io l'avevo lasciato morire perche' poco dopo mi ero accorto che era piu' semplice di quanto mi era sembrato (non mi ero proprio applicato a risolverlo prima di postarlo)
di base hai 24 sequenze minime forzate (smf d'ora in poi).
Si generano scegliendo una lettera fissa, diciamo A, e poi permuti le altre 4 (4!=24). Poi scrivi 2 volte queste subsequenze ad anello. Le smf si ottengono togliendo tagliando una lettera all'anello (togli una lettera e distendi l'anello)
usi queste sequenze facendo modo da sovrapporre il piu' possibile gli estremi. E si vede che la sovrapposizione massima e' $ ~n-2 $ lettere e si ottiene mettendo assieme le sequenze generate da $ ~n-1 $ lettere poste fisse e ponendo l'ultima nelle 4 posizioni possibili (ricordo che e' una struttura ad anello ergo prima e ultima posizione si equivalgono). es
ABCDEABCD AEBCDA BECDAB CEDABC (ABCDE +AEBCD+ABECD+ABCED)
i raggruppamenti di $ ~n-1 $ smf (d'ora in poi Gsmf) che si possono ottenere sono $ ~(n-2)! $: una lettera la posizioni dopo, una lettera la usi come indice (altrimenti ti ritrovi con n doppioni), ergo ti rimangono $ ~n-2 $ da sistemare
se si potesse fare una sequenza perfetta, in cui le sequenze di n lettere si ripetono tutte e solo una volta, sarebbe lunga $ ~(n-1)+n! $, quindi in questo caso 124
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(2n^2-6n+7)(n-2)! $ caratteri, quindi in questo caso 162
1-2 ripetizioni riesci a eliminarle se si fa attenzioni nelle giunzioni ergo si puo' stimare in 152-157 casi
direi che il valore ci sta'
di base hai 24 sequenze minime forzate (smf d'ora in poi).
Si generano scegliendo una lettera fissa, diciamo A, e poi permuti le altre 4 (4!=24). Poi scrivi 2 volte queste subsequenze ad anello. Le smf si ottengono togliendo tagliando una lettera all'anello (togli una lettera e distendi l'anello)
usi queste sequenze facendo modo da sovrapporre il piu' possibile gli estremi. E si vede che la sovrapposizione massima e' $ ~n-2 $ lettere e si ottiene mettendo assieme le sequenze generate da $ ~n-1 $ lettere poste fisse e ponendo l'ultima nelle 4 posizioni possibili (ricordo che e' una struttura ad anello ergo prima e ultima posizione si equivalgono). es
ABCDEABCD AEBCDA BECDAB CEDABC (ABCDE +AEBCD+ABECD+ABCED)
i raggruppamenti di $ ~n-1 $ smf (d'ora in poi Gsmf) che si possono ottenere sono $ ~(n-2)! $: una lettera la posizioni dopo, una lettera la usi come indice (altrimenti ti ritrovi con n doppioni), ergo ti rimangono $ ~n-2 $ da sistemare
se si potesse fare una sequenza perfetta, in cui le sequenze di n lettere si ripetono tutte e solo una volta, sarebbe lunga $ ~(n-1)+n! $, quindi in questo caso 124
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(2n^2-6n+7)(n-2)! $ caratteri, quindi in questo caso 162
1-2 ripetizioni riesci a eliminarle se si fa attenzioni nelle giunzioni ergo si puo' stimare in 152-157 casi
direi che il valore ci sta'
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
ovvio che non hai capito, manco il mio prof di mate capiva come risolvevo i compiti dato che meta' dei passaggi li facevo a mente (divisioni di ruffini incluse)
la Gsmf sono formate da 1 smf + (n-2) smf tronche di (n-2) caratteri
ergo hai, dato che una smf ha 2n-1 caratteri
$ ~(2n-1)+(n-2)(2n-1 -(n-2))=2n-1+(n-2)(n+1)=n^2+n-3 $
e come vedi c'era un errore nel conto precedente (purtroppo le due formule danno lo stesso risultato per n=5). per questo non ti tornava
quindi
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(n^2+n-3)(n-2)! $ caratteri
sempre $ ~27\cdot 3!=162 $
PS: no, non era perche' sbagliavo i conti che il mio prof non capiva
la Gsmf sono formate da 1 smf + (n-2) smf tronche di (n-2) caratteri
ergo hai, dato che una smf ha 2n-1 caratteri
$ ~(2n-1)+(n-2)(2n-1 -(n-2))=2n-1+(n-2)(n+1)=n^2+n-3 $
e come vedi c'era un errore nel conto precedente (purtroppo le due formule danno lo stesso risultato per n=5). per questo non ti tornava
quindi
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(n^2+n-3)(n-2)! $ caratteri
sempre $ ~27\cdot 3!=162 $
PS: no, non era perche' sbagliavo i conti che il mio prof non capiva
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
e la sequenza ABCED, ad es, dove la metti?
hai solo coperto 5 delle 120 possibili seguenze
hai solo coperto 5 delle 120 possibili seguenze
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Re: dal sito della Rowling
....................................................................................................................SkZ ha scritto:basta che tale ordine venga completato ad un certo punto.
mi sembrava ovvio che per sequenza indicassi sequenza di lettere consecutive
cmq correggo il testo
cmq correggo il testo
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php