Richiesta di aiuto sugli insiemi e sottoinsiemi
Salve a tutti , mi sono iscritto proprio adesso e posto subito un problema che mi assilla da diversi mesi riguardante gli insiemi su cui purtroppo non sono per niente ferrato.
Si tratta di questo :
Dato un Insieme A di "n" elementi (si dice cardinalità ?) , contenente i numeri da 1 a n ed S SottoInsiemi di "x" elementi , ad esempio S01,S02,S03,S04 .......SN che contengono ciascuno - in modo assolutamente casuale - una parte diversa di A, come faccio a trovare il minor numero di sottoinsiemi tali che combinati fra loro mi diano tutti i numeri dell'insieme A e cioè la sequenza completa da 1 a n ?
E' anche certo che ci sono diverse combinazioni di sottoinsiemi che soddisfano la mia richiesta, infatti operando con penna, carta e .... cervello - relativamente all'esempio che scrivo più giù - ne ho trovati alcuni, ma io devo fare un programma che svolga il tutto e non riesco a capire quale possa essere l'algoritmo che risolva il mio problema.
Ho fatto decine e decine di prove ma non ci riesco.
Esempio pratico : A(28) = 01 02 03 04 05 06 07 ................................. 28
S01(13) = 01 02 03 04 05 07 08 11 12 16 17 22 23
S02(13) = 01 02 03 04 06 07 09 11 13 16 18 22 24
S03(13) = 01 02 03 05 06 08 09 12 13 17 18 23 24
S04(13) = 01 02 04 05 06 07 10 11 14 16 19 22 25
S05(13) = 01 03 04 05 06 08 10 12 14 17 19 23 25
S06(13) = 02 03 04 05 06 09 10 13 14 18 19 24 25
S07(13) = 01 02 04 07 08 09 10 11 15 16 20 22 26
S08(13) = 01 03 05 07 08 09 10 12 15 17 20 23 26
S09(13) = 02 03 06 07 08 09 10 13 15 18 20 24 26
S10(13) = 04 05 06 07 08 09 10 14 15 19 20 25 26
S11(13) = 01 02 04 07 11 12 13 14 15 16 21 22 27
S12(13) = 01 03 05 08 11 12 13 14 15 17 21 23 27
S13(13) = 02 03 06 09 11 12 13 14 15 18 21 24 27
S14(13) = 04 05 06 10 11 12 13 14 15 19 21 25 27
S15(13) = 07 08 09 10 11 12 13 14 15 20 21 26 27
S16(13) = 01 02 04 07 11 16 17 18 19 20 21 22 28
S17(13) = 01 03 05 08 12 16 17 18 19 20 21 23 28
S18(13) = 02 03 06 09 13 16 17 18 19 20 21 24 28
S19(13) = 04 05 06 10 14 16 17 18 19 20 21 25 28
S20(13) = 07 08 09 10 15 16 17 18 19 20 21 26 28
S21(13) = 11 12 13 14 15 16 17 18 19 20 21 27 28
S22(13) = 01 02 04 07 11 16 22 23 24 25 26 27 28
S23(13) = 01 03 05 08 12 17 22 23 24 25 26 27 28
S24(13) = 02 03 06 09 13 18 22 23 24 25 26 27 28
S25(13) = 04 05 06 10 14 19 22 23 24 25 26 27 28
S26(13) = 07 08 09 10 15 20 22 23 24 25 26 27 28
S27(13) = 11 12 13 14 15 21 22 23 24 25 26 27 28
S28(13) = 16 17 18 19 20 21 22 23 24 25 26 27 28
C'è qualche anima gentile che mi possa risolvere il problema ?
Grazie in anticipo Claudik
Si tratta di questo :
Dato un Insieme A di "n" elementi (si dice cardinalità ?) , contenente i numeri da 1 a n ed S SottoInsiemi di "x" elementi , ad esempio S01,S02,S03,S04 .......SN che contengono ciascuno - in modo assolutamente casuale - una parte diversa di A, come faccio a trovare il minor numero di sottoinsiemi tali che combinati fra loro mi diano tutti i numeri dell'insieme A e cioè la sequenza completa da 1 a n ?
E' anche certo che ci sono diverse combinazioni di sottoinsiemi che soddisfano la mia richiesta, infatti operando con penna, carta e .... cervello - relativamente all'esempio che scrivo più giù - ne ho trovati alcuni, ma io devo fare un programma che svolga il tutto e non riesco a capire quale possa essere l'algoritmo che risolva il mio problema.
Ho fatto decine e decine di prove ma non ci riesco.
Esempio pratico : A(28) = 01 02 03 04 05 06 07 ................................. 28
S01(13) = 01 02 03 04 05 07 08 11 12 16 17 22 23
S02(13) = 01 02 03 04 06 07 09 11 13 16 18 22 24
S03(13) = 01 02 03 05 06 08 09 12 13 17 18 23 24
S04(13) = 01 02 04 05 06 07 10 11 14 16 19 22 25
S05(13) = 01 03 04 05 06 08 10 12 14 17 19 23 25
S06(13) = 02 03 04 05 06 09 10 13 14 18 19 24 25
S07(13) = 01 02 04 07 08 09 10 11 15 16 20 22 26
S08(13) = 01 03 05 07 08 09 10 12 15 17 20 23 26
S09(13) = 02 03 06 07 08 09 10 13 15 18 20 24 26
S10(13) = 04 05 06 07 08 09 10 14 15 19 20 25 26
S11(13) = 01 02 04 07 11 12 13 14 15 16 21 22 27
S12(13) = 01 03 05 08 11 12 13 14 15 17 21 23 27
S13(13) = 02 03 06 09 11 12 13 14 15 18 21 24 27
S14(13) = 04 05 06 10 11 12 13 14 15 19 21 25 27
S15(13) = 07 08 09 10 11 12 13 14 15 20 21 26 27
S16(13) = 01 02 04 07 11 16 17 18 19 20 21 22 28
S17(13) = 01 03 05 08 12 16 17 18 19 20 21 23 28
S18(13) = 02 03 06 09 13 16 17 18 19 20 21 24 28
S19(13) = 04 05 06 10 14 16 17 18 19 20 21 25 28
S20(13) = 07 08 09 10 15 16 17 18 19 20 21 26 28
S21(13) = 11 12 13 14 15 16 17 18 19 20 21 27 28
S22(13) = 01 02 04 07 11 16 22 23 24 25 26 27 28
S23(13) = 01 03 05 08 12 17 22 23 24 25 26 27 28
S24(13) = 02 03 06 09 13 18 22 23 24 25 26 27 28
S25(13) = 04 05 06 10 14 19 22 23 24 25 26 27 28
S26(13) = 07 08 09 10 15 20 22 23 24 25 26 27 28
S27(13) = 11 12 13 14 15 21 22 23 24 25 26 27 28
S28(13) = 16 17 18 19 20 21 22 23 24 25 26 27 28
C'è qualche anima gentile che mi possa risolvere il problema ?
Grazie in anticipo Claudik
Risposte
Ciao,
Penso che questo post stia meglio in Informatica, dato che cerchi un algoritmo
Comunque ti si può dare una mano, non risolvere il problema.
Penso che questo post stia meglio in Informatica, dato che cerchi un algoritmo
Comunque ti si può dare una mano, non risolvere il problema.
Grazie Ham per avermi risposto , in effetti stavo pensando anch'io di spostare il post in "informatica" , però credo che senza le adeguate conoscenze matematiche non si possa creare l'algoritmo.
Del resto il vero problema per me non è l'algoritmo, perchè credo che saprei farlo.
Il mio vero problema è che non so quasi nulla sugli insiemi.
Comunque sono indeciso e credo che lo lascerò ancora qui per qualche giorno, e magari cambiare dopo.
Non credo che lo stesso post possa essere in 2 sezioni diverse del forum o mi sbaglio ?
Ciao
Del resto il vero problema per me non è l'algoritmo, perchè credo che saprei farlo.
Il mio vero problema è che non so quasi nulla sugli insiemi.
Comunque sono indeciso e credo che lo lascerò ancora qui per qualche giorno, e magari cambiare dopo.
Non credo che lo stesso post possa essere in 2 sezioni diverse del forum o mi sbaglio ?
Ciao
se ho capuito bene il testo direi:
dal tuo esempio, hai 28 elementi presi in gruppi di 13: se sei particolarmente fortunato con due sottoinsiemi da 13 "prendi su" al massimo 26 numeri, quindi per "prendere su" gli altri due hai necessariamente bisogno di (almeno) un altro sottoinsieme. il numero minimo di sottoinsiemi da prendere è quindi 3.
ora saresti in grado di generalizzare per sottoinsiemi di x elementi?
(nel testo dove tu scrivi "combinati" io intendo unione tra insiemi)
dal tuo esempio, hai 28 elementi presi in gruppi di 13: se sei particolarmente fortunato con due sottoinsiemi da 13 "prendi su" al massimo 26 numeri, quindi per "prendere su" gli altri due hai necessariamente bisogno di (almeno) un altro sottoinsieme. il numero minimo di sottoinsiemi da prendere è quindi 3.
ora saresti in grado di generalizzare per sottoinsiemi di x elementi?
(nel testo dove tu scrivi "combinati" io intendo unione tra insiemi)
Grazie Hitpareid per il tuo interessamento. Posso dirti che 3 è il numero minimo teorico ma in effetti ce ne vogliono sempre non meno di 4.
Non ho capito la tua domanda : "ora saresti in grado di generalizzare per sottoinsiemi di x elementi? "
Per quanto riguarda "combinati" hai capito perfettamente , anche io intendevo dire "unione tra insiemi"
Non ho capito la tua domanda : "ora saresti in grado di generalizzare per sottoinsiemi di x elementi? "
Per quanto riguarda "combinati" hai capito perfettamente , anche io intendevo dire "unione tra insiemi"
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo