[EX] Problema combinatoria
Sono alcuni giorni che mi sto arrovellando su un problema molto simile hai problemi del lancio della monetina...
Se io ho 6 eventi successivi che mi possono dare 2 esiti distinti, 0 e 1, so che avrò 64 possibili sequenze di tali eventi (2^6). Adesso arriva il bello...
1. Come faccio a sapere quante sequenze contengono 4 o più esiti 1?
2. Come faccio a sapere quante sono le sequenze che contengono 4 o più esiti 1 con max 3 eventi con esito 1 consecutivi?
3. Come faccio a sapere quante sono le sequenze che raggiungono il 4° evento con esito 1 non superando i 3 eventi con esito 1 consecutivi?
4. Come faccio a sapere quante sono le sequenze che contengono esattamente 4 eventi con esito 1 senza superare i 3 eventi con esito 1 consecutivi)
Le risposte a queste domande io le ho già trovate creandomi tutte le sequenze e spulciandole posso dirvi che:
La risposta alla domanda 1 è 22. Cioé:
001111 100111 110101 111011
010111 101011 110110 111100
011011 101101 110111 111101
011101 101110 111001 111110
011110 101111 111010 111111
011111 110011
La risposta alla domanda 2 è 14. Cioé:
010111 101101 110111
011011 101110 111001
011101 110011 111010
100111 110101 111011
101011 110110
La risposta alla domanda 3 è 15. Cioé:
010111 101101 110110
011011 101110 110111
011101 101111 111001
100111 110011 111010
101011 110101 111011
P.S.: Si aggiunge solo una colonna, 101111, perchè raggiunge il 4°evento con esito 1 al 5° evento senza superare 3 eventi con esito 1 consecutivi,anche se successivamente li supera per il quesito 3 questa sequenza deve essere considerata.
La risposta alla domanda 4 è 12. Cioé:
010111 101011 110101
011011 101101 110110
011101 101110 111001
100111 110011 111010
La domanda è... Con numeri cosi piccoli l' ho potuto fare creandomi tutte le sequenze e cercando quelle che rispettavano i criteri. Ma pensiamo se la domanda fosse stata 15 eventi con 8 con esito 1 e con max 6 eventi consecutivi. Avrei dovuto creare 32768 sequenze e tra queste cercare quali rispettavano i criteri...
Quindi, secondo voi esiste un modo per ricavare le risposte alle mie domande senza creare fisicamente tutte le sequenze?
Se io ho 6 eventi successivi che mi possono dare 2 esiti distinti, 0 e 1, so che avrò 64 possibili sequenze di tali eventi (2^6). Adesso arriva il bello...
1. Come faccio a sapere quante sequenze contengono 4 o più esiti 1?
2. Come faccio a sapere quante sono le sequenze che contengono 4 o più esiti 1 con max 3 eventi con esito 1 consecutivi?
3. Come faccio a sapere quante sono le sequenze che raggiungono il 4° evento con esito 1 non superando i 3 eventi con esito 1 consecutivi?
4. Come faccio a sapere quante sono le sequenze che contengono esattamente 4 eventi con esito 1 senza superare i 3 eventi con esito 1 consecutivi)
Le risposte a queste domande io le ho già trovate creandomi tutte le sequenze e spulciandole posso dirvi che:
La risposta alla domanda 1 è 22. Cioé:
001111 100111 110101 111011
010111 101011 110110 111100
011011 101101 110111 111101
011101 101110 111001 111110
011110 101111 111010 111111
011111 110011
La risposta alla domanda 2 è 14. Cioé:
010111 101101 110111
011011 101110 111001
011101 110011 111010
100111 110101 111011
101011 110110
La risposta alla domanda 3 è 15. Cioé:
010111 101101 110110
011011 101110 110111
011101 101111 111001
100111 110011 111010
101011 110101 111011
P.S.: Si aggiunge solo una colonna, 101111, perchè raggiunge il 4°evento con esito 1 al 5° evento senza superare 3 eventi con esito 1 consecutivi,anche se successivamente li supera per il quesito 3 questa sequenza deve essere considerata.
La risposta alla domanda 4 è 12. Cioé:
010111 101011 110101
011011 101101 110110
011101 101110 111001
100111 110011 111010
La domanda è... Con numeri cosi piccoli l' ho potuto fare creandomi tutte le sequenze e cercando quelle che rispettavano i criteri. Ma pensiamo se la domanda fosse stata 15 eventi con 8 con esito 1 e con max 6 eventi consecutivi. Avrei dovuto creare 32768 sequenze e tra queste cercare quali rispettavano i criteri...
Quindi, secondo voi esiste un modo per ricavare le risposte alle mie domande senza creare fisicamente tutte le sequenze?
Risposte
Rispondo alla tua prima domanda. Anche perchè è la più semplice.....
Per troavre quante sono le sequenze con almeno 4 esiti, devi sommare le sequenze con 6, 5 e 4 esiti.
Con 6 esiti ce n'è una sola.
Con 5 esiti $(6!)/(5!) = 6$
Con 4 esiti $(6!)/[(4!)*(2!)] = 15$
$1+6+15=22$
Per le altre ci penserò....
Per troavre quante sono le sequenze con almeno 4 esiti, devi sommare le sequenze con 6, 5 e 4 esiti.
Con 6 esiti ce n'è una sola.
Con 5 esiti $(6!)/(5!) = 6$
Con 4 esiti $(6!)/[(4!)*(2!)] = 15$
$1+6+15=22$
Per le altre ci penserò....
"superpippone":
Rispondo alla tua prima domanda. Anche perchè è la più semplice.....
Per troavre quante sono le sequenze con almeno 4 esiti, devi sommare le sequenze con 6, 5 e 4 esiti.
Con 6 esiti ce n'è una sola.
Con 5 esiti $(6!)/(5!) = 6$
Con 4 esiti $(6!)/[(4!)*(2!)] = 15$
$1+6+15=22$
Per le altre ci penserò....
Nella tua risposta se non sbaglio c' è anche la risposta alla mia terza domanda...
Con 4 esiti $(6!)/[(4!)*(2!)] = 15$
Giusto??? O è solo un caso che coincidono???
Ciao.
No è solo un caso che coincidono.
Le mie 15 erano le sequenze con 4 esiti 1, indipendentemente dal fatto se fossero o meno consecutivi.
Nelle tue 15 c'è anche una sequenza con 5 esiti 1.
Per quanto riguarda la domanda 4, ragionandoci un po', alle 15 sequenze utili basta togliere quelle con i 4 esiti 1 consecutivi, ovvero quelle che li hanno nelle posizioni da 1 a 4, da 2 a 5, e da 3 a 6.
15 - 3 = 12.
Certo questo metodo empirico va bene per pochi esiti, con tanti e più complicato...
No è solo un caso che coincidono.
Le mie 15 erano le sequenze con 4 esiti 1, indipendentemente dal fatto se fossero o meno consecutivi.
Nelle tue 15 c'è anche una sequenza con 5 esiti 1.
Per quanto riguarda la domanda 4, ragionandoci un po', alle 15 sequenze utili basta togliere quelle con i 4 esiti 1 consecutivi, ovvero quelle che li hanno nelle posizioni da 1 a 4, da 2 a 5, e da 3 a 6.
15 - 3 = 12.
Certo questo metodo empirico va bene per pochi esiti, con tanti e più complicato...
"pololo84":
Quindi, secondo voi esiste un modo per ricavare le risposte alle mie domande senza creare fisicamente tutte le sequenze?
Mi sembrano domande un po troppo specifiche, sinceramente se dovessi risolvere utilizzerei 4 righe di codice.
"Umby":
[quote="pololo84"]
Quindi, secondo voi esiste un modo per ricavare le risposte alle mie domande senza creare fisicamente tutte le sequenze?
Mi sembrano domande un po troppo specifiche, sinceramente se dovessi risolvere utilizzerei 4 righe di codice.[/quote]
Potrebbe andare tu che linguaggio avresti in mente e come svilupperesti la cosa???
Utilizzo il linguaggio meno indicato per esercizi simili: il cobol.
Ma solo e solamente perchè lo conosco bene, e quindi mi viene più facile.
Nel caso che hai menzionato, (6 elementi), ho generato una tabella a due dimensioni dove da un lato è presente la frequenza del numero "1" (cha va da 0 a 6), e dall'altra il numero massimo di consecutività.
Osservando questa tabella, troverai le soluzioni ai tuoi quesiti in modo veloce.
Ma solo e solamente perchè lo conosco bene, e quindi mi viene più facile.
Nel caso che hai menzionato, (6 elementi), ho generato una tabella a due dimensioni dove da un lato è presente la frequenza del numero "1" (cha va da 0 a 6), e dall'altra il numero massimo di consecutività.
Osservando questa tabella, troverai le soluzioni ai tuoi quesiti in modo veloce.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo