Bitstring e combinatoria
Salve a tutti! Sono da poco arrivato qui sul forum, e già sono disperato per un esercizio dell'esame di Matematica Discreta che dovrò dare questo Lunedì che verrà. C'è qualcuno che mi può aiutare a capire come risolvere passo passo i quesiti richiesti? Ecco qua la traccia:
Quanti bit string di lunghezza 55 ci sono tale che:
a.) il bit string ha esattamente quarantanove 0 oltre si deve avere che il bit string
corrispondente alle prime trenta posizione contiene almeno ventotto 0 e il bit string corrispondente
alle ultimi venti posizioni contiene al massimo due 1.
b.) il bit string corrispondente alle prime dieci posizioni ha esattamente sei 0 e il bit string
corrispondente alle ultime ventisette posizioni contiene lo string 1001100 come sotto-string.
In particolare, mi blocco sul da farsi quando ci sono le parole "al minimo" e "al massimo" e quando si tratta di sottostringhe.
Quanti bit string di lunghezza 55 ci sono tale che:
a.) il bit string ha esattamente quarantanove 0 oltre si deve avere che il bit string
corrispondente alle prime trenta posizione contiene almeno ventotto 0 e il bit string corrispondente
alle ultimi venti posizioni contiene al massimo due 1.
b.) il bit string corrispondente alle prime dieci posizioni ha esattamente sei 0 e il bit string
corrispondente alle ultime ventisette posizioni contiene lo string 1001100 come sotto-string.
In particolare, mi blocco sul da farsi quando ci sono le parole "al minimo" e "al massimo" e quando si tratta di sottostringhe.
Risposte
[xdom="vict85"]Il [regolamento]1_4[/regolamento] prevede un tentativo da parte tua.[/xdom]
Al massimo due 1 vuol dire che non possiede 1, che ne possiede uno oppure che ne possiede due. Insomma dividi nei tre casi e somma.
Al massimo due 1 vuol dire che non possiede 1, che ne possiede uno oppure che ne possiede due. Insomma dividi nei tre casi e somma.
Perdonatemi, come potete vedere sono un novizio e non ho ancora letto completamente il regolamento.
Alla fine, comunque, sono riuscito a risolvere il primo punto, attraverso tutte le combinazioni, che si sono rivelate esatte (è uscito il giusto risultato); i dubbi che ho riguardano invece il secondo punto: ho provato a seguire lo stesso ragionamento logico delle combinazioni precedenti, spostando sempre la sottostringa di un posto e calcolando i posti che rimanevano, ma i risultati sono questa volta sballati: avete qualche suggerimento?
Alla fine, comunque, sono riuscito a risolvere il primo punto, attraverso tutte le combinazioni, che si sono rivelate esatte (è uscito il giusto risultato); i dubbi che ho riguardano invece il secondo punto: ho provato a seguire lo stesso ragionamento logico delle combinazioni precedenti, spostando sempre la sottostringa di un posto e calcolando i posti che rimanevano, ma i risultati sono questa volta sballati: avete qualche suggerimento?
Ma i posti che rimangono son sempre venti ... per ognuna delle ventuno posizioni della sottostringa ...
"axpgn":
Ma i posti che rimangono son sempre venti ... per ognuna delle ventuno posizioni della sottostringa ...
E appunto per questo non ho ben chiaro come procedere
Ma come non ti è chiaro?
Hai $27$ posti, ok?
Primo caso: i primi sette posti sono occupati in modo fisso e gli altri venti possono assumere $2^20$ combinazioni, ok?
Secondo caso: uguale al primo. I posti dal $2$ all'$8$ sono occupati in modo fisso, ne rimangono venti che possono assumere due valori per un totale di $2^20$ combinazioni.
Terzo caso, quarto caso, ecc. fino al ventunesimo: tutti uguali al primo!
Chiaro?
Questo pezzo è sistemato, ti rimane il resto ...
Cordialmente, Alex
Hai $27$ posti, ok?
Primo caso: i primi sette posti sono occupati in modo fisso e gli altri venti possono assumere $2^20$ combinazioni, ok?
Secondo caso: uguale al primo. I posti dal $2$ all'$8$ sono occupati in modo fisso, ne rimangono venti che possono assumere due valori per un totale di $2^20$ combinazioni.
Terzo caso, quarto caso, ecc. fino al ventunesimo: tutti uguali al primo!
Chiaro?
Questo pezzo è sistemato, ti rimane il resto ...
Cordialmente, Alex
E' proprio il resto che mi spaventa: tra le soluzioni del prof (che ho controllato dopo milioni di tentativi senza un risultato), è praticamente evidenziato come io debba riscrivere la sottostringa più volte per trovare le combinazioni, tuttavia non riesco a capire il perchè!
In effetti hai ragione, facendo come ho detto ti ritrovi con molti doppioni ... 
Sorry ma al momento non mi vien niente di "semplice" ...
Sorry ma al momento non mi vien niente di "semplice" ...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo