Newsgroup: it.hobby.enigmi
Titolo: calcolo...combinatorio?

scusate se riposto questa domanda ma involontariamente era finita sotto un
thread già esistente:
Qualcuno mi saprebbe dire come è possibile ricavare il numero di
combinazioni che rispettano le seguenti caratteristiche?
combinazioni di 6 numeri
compresi tra 1 e 90
tutti diversi tra loro
la cui somma sia X
esempio
superenalotto
il numero di sestine la cui somma sia = 270
Grazie in anticipo
totò

 la cui somma sia X
Non è assolutamente facile. Non hai molto di meglio che contarle con delle
sommatorie annidate, o con un programma (!). Se vuoi solo una stima, ed hai
familiarità con la distribuzione normale, allora puoi supporre che le
estrazioni siano con rimpiazzo. Se Xi è l'esito dell'i-esima estrazione,
allora la distribuzione di X1+X2+..+X6 è approssimabile ad una gussiana, i
cui valori si trovano tabulati. Devi però prima normalizzare i valori,
quindi hai bisogno di media e varianza, che comunque sono semplici in questo
caso (perlomeno credo, le mie nozioni di statistica sono un po'
arrugginite).
Ciao, Silv:o)





.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Provo a risponderti con un esempio. Supponi che X sia 99. Una possibile
combinazione è 14, 15, 16, 17, 18, 19. Questi numeri sono consecutivi e 3 di
loro stanno a "sinistra" e altri 3 a "destra" del numero 16.5, che è dato da
99/6. Qualunque altra combinazione trovi, avrà sempre 3 numeri minori di
16.5 e 3 maggiori di 16.5. In questo caso, comunque tu scelga i 3 numeri a
sinistra, troverai sempre altri 3 numeri a destra per ottenere il valore X,
quindi tutto si riduce a trovare in quanti modi puoi scegliere 3 valori
diversi tra 16. I modi possibili sono 16! / (3!*(16-3)!). Naturalmente se il
numero centrale è più vicino al 90 devi fare il ragionamento dall'altra
parte.
Poi devi considerare i casi in cui non esista una combinazione con numeri
consecutivi, ma con un piccolo studio non dovrebbe essere difficile trovare
una regola.
Ciao
Giorgio

 ore di elaborazione?
Dipende da come è fatto il programma!
Se genera tutte le possibili sestine (sono 600 milioni!) per esempio con dei
cicli nidificati, allora ti basta un vettore a(i) con i che copre il range
minSum...maxSum (15..440) per crearti una tabella valida una volta per
tutte. Per ogni sestina trovata incrementi l'elemento del vettore il cui
indice corrispondente alla somma. Poi ti stampi tutte le componenti ed il
gioco è fatto.
Ecco il programma in basic. E' proprio brute, ma veramente brute, comunque
in un oretta o due dovresti avere i tuoi dati
Sub ContaSestine ()
 Dim a(15 to 450) as long
    For i1=1 to 85
    For i2=i1+1 to 86
    For i3=i2+1 to 87
    For i4=i3+1 to 88
    For i5=i4+1 to 89
    For i6=i5+1 to 90
      s=i1+i2+i3+i4+i5
      a(s)=a(s)+1
    Next
    Next
    Next
    Next
    Next
    Next
    For i=15 to 450
      Print i;a(i)
    Next i
End Sub
Ciao, Silv:o)

 16.5 e 3 maggiori di 16.5.
Perché?
4+17+18+19+20+21 = 99
Silv:o)

 wrote in message
8rs8i9$j2hrk$1...@ID-49224.news.cis.dfn.de...


 Dim a(21 to 525) as long
Sorry, contavo le cinquine
Ciao, Silv:o)

 ha scritto nel messaggio
news:8rs8va$irjrp$1...@ID-49224.news.cis.dfn.de...

Forse..., per eccesso di ottimismo! :-)
Ciao
Giorgio

 semplice. Comunque controllo
Ho controllato. Intanto che me lo studio, lo riporto sperando che gli
interessati non abbiano niente in contrario.
Numbo:
|Consideriamo cinque numeri interi qualsiasi (anche con ripetizione)
|compresi tra 0 e 9; Qual'è la probabilià che la somma di questi cinque
|numeri sia un certo numero x (compreso ovviamente tra 0 e 45).
|qual'è l'equazione che risolve univocamente il problema?
El Filibustero:
|Ciao Numbo, l'espressione della probabilita' varia secondo fasce di
|ampiezza 10, con estremi sovrapposti. Per x=0..9 la probabilita'
|(in centomillesimi) e'
|
|p(x) = (x+4 su 4)  = coeff. binomiale di x+4 su 4 = (x+4)!/(x! 4!)
|
|per x=9..18 si ha    p(x) = (x+4 su 4) - 5 (x-6 su 4)
|
|per x=18..27 si ha  p(x) = (x+4 su 4) - 5 (x-6 su 4) + 10 (x-16 su 4)
|
|In generale, sommando m volte gli interi tra 0 e N si ha la
|probabilita' (espressa in (N+1)^m - esimi) che varia secondo fasce.
|Nella fascia per x che va da hN ad (h+1)N per h=0..m-1 si ha
|
|p(x) = somma{k=0..h} (-1)^k (m su k) (x+m-1-k(N+1) su m-1)
|
Ciao, Silv:o)

 wrote in message
8rsbj9$imt0t$1...@ID-49224.news.cis.dfn.de...


 wrote in message
8rschg$iq08u$1...@ID-49224.news.cis.dfn.de...


ore di elaborazione?
si puo' definire la seguente funzione ricorsiva:
f(n,m,s,x) :=  se n=1  allora  1 se s<=x<=m
                       altrimenti 0
               se n>1  somma per i=s+1..x di f(n-1,m,i,x-i+1)
le n-uple di somma x fatte da numeri da s a m sono f(n,m,s,x).
Esempio: sestuple di numeri da 1 a 90 di somma 300: f(6,90,1,300). Il
tempo di calcolo e' dell'ordine del minuto. Pero' si puo' anche
trovare un metodo iterativo (tabellare) equivalente per evitare i
tempi lunghi della ricorsione. In questo modo il tempo massimo e'
dell'ordine dimensione della tabella: 6*90*somma. Ciao

 voglio pensarci!!!
Al tempo. I miei tempi si riferivano a cicli completi di i1, quello più
esterno. Ma per tagliare la testa ho fatto girare il programma: 28 minuti.
Silv:o)

 Al tempo. I miei tempi si riferivano a cicli completi di i1, quello piů


                se n>1  somma per i=s+1..x di f(n-1,m,i,x-i+1)
Si puo' eliminare il parametro i, il numero minimo, togliendo n*i alla somma
obiettivo ed i al massimo utilizzabile. Infatti arrivare a 100 con 5 numeri
da 11 a 20 e come arrivare a 50 con 5 numeri da 1 a 10.
Quindi
f(n,m,x) :=  se n=1  allora  1 se x<=m
                   altrimenti 0
            se n>1  somma per i=1..x di f(n-1,m-i,x-n*i)
Se introduciamo un controllo iniziale sui parametri, uscendo immediatamente
se la somma massima possibile non arriva alla somma target o se la minima
oltrepassa il target, si pota drasticamente l'albero dell'analisi, con
significativi incrementi di prestazioni.
Questo problema secondo me si inserisce perfettamente nella discussione
sull'utilizzo della programmazione nella soluzione dei problemi
matematico-ricreativi.
Dato che non vedevo il modo di ottenere una formula compatta per risolvere
il quesito, avevo suggerito al proponente di utilizzare un pregramma per
ricavare i valori richiesti. Avevo bene in mente che si potevano tentare
approcci più raffinati (come l'elegante funzione ricorsiva proposta da El
Filibustero dimostra), così come resto convinto che il calcolo combinatorio
potrebbe ancora tornare a far sentire la sua voce in questo contesto,
soprattutto dopo aver ripescato quell'intervento (indovinate di chi?) che
risolve un problema abbastanza simile.
E' chiaro che l'approccio che ho proposto, una semplice enumerazione delle
combinazioni possibili, voleva solo dimostrare che non era necessario
ricorrere al calcolo per ogni istanza diversa del problema, potendosi
ricavare una volta per tutte il vettore delle soluzioni.
Anche nella sua grossonalità, fa il suo lavoro, visto che lo sforzo
computazione, con le dimensioni che stiamo trattando, non è affatto
proibitivo.
Non voglio assolutamente affermare che ci sia nulla di gratificante o
creativo in un approccio tanto miope, però continuo a pensare che ragionare
avendo come obiettivo un algoritmo può essere di grande aiuto. Almeno per
me, che non sempre riesco a formalizzare al meglio i miei processi mentali,
e che in ogni sommatoria vedo un ciclo for.
Ciao, Silv:o)

 
Io a volte...quando parlo con gli amici...gli dico:
"If.......then.......goto"
;-)
CiaO,
Massimo

 273?
a dir la verità la matrice è nata e morta in una finestra di debug, per cui
non l'ho tenuta, però con la funzione di El Filibustero ottimizzata trovo
qualsiasi risultato in al più due secondi.
270 => 3911910
271 => 3914353
272 => 3915627
273 => 3916220
e poi, vista la simmetria rispetto al centro (6*91/2=273), i risultani si
ripetono speculari
274 => 3915627
275 => 3914353
276 => 3911910
Ciao, Silv:o)

 allora la distribuzione di X1+X2+..+X6 è approssimabile ad una gussiana.
Confermo. Ho plottato il grafico della distribuzione delle somme,
normalizzata (Per una estrazione singola: media m=91/2 varianza
s^2=(90^2-1)/12; per la somma di 6 estrazioni: media 6*m e varianza 36*s^2).
Risulta quasi perfettamnte coincidente col tracciato della distribuzione
normale standard, soprattutto nei valori centrali. Quindi si puo' utilizzare
la gaussiana per avere una buona stima dei valori cercati.
Ciao, Silv:o)

 totò
Scusate il ritardo!
Il problema era piu' tosto del previsto [Murphy!]
Ho diagrammato i risultati numerici ottenuti con la forza quasi bruta.
Potete vedere il risultato in:
http://www.geocities.com/liviozuc/images/campana.gif
I risultati si raggruppano nella classica 'campana' tipica di molti
problemi statistici. Se il matematico non fornisce la "formula" esatta,
l'ingegnere può darne una approssimata, che in genere "serve e basta".
L'approssimazione poi si può anche ridurre a piacere aumentando la
complessità della formula.
Ma questa campana si può rappresentare abbastanza bene con
l'esponenziale che gli Americani chiamano "Standard Normal Curve" (e gli
Italiani non lo so!):
N=H*e^(((273-X)^2)/K) con 
H= 3,916,220
K= 7623.57
si ottiene la curva in fuxia.
L'errore percentuale normalizzato al massimo della funzione è basso,
quello relativo "ai bordi" può essere considerato grossolano. Si può
affinare a piacere.
Ciao a tutti!
Livio Zucca
--------------------------------
It isn't trivial!
http://www.geocities.com/liviozuc
-- 
Posted from 
laguna.tiscalinet.it
 [195.130.224.86] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG